Loading...
Please wait, while we are loading the content...
Similar Documents
Negative Correlation in Graphs and Matroids
| Content Provider | Scilit |
|---|---|
| Author | Semple, Charles Welsh, Dominic |
| Copyright Year | 2008 |
| Description | The following two conjectures arose in the work of Grimmett and Winkler, and Pemantle: the uniformly random forestFand the uniformly random connected subgraphCof a finite graphGhave the edge-negative association property. In other words, for all distinct edgeseandfofG, the probability thatF(respectively,C) containseconditioned on containingfis less than or equal to the probability thatF(respectively,C) containse. 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. |
| Related Links | http://www.math.canterbury.ac.nz/~c.semple/papers/SW07.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/83AA62C56FBF2C6E6C3D35AE43C10519/S0963548307008978a.pdf/div-class-title-negative-correlation-in-graphs-and-matroids-div.pdf |
| Ending Page | 435 |
| Page Count | 13 |
| Starting Page | 423 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548307008978 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 3 |
| Volume Number | 17 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2008-05-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Mathematical Physics Random Forest |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
