Negative dependence and the geometry of polynomials

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

¹ Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden
² Department of Mathematics, Royal Institute of Technology, SE-100 44 Stockholm, Sweden
³ Department of Mathematics, University of California, Los Angeles, California 90095-1555

Journal of the American Mathematical Society, Tome 22 (2009) no. 2, pp. 521-567

Résumé

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.

Détail

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

Bibliographie

[1] Aissen, Michael, Schoenberg, I. J., Whitney, A. M. On the generating functions of totally positive sequences. I J. Analyse Math. 1952 93 103

[2] Andjel, Enrique D. A correlation inequality for the symmetric exclusion process Ann. Probab. 1988 717 721

[3] Atiyah, M. F., Bott, R., Gè§Rding, L. Lacunas for hyperbolic differential operators with constant coefficients. I Acta Math. 1970 109 189

[4] Bauschke, Heinz H., Gã¼Ler, Osman, Lewis, Adrian S., Sendov, Hristo S. Hyperbolic polynomials and convex analysis Canad. J. Math. 2001 470 488

[5] Hough, J. Ben, Krishnapur, Manjunath, Peres, Yuval, Virã¡G, Bã¡Lint Determinantal processes and independence Probab. Surv. 2006 206 229

[6] Borcea, Julius Spectral order and isotonic differential operators of Laguerre-Pólya type Ark. Mat. 2006 211 240

[7] Borcea, Julius, Brã¤Ndã©N, Petter Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products Duke Math. J. 2008 205 223

[8] Borodin, Alexei, Okounkov, Andrei, Olshanski, Grigori Asymptotics of Plancherel measures for symmetric groups J. Amer. Math. Soc. 2000 481 515

[9] Bourgain, Jean, Kahn, Jeff, Kalai, Gil, Katznelson, Yitzhak, Linial, Nathan The influence of variables in product spaces Israel J. Math. 1992 55 64

[10] Brã¤Ndã©N, Petter Polynomials with the half-plane property and matroid theory Adv. Math. 2007 302 320

[11] Burton, Robert, Pemantle, Robin Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances Ann. Probab. 1993 1329 1371

[12] Carlson, David Weakly sign-symmetric matrices and some determinantal inequalities Colloq. Math. 1967 123 129

[13] Chaiken, Seth A combinatorial proof of the all minors matrix tree theorem SIAM J. Algebraic Discrete Methods 1982 319 329

[14] Choe, Young-Bin, Oxley, James G., Sokal, Alan D., Wagner, David G. Homogeneous multivariate polynomials with the half-plane property Adv. in Appl. Math. 2004 88 187

[15] Choe, Youngbin, Wagner, David G. Rayleigh matroids Combin. Probab. Comput. 2006 765 781

[16] Conrey, J. Brian The Riemann hypothesis Notices Amer. Math. Soc. 2003 341 353

[17] Craven, Thomas, Csordas, George Jensen polynomials and the Turán and Laguerre inequalities Pacific J. Math. 1989 241 260

[18] Daley, D. J., Vere-Jones, D. An introduction to the theory of point processes 1988

[19] Dubhashi, Devdatt, Jonasson, Johan, Ranjan, Desh Positive influence and negative dependence Combin. Probab. Comput. 2007 29 41

[20] Dubhashi, Devdatt, Ranjan, Desh Balls and bins: a study in negative dependence Random Structures Algorithms 1998 99 124

[21] Ethier, Stewart N., Kurtz, Thomas G. Markov processes 1986

[22] Fallat, Shaun M., Johnson, Charles R. Determinantal inequalities: ancient history and recent advances 2000 199 212

[23] Fortuin, C. M., Kasteleyn, P. W., Ginibre, J. Correlation inequalities on some partially ordered sets Comm. Math. Phys. 1971 89 103

[24] Grimmett, Geoffrey The random-cluster model 2006

[25] Gurvits, Leonid Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications 2006 417 426

[26] Gã¼Ler, Osman Hyperbolic polynomials and interior point methods for convex programming Math. Oper. Res. 1997 350 377

