Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-08T00:13:40.830Z Has data issue: false hasContentIssue false
  • English
  • Français

Negative Correlation in Graphs and Matroids

Published online by Cambridge University Press:  01 May 2008

CHARLES SEMPLE  and
DOMINIC WELSH
CHARLES SEMPLE
Affiliation:
Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand (e-mail: c.semple@math.canterbury.ac.nz)
DOMINIC WELSH
Affiliation:
Merton College, University of Oxford, Oxford, UK (e-mail: d.welsh@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 3 , May 2008 , pp. 423 - 435
Copyright
Copyright © Cambridge University Press 2008

References

[1]Choe, Y.-B., Oxley, J. G., Sokal, A. D. and Wagner, D. G. (2004) Homogeneous multivariate polynomials with the half-plane property. Adv. Appl. Math. 32 88–187.CrossRefGoogle Scholar
[2]Choe, Y.-B. and Wagner, D. G. (2006) Rayleigh matroids. Combin. Probab. Comput. 15 765–781.CrossRefGoogle Scholar
[3]Cocks, C. C. Correlated matroids. Submitted.Google Scholar
[4]Feder, T. and Mihail, M. (1992) Balanced matroids. In Proc. 24th ACM Symposium on Theory of Computing, pp. 26–38.CrossRefGoogle Scholar
[5]Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971) Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22 89–103.CrossRefGoogle Scholar
[6]Grimmett, G. R. and Winkler, S. N. (2004) Negative association in uniform forests and connected graphs. Random Struct. Alg. 24 444–460.CrossRefGoogle Scholar
[7]Jerrum, M. Two remarks concerning balanced matroids. Combinatorica 26 733–742.CrossRefGoogle Scholar
[8]Oxley, J. G. (1992) Matroid Theory, Oxford University Press, New York.Google Scholar
[9]Pemantle, R. (2000) Towards a theory of negative independence. J. Math. Phys. 41 1371–1390.CrossRefGoogle Scholar
[10]Royle, G. and Sokal, A. D. (2004) The Brown–Colbourn conjecture on zeros of reliability polynomials is false. J. Combin. Theory Ser. B 91 345–360.CrossRefGoogle Scholar
[11]Seymour, P. D. and Welsh, D. J. A. (1975) Combinatorial applications of an inequality from statistical mechanics. Math. Proc. Cambridge Philos. Soc. 77 485–495.CrossRefGoogle Scholar
[12]Sokal, A. D. (2005) The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in Combinatorics 2005 (Webb, B. S., ed.), Cambridge University Press, pp. 173–226.CrossRefGoogle Scholar
[13]Wagner, D. G. (2005) Rank-three matroids are Rayleigh. Electron. J. Combin. 12 1–11.CrossRefGoogle Scholar
[14]Wagner, D. G. (2006) Negatively correlated random variables and Mason's conjecture. arXiv:math.CO/0602648v1.Google Scholar