Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-13T04:45:14.523Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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