<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Negatively Correlated Random Variables and Mason's Conjecture for Independent Sets in Matroids
David G. Wagner
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
dgwagner@math.uwaterloo.ca
Annals of Combinatorics 12 (2) p.211-239 June, 2008
AMS Subject Classification: 05A20; 05B35, 60C05, 82B20
Abstract:
Mason's Conjecture asserts that for an m-element rank r matroid $\M$ the sequence (Ik/\binom{m}{k} 0‹ k‹ r) is logarithmically concave, in which Ik is the number of independent k-sets of $\M$. A related conjecture in probability theory implies these inequalities provided that the set of independent sets of $\M$ satisfies a strong negative correlation property we call the Rayleigh condition. This condition is known to hold for the set of bases of a regular matroid. We show that if $\omega$ is a weight function on a set system $\Q$ that satisfies the Rayleigh condition then $\Q$ is a convex delta-matroid and $\omega$ is logarithmically submodular. Thus, the hypothesis of the probabilistic conjecture leads inevitably to matroid theory. We also show that two-sums of matroids preserve the Rayleigh condition in four distinct senses, and hence that the Potts model of an iterated two-sum of uniform matroids satisfies the Rayleigh condition. Numerous conjectures and auxiliary results are included.
Keywords: matroid, delta-matroid, unimodality, logarithmic concavity, Rayleigh monotonicity, Potts model, random cluster model

References:

1. A. Abdesselam, Grassmann-Berezin calculus and theorems of the matrix-tree type, Adv. Appl. Math. 33 (1) (2004) 51-–70.

2. A. Bj¨orner, The unimodality conjecture for convex polytopes, Bull. Amer. Math. Soc. 4 (2) (1981) 187-–188.

3. A. Bj¨orner, Partial unimodality for f -vectors of simplicial polytopes and spheres, Contemp. Math. 178 (1994) 45–-54.

4. J. Borcea, P. Br¨and´en, and T.M. Liggett, Negative dependence and the geometry of polynomials, arXiv: math.CO/0707.23-40.

5. A. Bouchet, Greedy algorithm and symmetric matroids, Math. Program. 38 (2) (1987) 147–- 159.

6. A. Bouchet and W.H. Cunningham, Delta-matroids, jump systems, and bisubmodular polyhedra, SIAM J. Discrete Math. 8 (1) (1995) 17-–32.

7. A. Bouchet and B. Jackson, Parity systems and the delta-matroid intersection problem, Electron. J. Combin. 7 (2000) #R14.

8. F. Brenti, G.F. Royle, and D.G. Wagner, Location of zeros of chromatic and related polynomials of graphs, Canad. J. Math. 46 (1) (1994) 55-–80.

9. D.C. Brydges and J.Z. Imbrie, Branched polymers and dimensional reduction, Ann. of Math. (2) 158 (3) (2003) 1019-–1039.

10. S. Caracciolo, J.L. Jacobsen, H. Saleur, A.D. Sokal, and A. Sportiello, Fermionic eld theory for trees and forests, Phys. Rev. Lett. 93 (8) (2004) 080-601.

11. S. Chaiken, A combinatorial proof of the all-minors matrix-tree theorem, SIAM J. Algebraic Discrete Methods 3 (3) (1982) 319-–329.

12. Y.-B. Choe, Polynomials with the half-plane property and the support theorems, J. Combin. Theory Ser. B 94 (1) (2005) 117-–145.

13. Y.-B. Choe, J.G. Oxley, A.D. Sokal, and D.G. Wagner, Homogeneous polynomials with the half-plane property, Adv. Appl. Math. 32 (1-2) (2004) 88–-187.

14. Y.-B. Choe and D.G. Wagner, Rayleigh matroids, Combin. Probab. Comput. 15 (5) (2006) 765–-781.

15. J.E. Dawson, A collection of sets related to the Tutte polynomial of a matroid, In: Graph Theory, Lecture Notes in Math., Vol. 1073, Springer, Berlin, (1984) pp. 193-–204.

16. T.A. Dowling, On the independent set numbers of a nite matroid, Ann. Discrete Math. 8 (1980) 21-–28.