[27] Gè§Rding, Lars An inequality for hyperbolic polynomials J. Math. Mech. 1959 957 965

[28] Hardy, G. H., Littlewood, J. E., Pã³Lya, G. Inequalities 1988

[29] Holtz, Olga 𝑀-matrices satisfy Newton’s inequalities Proc. Amer. Math. Soc. 2005 711 717

[30] Holtz, Olga, Schneider, Hans Open problems on GKK 𝜏-matrices Linear Algebra Appl. 2002 263 267

[31] Holtz, Olga, Sturmfels, Bernd Hyperdeterminantal relations among symmetric principal minors J. Algebra 2007 634 648

[32] Hã¤Ggstrã¶M, Olle Random-cluster measures and uniform spanning trees Stochastic Process. Appl. 1995 267 275

[33] Hã¶Rmander, Lars Notions of convexity 1994

[34] James, Gordon, Johnson, Charles, Pierce, Stephen Generalized matrix function inequalities on 𝑀-matrices J. London Math. Soc. (2) 1998 562 582

[35] Joag-Dev, Kumar, Proschan, Frank Negative association of random variables, with applications Ann. Statist. 1983 286 295

[36] Johansson, Kurt Discrete orthogonal polynomial ensembles and the Plancherel measure Ann. of Math. (2) 2001 259 296

[37] Johansson, Kurt Determinantal processes with number variance saturation Comm. Math. Phys. 2004 111 148

[38] Karlin, Samuel Total positivity. Vol. I 1968

[39] Levin, B. Ja. Distribution of zeros of entire functions 1980

[40] Lieb, Elliott H., Sokal, Alan D. A general Lee-Yang theorem for one-component and multicomponent ferromagnets Comm. Math. Phys. 1981 153 179

[41] Liggett, Thomas M. Interacting particle systems 1985

[42] Liggett, Thomas M. Ultra logconcave sequences and negative dependence J. Combin. Theory Ser. A 1997 315 325

[43] Liggett, Thomas M. Stochastic interacting systems: contact, voter and exclusion processes 1999

[44] Liggett, T. M. Negative correlations and particle systems Markov Process. Related Fields 2002 547 564

[45] Lyons, Russell Determinantal probability measures Publ. Math. Inst. Hautes Études Sci. 2003 167 212

[46] Lyons, Russell, Steif, Jeffrey E. Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination Duke Math. J. 2003 515 575

[47] Markstrã¶M, Klas Negative association does not imply log-concavity of the rank sequence J. Appl. Probab. 2007 1119 1121

[48] Marshall, Albert W., Olkin, Ingram Inequalities: theory of majorization and its applications 1979

[49] Mason, J. H. Matroids: unimodal conjectures and Motzkin’s theorem 1972 207 220

[50] Newman, C. M. Normal fluctuations and the FKG inequalities Comm. Math. Phys. 1980 119 128

[51] Okounkov, Andrei, Reshetikhin, Nikolai Correlation function of Schur process with application to local geometry of a random 3-dimensional Young diagram J. Amer. Math. Soc. 2003 581 603

[52] Pemantle, Robin Towards a theory of negative dependence J. Math. Phys. 2000 1371 1390

[53] Rahman, Q. I., Schmeisser, G. Analytic theory of polynomials 2002

[54] Seymour, P. D., Welsh, D. J. A. Combinatorial applications of an inequality from statistical mechanics Math. Proc. Cambridge Philos. Soc. 1975 485 495

[55] Sokal, Alan D. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids 2005 173 226

[56] Szegã¶, G. Bemerkungen zu einem Satz von J. H. Grace über die Wurzeln algebraischer Gleichungen Math. Z. 1922 28 55

[57] Wagner, David G. Matroid inequalities from electrical network theory Electron. J. Combin. 2004/06

[58] Walsh, J. L. On the location of the roots of certain types of polynomials Trans. Amer. Math. Soc. 1922 163 180