Negative dependence and the geometry of polynomials

Borcea, Julius; Brändén, Petter; Liggett, Thomas

doi:10.1090/S0894-0347-08-00618-8

Negative dependence and the geometry of polynomials

Authors: Julius Borcea, Petter Brändén and Thomas M. Liggett
Journal: J. Amer. Math. Soc. 22 (2009), 521-567
MSC (2000): Primary 62H20; Secondary 05B35, 15A15, 15A22, 15A48, 26C10, 30C15, 32A60, 60C05, 60D05, 60E05, 60E15, 60G55, 60K35, 82B31
DOI: https://doi.org/10.1090/S0894-0347-08-00618-8
Published electronically: September 19, 2008
MathSciNet review: 2476782
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce the class of strongly Rayleigh probability measures by means of geometric properties of their generating polynomials that amount to the stability of the latter. This class covers important models such as determinantal measures (e.g. product measures and uniform random spanning tree measures) and distributions for symmetric exclusion processes. We show that strongly Rayleigh measures enjoy all virtues of negative dependence, and we also prove a series of conjectures due to Liggett, Pemantle, and Wagner, respectively. Moreover, we extend Lyons' recent results on determinantal measures, and we construct counterexamples to several conjectures of Pemantle and Wagner on negative dependence and ultra log-concave rank sequences.