17. T. Feder and M. Mihail, Balanced Matroids, In: Proceedings of the 24th Annual ACM (STOC), Victoria B.C., ACM Press, New York, 1992.

18. A. Frank and E. Tardos, Generalized polymatroids and submodular ows, Math. Program. 42 (1988) (3) 489-–563.

19. J.F. Geelen, S. Iwata, and K. Murota, The linear delta-matroid parity problem, J. Combin. Theory Ser. B 88 (2003) (2) 377–-398.

20. C.D. Godsil, Real graph polynomials, In: Progress in Graph Theory, J.A. Bondy and U.S.R. Murty, Eds., Academic Press, Toronto, 1984.

21. G.R. Grimmett and S.N. Winkler, Negative association in uniform forests and connected graphs, Random Structures Algorithms 24 (4) (2004) 444-–460.

22. G.H. Hardy, J.E. Littlewood, and G. P´olya, Inequalities, 2nd Ed., Cambridge Univ. Press, Cambridge, 1952.

23. S.G. Hoggar, Chromatic polynomials and logarithmic concavity, J. Combin. Theory Ser. B 16 (1974) 248–-254.

24. O. Holtz, M-Matrices satisfy Newton's inequalities, Proc. Amer. Math. Soc. 133 (3) (2005) 711-–717.

25. B. Jackson, Zeros of chromatic and ow polynomials of graphs, J. Geom. 76 (1-2) (2003) 95-–109.

26. J. Kahn and M. Neiman, Negative correlation and log-concavity, arXiv: math.CO/0712.3507.

27. S. Karlin, Total Positivity, Vol. I, Stanford Univ. Press, Stanford, 1968.

28. T.M. Liggett, Ultra logconcave sequences and negative dependence, J. Combin. Theory Ser. A 79 (2) (1997) 315-–325.

29. R. Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes ´ Etudes Sci. 98 (2003) 167–-212.

30. C. Mahoney, On the unimodality of the independent set numbers of a class of matroids, J. Combin. Theory Ser. B 39 (1) (1985) 77-–85.

31. J.H. Mason, Matroids: unimodal conjectures and Motzkin's theorem, In: Combinatorics, Proc. Conf. Combinatorial Math., Inst. Math. Appl., Southend-on-Sea, (1972) pp. 207-–220.

32. K.V. Menon, On the convolution of logarithmically concave sequences, Proc. Amer. Math. Soc. 23 (1969) 439-–411.

33. R. Pemantle, Towards a theory of negative dependence, J. Math. Phys. 41 (3) (2000) 1371– 13-90.

34. R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52–-71.

35. G.-C. Rota, Combinatorial theory, old and new, In: Actes du Congres International des Math´ematiciens, Vol. 3, Gauthier-Villars, Paris, (1971) pp. 229–-233.

36. P.D. Seymour, On the points-lines-planes conjecture, J. Combin. Theory Ser. B 33 (1) (1982) 17-–26.

37. P.D. Seymour and D.J.A.Welsh, Combinatorial applications of an inequality from statistical mechanics, Math. Proc. Cambridge Philos. Soc. 77 (1975) 495-–495.

38. A.D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, In: Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser., Vol. 327, B.S. Webb, Ed., Cambridge Univ. Press, Cambridge, (2005) pp. 173–-226.

39. R.P. Stanley, Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Combin. Theory Ser. A 31 (1) (1981) 56-–65.

40. D.G. Wagner, Rank three matroids are Rayleigh, Electron. J. Combin. 12 (2005) #N8.

41. D.G. Wagner, Matroid inequalities from electrical network theory, Electron. J. Combin. 11 (2) (2004/06) #A1.

42. D.J.A. Welsh, Combinatorial problems in matroid theory, In: Combinatorial Mathematics and Its Applications, D.J.A.Welsh, Ed., Academic Press, London, (1971) pp. 291-–306.

43. C.K. Zhao, A conjecture on matroids, Acta Scientiarum Naturalium Universitatis Neimongol 16 (3) (1985) 321-–326.