• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    Negative correlation in graphs and matroids

    Thumbnail
    View/Open
    semple_welsh_UCDMS2005-12_report.pdf (1.299Mb)
    Author
    Semple, C.
    Welsh, D.
    Date
    2005
    Permanent Link
    http://hdl.handle.net/10092/11721

    The following two conjectures arose in the work of Grimmett and Winkler, and Pemantle: the uniformly random forest F and the uniformly random connected subgraph C of a finite graph G have the edge-negative-association property. In other words, for all distinct edges e and f of G, the probability that F (respectively, C) contains e conditioned on containing f is less than or equal to the probability that F (respectively, C) contains e. Grimmett and Winkler showed that the first conjecture is true for all simple graphs on 8 vertices and all graphs on 9 vertices with at most 18 edges. In this paper, we describe an infinite, nontrivial class of graphs and matroids for which a generalized version of both conjectures holds.

    Subjects
    Negatively correlated
     
    balanced matroids
     
    Rayleigh matroids
     
    random cluster model
     
    Field of Research::01 - Mathematical Sciences::0101 - Pure Mathematics::010104 - Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
    Collections
    • Engineering: Reports [684]
    Rights
    http://library.canterbury.ac.nz/thesis/etheses_copyright.shtml

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us