1. M. Aissen, I. J. Schoenberg, A. Whitney, On the generating functions of totally positive sequences I, J. Analyse Math. 2 (1952), 93-103. MR 0053174 (14:732d)
2. E. D. Andjel, A correlation inequality for the symmetric exclusion process, Ann. Probab. 16 (1988), 717-721. MR 929073 (89d:60192)
3. M. F. Atiyah, R. Bott, L. Gårding, Lacunas for hyperbolic differential operators with constant coefficients I, Acta Math. 124 (1970), 109-189. MR 0470499 (57:10252a)
4. H. H. Bauschke, O. Güler, A. S. Lewis, H. S. Sendov, Hyperbolic polynomials and convex analysis, Canad. J. Math. 53 (2001), 470-488. MR 1827817 (2002c:90099)
5. J. Ben Hough, M. Krishnapur, Y. Peres, B. Virág, Determinantal processes and independence, Probab. Surv. 3 (2006), 206-229. MR 2216966 (2006m:60068)
6. J. Borcea, Spectral order and isotonic differential operators of Laguerre-Pólya type, Ark. Mat. 44 (2006), 211-240. MR 2292718 (2008c:30010)
7. J. Borcea, P. Brändén, Pólya-Schur master theorems for circular domains and their boundaries, to appear in Ann. of Math., http://annals.math.princeton.edu.
8. J. Borcea, P. Brändén, Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products, Duke Math. J. 143 (2008), 205-223. MR 2420507
9. J. Borcea, P. Brändén, Multivariate Pólya-Schur classification problems in the Weyl algebra, arXiv:math/0606360.
10. J. Borcea, P. Brändén, The Lee-Yang and Pólya-Schur programs I. Linear operators preserving stability, arXiv:0809.0401.
11. J. Borcea, P. Brändén, The Lee-Yang and Pólya-Schur programs II. Theory of stable polynomials and applications, preprint (2008).
12. J. Borcea, P. Brändén, G. Csordas, V. Vinnikov, Pólya-Schur-Lax problems: hyperbolicity and stability preservers, http://www.aimath.org/pastworkshops/polyaschurlax.html.
13. A. Borodin, A. Okounkov, G. Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), 481-515. MR 1758751 (2001g:05103)
14. J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson, N. Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992), 55-64. MR 1194785 (94g:05091)
15. P. Brändén, Polynomials with the half-plane property and matroid theory, Adv. Math. 216 (2007), 302-320. MR 2353258 (2008h:05022)
16. R. Burton, R. Pemantle, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab. 21 (1993), 1329-1371. MR 1235419 (94m:60019)
17. D. Carlson, Weakly sign-symmetric matrices and some determinantal inequalities, Colloq. Math. 17 (1967), 123-129. MR 0212041 (35:2916)
18. S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Alg. Disc. Meth. 3 (1982), 319-329. MR 666857 (83h:05062)
19. Y. Choe, J. Oxley, A. Sokal, D. G. Wagner, Homogeneous multivariate polynomials with the half-plane property, Adv. Appl. Math. 32 (2004), 88-187. MR 2037144 (2005d:05043)
20. Y. Choe, D. G. Wagner, Rayleigh matroids, Combin. Prob. Comput. 15 (2006), 765-781. MR 2248326 (2007f:05032)
21. J. B. Conrey, The Riemann hypothesis, Notices Amer. Math. Soc. 50 (2003), 341-353. MR 1954010 (2003j:11094)
22. T. Craven, G. Csordas, Jensen polynomials and the Túran and Laguerre inequalities, Pacific J. Math 136 (1989), 241-260. MR 978613 (90a:26035)
23. D. J. Daley, D. Vere-Jones, An Introduction to the Theory of Point Processes. Springer, New York, 1988. MR 950166 (90e:60060)
24. D. Dubhashi, J. Jonasson, D. Ranjan, Positive influence and negative dependence, Combin. Probab. Comput. 16 (2007), 29-41. MR 2286510 (2008h:62035)
25. D. Dubhashi, V. Priebe, D. Ranjan, Negative Dependence Through the FKG Inequality, Technical Report RS-96-27, BRICS Report Series, Basic Research In Computer Science, Århus, Denmark, 1996; web version available at http://citeseer.ist.psu.edu/352490.html.
26. D. Dubhashi, D. Ranjan, Balls and bins: A study in negative dependence, Random Struct. Algorithms 13 (1998), 99-124. MR 1642566 (99k:60048)
27. S. N. Ethier, T. G. Kurtz, Markov Processes: Characterization and Convergence. Wiley, 1986. MR 838085 (88a:60130)
28. S. M. Fallat, C. R. Johnson, Determinantal Inequalities: Ancient History and Recent Advances, Contemp. Math. 259 (2000), 199-212. MR 1778502 (2001m:15019)
29. T. Feder, M. Mihail, Balanced matroids, in ``Proceedings of the 24th Annual ACM (STOC)'', ACM Press, New York, 1992.
30. C. M. Fortuin, P. W. Kasteleyn, J. Ginibre, Correlation inequalities on some partially ordered sets, Commun. Math. Phys. 22 (1971), 89-103. MR 0309498 (46:8607)
31. F. R. Gantmacher, M. G. Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, Gostechizdat, 1950.
32. J. H. Grace, The zeros of a polynomial, Proc. Cambridge Philos. Soc. 11 (1902), 352-357.
33. G. Grimmett, The Random Cluster Model. Springer, 2006. MR 2243761 (2007m:60295)
34. L. Gurvits, A proof of hyperbolic van der Waerden conjecture: the right generalization is the ultimate simplification, arXiv:math/0504397.
35. L. Gurvits, Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like Conjectures: sharper bounds, simpler proofs and algorithmic applications, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp.417-426. MR 2277167
36. O. Güler, Hyperbolic polynomials and interior point methods for convex programming, Math. Oper. Res. 22 (1997), 350-377. MR 1450796 (98d:90084)
37. L. Gårding, An inequality for hyperbolic polynomials, J. Math. Mech. 8 (1959), 957-965. MR 0113978 (22:4809)
38. G. H. Hardy, J. E. Littlewood, G. Pólya, Inequalities. 2nd ed., Cambridge Univ. Press, Cambridge, United Kingdom, 1988. MR 944909 (89d:26016)
39. O. Holtz, -matrices satisfy Newton's inequalities, Proc. Amer. Math. Soc. 133 (2005), 711-717. MR 2113919 (2005k:15042)
40. O. Holtz, H. Schneider, Open problems on GKK $\tau$ -matrices, Linear Algebra Appl. 345 (2002), 263-267. MR 1883278
41. O. Holtz, B. Sturmfels, Hyperdeterminantal relations among symmetric principal minors, J. Algebra 316 (2007), 634-648. MR 2358606
42. O. Häggström, Random-cluster measures and uniform spanning trees, Stoch. Proc. Appl. 59 (1995), 267-275. MR 1357655 (97b:60170)
43. L. Hörmander, Notions of Convexity. Progr. Math. 127. Birkhäuser, Boston, MA, 1994. MR 1301332 (95k:00002)
44. G. James, C. Johnson, S. Pierce, Generalized matrix function inequalities on -matrices, J. London Math. Soc (2) 57 (1998), 562-582. MR 1659833 (2000b:15005)
45. K. Joag-Dev, F. Proschan, Negative association of random variables with applications, Ann. Stat. 11 (1983), 286-295. MR 684886 (85d:62058)
46. K. Johansson, Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2) 153 (2001), 259-296. MR 1826414 (2002g:05188)
47. K. Johansson, Determinantal processes with number variance saturation, Commun. Math. Phys. 252 (2004), 111-148. MR 2103906 (2006b:82110)
48. J. Kahn, M. Neiman, Negative correlation and log-concavity, arXiv:math/0712.3507.
49. S. Karlin, Total Positivity. Vol. I. Stanford Univ. Press, Stanford, CA, 1968. MR 0230102 (37:5667)
50. B. Ja. Levin, Distribution of Zeros of Entire Functions. Transl. Math. Monogr. 5, Amer. Math. Soc., Providence, R.I., 1980. MR 589888 (81k:30011)
51. E. H. Lieb, A. D. Sokal, A general Lee-Yang theorem for one-component and multicomponent ferromagnets, Commun. Math. Phys. 80 (1981), 153-179. MR 623156 (83c:82008)
52. T. M. Liggett, Interacting Particle Systems. Springer, 1985. MR 776231 (86e:60089)
53. T. M. Liggett, Ultra log-concave sequences and negative dependence, J. Combin. Theory Ser. A 79 (1997), 315-325. MR 1462561 (98j:60018)
54. T. M. Liggett, Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer, 1999. MR 1717346 (2001g:60247)
55. T. M. Liggett, Negative correlations and particle systems, Markov Proc. Rel. Fields 8 (2002), 547-564. MR 1957219 (2004f:60207)
56. T. M. Liggett, Distributional limits for the symmetric exclusion process, to appear in Stoch. Proc. Appl, arXiv:math/0710.3606.
57. R. Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167-212. MR 2031202 (2005b:60024)
58. R. Lyons, Y. Peres, Probability on Trees and Networks. Book in progress, web version available at http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html.
59. R. Lyons, J. Steif, Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination, Duke Math. J. 120 (2003), 515-575. MR 2030095 (2004k:60100)
60. K. Markström, Negative association does not imply log-concavity of the rank sequence, J. Appl. Probab. 44 (2007), 1119-1121; updated version: http://abel.math.umu.se/˜klasm/. MR 2382951
61. A. Marshall, I. Olkin, Inequalities: Theory of Majorization and Its Applications. Academic Press, New York, 1979. MR 552278 (81b:00002)
62. J. H. Mason, Matroids: unimodal conjectures and Motzkin's theorem, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 207-220. Inst. Math. Appl., Southend-on-Sea, 1972. MR 0349445 (50:1939)
63. C. Newman, Normal fluctuations and the FKG inequalities, Commun. Math. Phys. 74 (1980), 119-128. MR 576267 (81i:82070)
64. A. Okounkov, N. Reshetikhin, Correlation function of Schur process with applications to local geometry of a random 3-dimensional Young diagram, J. Amer. Math. Soc. 16 (2003), 581-603. MR 1969205 (2004b:60033)
65. R. Pemantle, Towards a theory of negative dependence, J. Math. Phys. 41 (2000), 1371-1390. MR 1757964 (2001g:62039)
66. Q. I. Rahman, G. Schmeisser, Analytic Theory of Polynomials. London Math. Soc. Monogr. (N. S.) 26, Oxford Univ. Press, New York, NY, 2002. MR 1954841 (2004b:30015)
67. G.-C. Rota, D. Sharp, Mathematics, Philosophy, and Artificial Intelligence: a Dialogue with Gian-Carlo Rota and David Sharp, Los Alamos Science, Spring/Summer 1985.
68. C. Semple, D. J. A. Welsh, Negative correlation in graphs and matroids, Combin. Prob. Comput. 15 (2006), 765-781.
69. P. D. Seymour, D. J. A. Welsh, Combinatorial applications of an inequality from statistical mechanics, Math. Proc. Camb. Phil. Soc. 77 (1975), 485-495. MR 0376378 (51:12554)
70. A. D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, in ``Surveys in Combinatorics, 2005'' (B. S. Webb, ed.), Cambridge Univ. Press, Cambridge, United Kingdom, 2005. MR 2187739 (2006k:05052)
71. G. Szegö, Bemerkungen zu einem Satz von J. H. Grace über die Wurzeln algebraischer Gleichungen, Math. Z. 13 (1922), 28-55. MR 1544526
72. D. G. Wagner, Negatively correlated random variables and Mason's conjecture for independent sets in matroids, Ann. Combin. 12 (2008), 211-239.
73. D. G. Wagner, Matroid inequalities from electrical network theory, Electron. J. Combin. 11 (2005), A1 (17pp). MR 2195432 (2006j:05041)
74. J. L. Walsh, On the location of the roots of certain types of polynomials, Trans. Amer. Math. Soc. 24 (1922), 163-180. MR 1501220