×

Lorentzian polynomials. (English) Zbl 1454.52013

Summary: We study the class of Lorentzian polynomials. The class contains homogeneous stable polynomials as well as volume polynomials of convex bodies and projective varieties. We prove that the Hessian of a nonzero Lorentzian polynomial has exactly one positive eigenvalue at any point on the positive orthant. This property can be seen as an analog of the Hodge-Riemann relations for Lorentzian polynomials.
Lorentzian polynomials are intimately connected to matroid theory and negative dependence properties. We show that matroids, and more generally \(\text{M}\)-convex sets, are characterized by the Lorentzian property, and develop a theory around Lorentzian polynomials. In particular, we provide a large class of linear operators that preserve the Lorentzian property and prove that Lorentzian measures enjoy several negative dependence properties. We also prove that the class of tropicalized Lorentzian polynomials coincides with the class of \(\text{M}\)-convex functions in the sense of discrete convex analysis. The tropical connection is used to produce Lorentzian polynomials from \(\text{M}\)-convex functions.
We give two applications of the general theory. First, we prove that the homogenized multivariate Tutte polynomial of a matroid is Lorentzian whenever the parameter \(q\) satisfies \(0<q\leq 1\). Consequences are proofs of the strongest Mason’s conjecture from 1972 and negative dependence properties of the random cluster model in statistical physics. Second, we prove that the multivariate characteristic polynomial of an \(\text{M}\)-matrix is Lorentzian. This refines a result of Holtz who proved that the coefficients of the characteristic polynomial of an \(\text{M}\)-matrix form an ultra log-concave sequence.

MSC:

52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
14T15 Combinatorial aspects of tropical varieties
05A20 Combinatorial inequalities
05E14 Combinatorial aspects of algebraic geometry
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adiprasito, Karim; Huh, June; Katz, Eric, Hodge theory for combinatorial geometries, Ann. of Math. (2). Annals of Mathematics. Second Series, 188, 381-452 (2018) · Zbl 1442.14194 · doi:10.4007/annals.2018.188.2.1
[2] Anari, Nima; Oveis Gharan, Shayan; Vinzant, Cynthia, Log-concave polynomialS, entropy and a deterministic Approximation Algorithm for counting bases of matroids. 59th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience—{FOCS} 2018, 35-46 (2018) · doi:10.1109/FOCS.2018.00013
[3] Anari, Nima; Liu, Kuikui; Gharan, Shayan Oveis; Vinzant, Cynthia, Log-concave polynomials {II}: {H}igh-dimensional walks and an {FPRAS} for counting bases of a matroid. S{TOC}’19—{P}roceedings of the 51st {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing, 1-12 (2019) · Zbl 1433.68606 · doi:10.1145/3313276.3316385
[4] Anari, Nima; Liu, Kuikui; Gharan, Shayan Oveis; Vinzant, Cynthia, Log-Concave Polynomials {III: M}ason’s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids (2018) · Zbl 1433.68606
[5] Bapat, R. B.; Raghavan, T. E. S., Nonnegative Matrices and Applications, Encyclopedia Math. Appl., 64, xiv+336 pp. (1997) · Zbl 0879.15015 · doi:10.1017/CBO9780511529979
[6] Berg, Christian; Christensen, Jens Peter Reus; Ressel, Paul, Harmonic Analysis on Semigroups. Theory of Positive Definite and Related Functions, Grad. Texts in Math., 100, x+289 pp. (1984) · Zbl 0619.43001 · doi:10.1007/978-1-4612-1128-0
[7] Berman, Abraham; Plemmons, Robert J., Nonnegative Matrices in the Mathematical Sciences, Classics Appl. Math., 9, xx+340 pp. (1994) · Zbl 0815.15016 · doi:10.1137/1.9781611971262
[8] Borcea, Julius; Br\"{a}nd\'{e}n, Petter, Applications of stable polynomials to mixed determinants: {J}ohnson’s conjectures, unimodality, and symmetrized {F}ischer products, Duke Math. J.. Duke Mathematical Journal, 143, 205-223 (2008) · Zbl 1151.15013 · doi:10.1215/00127094-2008-018
[9] Borcea, Julius; Br\"{a}nd\'{e}n, Petter, The {L}ee-{Y}ang and {P}\'{o}lya-{S}chur programs. {I}. {L}inear operators preserving stability, Invent. Math.. Inventiones Mathematicae, 177, 541-569 (2009) · Zbl 1175.47032 · doi:10.1007/s00222-009-0189-3
[10] Borcea, Julius; Br\"{a}nd\'{e}n, Petter, Multivariate {P}\'{o}lya-{S}chur classification problems in the {W}eyl algebra, Proc. Lond. Math. Soc. (3). Proceedings of the London Mathematical Society. Third Series, 101, 73-104 (2010) · Zbl 1196.47028 · doi:10.1112/plms/pdp049
[11] Borcea, Julius; Br\"{a}nd\'{e}n, Petter; Liggett, Thomas M., Negative dependence and the geometry of polynomials, J. Amer. Math. Soc.. Journal of the Amer. Math. Soc., 22, 521-567 (2009) · Zbl 1206.62096 · doi:10.1090/S0894-0347-08-00618-8
[12] Br{\"{a}}nd{\'{e}}n, Petter, Polynomials with the half-plane property and matroid theory, Adv. Math.. Advances in Mathematics, 216, 302-320 (2007) · Zbl 1128.05014 · doi:10.1016/j.aim.2007.05.011
[13] Br{\"{a}}nd{\'{e}}n, Petter, Discrete concavity and the half-plane property, SIAM J. Discrete Math.. SIAM Journal on Discrete Mathematics, 24, 921-933 (2010) · Zbl 1228.90091 · doi:10.1137/090758738
[14] Br{\"{a}}nd{\'{e}}n, Petter; Huh, June, Hodge–{R}iemann relations for {P}otts model partition functions (2018)
[15] Brualdi, Richard A., Combinatorial Matrix Classes, Encycl. Math. Appl., 108, x+544 pp. (2006) · Zbl 1106.05001 · doi:10.1017/CBO9780511721182
[16] Castillo, Federico; Cid Ruiz, Yairon; Li, Binglin; Monta{\~{n}}o, Jonathan; Zhang, Naizhen, When are multidegrees positive? · Zbl 1453.14019
[17] Choe, Young-Bin; Oxley, James G.; Sokal, Alan D.; Wagner, David G., Homogeneous multivariate polynomials with the half-plane property. Special issue on the Tutte polynomial, Adv. in Appl. Math.. Advances in Applied Mathematics, 32, 88-187 (2004) · Zbl 1054.05024 · doi:10.1016/S0196-8858(03)00078-2
[18] Dellacherie, Claude; Martinez, Servet; San Martin, Jaime, Inverse {\(M\)}-Matrices and Ultrametric Matrices, Lecture Notes in Math., 2118, x+236 pp. (2014) · Zbl 1311.15002 · doi:10.1007/978-3-319-10298-6
[19] Dowling, T. A., On the independent set numbers of a finite matroid, Ann. Discrete Math.. Annals of Discrete Mathematics, 8, 21-28 (1980) · Zbl 0462.05020 · doi:10.1016/S0167-5060(08)70842-2
[20] Eur, Christopher; Huh, June, Logarithmic concavity for morphisms of matroids, Adv. Math.. Advances in Mathematics, 367, 107094-19 (2020) · Zbl 1437.05039 · doi:10.1016/j.aim.2020.107094
[21] Feder, T.; Mihail, Milena, Balanced matroids. Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 26-38 (1992) · doi:10.1145/129712.129716
[22] Fortuin, C. M.; Kasteleyn, P. W., On the random-cluster model. {I}. {I}ntroduction and relation to other models, Physica. Physica, 57, 536-564 (1972) · doi:10.1016/0031-8914(72)90045-6
[23] Fujishige, Satoru, Submodular Functions and Optimization, Ann. Discrete Math., 58, xiv+395 pp. (2005) · Zbl 1119.90044
[24] Fulton, William, Introduction to Toric Varieties, Ann. Math. Stud., 131, xii+157 pp. (1993) · Zbl 0813.14039 · doi:10.1515/9781400882526
[25] Fulton, William, Intersection Theory, Ergeb. Math. Grenzgeb., 2, xiv+470 pp. (1998) · Zbl 0885.14002 · doi:10.1007/978-1-4612-1700-8
[26] Galashin, Pavel; Karp, Steven N.; Lam, Thomas, The totally nonnegative {G}rassmannian is a ball, S\'{e}m. Lothar. Combin.. S\'{e}minaire Lotharingien de Combinatoire, 80B, 23-12 (2018) · Zbl 1417.05253
[27] Galashin, Pavel; Karp, Steven N.; Lam, Thomas, The totally nonnegative part of {\(G/P\)} is a ball, Adv. Math.. Advances in Mathematics, 351, 614-620 (2019) · Zbl 1440.14224 · doi:10.1016/j.aim.2019.05.009
[28] Gregor, Ji\v{r}\'{\i}, On quadratic {H}urwitz forms. {I}, Apl. Mat.. \v{C}eskoslovensk\'{a} Akademie V\v{e}d. Aplikace Matematiky, 26, 142-153 (1981) · Zbl 0457.15016
[29] Grimmett, Geoffrey, The Random-Cluster Model, Grundlehren Math. Wiss., 333, xiv+377 pp. (2006) · Zbl 1122.60087 · doi:10.1007/978-3-540-32891-9
[30] Grimmett, G. R.; Winkler, S. N., Negative association in uniform forests and connected graphs, Random Structures Algorithms. Random Structures & Algorithms, 24, 444-460 (2004) · Zbl 1048.60007 · doi:10.1002/rsa.20012
[31] Gurvits, Leonid, On multivariate {N}ewton-like inequalities. Advances in Combinatorial Mathematics, 61-78 (2009) · Zbl 1196.26020 · doi:10.1007/978-3-642-03562-3_4
[32] Hamidoune, Yahya Ould; Sala\"{u}n, Isabelle, On the independence numbers of a matroid, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 47, 146-152 (1989) · Zbl 0629.05020 · doi:10.1016/0095-8956(89)90015-4
[33] Hartshorne, Robin, Algebraic Geometry, 52, xvi+496 pp. (1977) · Zbl 0531.14001 · doi:10.1007/978-1-4757-3849-0
[34] Heine, Rudolf, Der {W}ertvorrat der gemischten {I}nhalte von zwei, drei und vier ebenen {E}ibereichen, Math. Ann.. Mathematische Annalen, 115, 115-129 (1938) · Zbl 0017.23003 · doi:10.1007/BF01448930
[35] Herzog, J\"{u}rgen; Hibi, Takayuki, Discrete polymatroids, J. Algebraic Combin.. Journal of Algebraic Combinatorics. An International Journal, 16, 239-268 (2002) · Zbl 1012.05046 · doi:10.1023/A:1021852421716
[36] Holtz, Olga, {\(M\)}-matrices satisfy {N}ewton’s inequalities, Proc. Amer. Math. Soc.. Proceedings of the Amer. Math. Soc., 133, 711-717 (2005) · Zbl 1067.15018 · doi:10.1090/S0002-9939-04-07576-8
[37] Horn, Roger A.; Johnson, Charles R., Topics in Matrix Analysis, viii+607 pp. (1994) · Zbl 0801.15001
[38] Huh, June, Combinatorial applications of the {H}odge-{R}iemann relations. Proceedings of the {I}nternational {C}ongress of {M}athematicians—{R}io de {J}aneiro 2018. {V}ol. {IV}. {I}nvited {L}ectures, 3093-3111 (2019) · Zbl 1448.05016 · doi:10.1142/9789813272880_0173
[39] Huh, June; Katz, Eric, Log-concavity of characteristic polynomials and the {B}ergman fan of matroids, Math. Ann.. Mathematische Annalen, 354, 1103-1116 (2012) · Zbl 1258.05021 · doi:10.1007/s00208-011-0777-6
[40] Huh, June; Schr\"oter, Benjamin; Wang, Botong, Correlation bounds for fields and matroids (2018)
[41] Huh, June; Wang, Botong, Enumeration of points, lines, planes, etc, Acta Math.. Acta Mathematica, 218, 297-317 (2017) · Zbl 1386.05021 · doi:10.4310/ACTA.2017.v218.n2.a2
[42] Huh, June; Matherne, Jacob P.; M\'esz\'aros, Karola; St. Dizier, Avery, Logarithmic concavity of {S}chur and related polynomials (2019)
[43] Kahn, Jeff, A normal law for matchings, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 20, 339-391 (2000) · Zbl 0963.05111 · doi:10.1007/PL00009835
[44] Kahn, J.; Neiman, M., Negative correlation and log-concavity, Random Structures Algorithms. Random Structures & Algorithms, 37, 367-388 (2010) · Zbl 1211.62098 · doi:10.1002/rsa.20292
[45] Kahn, J.; Neiman, M., A strong log-concavity property for measures on {B}oolean algebras, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 118, 1749-1760 (2011) · Zbl 1227.60005 · doi:10.1016/j.jcta.2011.02.007
[46] Karlin, Samuel, Total Positivity. {V}ol. {I}, xii+576 pp. (1968) · doi:10.1017/S0013091500009305
[47] Kobayashi, Yusuke; Murota, Kazuo; Tanaka, Ken’ichiro, Operations on {M}-convex functions on jump systems, SIAM J. Discrete Math.. SIAM Journal on Discrete Mathematics, 21, 107-129 (2007) · Zbl 1144.90015 · doi:10.1137/060652841
[48] Lazarsfeld, Robert, Positivity in Algebraic Geometry {I}. Classical Setting: Line Bundles and Linear Series, Ergeb. Math. Grenzgeb., 48, xviii+387 pp. (2004) · Zbl 1093.14501 · doi:10.1007/978-3-642-18808-4
[49] Lenz, Matthias, The {\(f\)}-vector of a representable-matroid complex is log-concave, Adv. in Appl. Math.. Advances in Applied Mathematics, 51, 543-545 (2013) · Zbl 1301.05382 · doi:10.1016/j.aam.2013.07.001
[50] Lieb, Elliott H.; Sokal, Alan D., A general {L}ee-{Y}ang theorem for one-component and multicomponent ferromagnets, Comm. Math. Phys.. Communications in Mathematical Physics, 80, 153-179 (1981) · doi:10.1007/BF01213009
[51] Liggett, Thomas M., Ultra logconcave sequences and negative dependence, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 79, 315-325 (1997) · Zbl 0888.60013 · doi:10.1006/jcta.1997.2790
[52] Liggett, Thomas M., Continuous Time {M}arkov Processes. An Introduction, Grad. Stud. Math., 113, xii+271 pp. (2010) · Zbl 1205.60002 · doi:10.1090/gsm/113
[53] Maclagan, Diane; Sturmfels, Bernd, Introduction to Tropical Geometry, Grad. Stud. Math., 161, xii+363 pp. (2015) · Zbl 1321.14048 · doi:10.1090/gsm/161
[54] Mahoney, Carolyn, On the unimodality of the independent set numbers of a class of matroids, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 39, 77-85 (1985) · Zbl 0554.05016 · doi:10.1016/0095-8956(85)90038-3
[55] Marker, David, Model Theory. An Introduction, Grad. Texts in Math., 217, viii+342 pp. (2002) · Zbl 1003.03034
[56] Mason, J. H., Matroids: unimodal conjectures and {M}otzkin’s theorem. Combinatorics, 207-220 (1972)
[57] Menon, K. V., On the convolution of logarithmically concave sequences, Proc. Amer. Math. Soc.. Proceedings of the Amer. Math. Soc., 23, 439-441 (1969) · Zbl 0193.02302 · doi:10.2307/2037189
[58] Murota, Kazuo, Discrete Convex Analysis, SIAM Monogr. Discrete Math. Appl., xxii+389 pp. (2003) · Zbl 1029.90055 · doi:10.1137/1.9780898718508
[59] Nuij, Wim, A note on hyperbolic polynomials, Math. Scand.. Mathematica Scandinavica, 23, 69-72 (1968) · Zbl 0189.40803 · doi:10.7146/math.scand.a-10898
[60] Oxley, James, Matroid Theory, Oxford Grad. Texts in Math., 21, xiv+684 pp. (2011) · Zbl 1254.05002 · doi:10.1093/acprof:oso/9780198566946.001.0001
[61] Pemantle, Robin, Towards a theory of negative dependence. Probabilistic techniques in equilibrium and nonequilibrium statistical physics, J. Math. Phys.. Journal of Mathematical Physics, 41, 1371-1390 (2000) · Zbl 1052.62518 · doi:10.1063/1.533200
[62] Pemantle, Robin, Hyperbolicity and stable polynomials in combinatorics and probability. Current Developments in Mathematics, 2011, 57-123 (2012) · Zbl 1316.62078 · doi:10.4310/CDM.2011.v2011.n1.a2
[63] Postnikov, Alexander, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN. International Mathematics Research Notices. IMRN, 1026-1106 (2009) · Zbl 1162.52007 · doi:10.1093/imrn/rnn153
[64] Schneider, Rolf, Convex Bodies: the {B}runn-{M}inkowski Theory, Encyclopedia Math. Appl., 151, xxii+736 pp. (2014) · Zbl 1287.52001 · doi:10.1017/CBO9781139003858
[65] Schoenberg, I. J., Metric spaces and positive definite functions, Trans. Amer. Math. Soc.. Transactions of the Amer. Math. Soc., 44, 522-536 (1938) · Zbl 0019.41502 · doi:10.2307/1989894
[66] Serre, Denis, Matrices, Grad. Texts in Math., 216, xiv+289 pp. (2010) · Zbl 1206.15001 · doi:10.1007/978-1-4419-7683-3
[67] Seymour, P., Matroids, hypergraphs, and the max-flow min-cut theorem (1975)
[68] Seymour, P. D.; Welsh, D. J. A., Combinatorial applications of an inequality from statistical mechanics, Math. Proc. Cambridge Philos. Soc.. Mathematical Proceedings of the Cambridge Philosophical Society, 77, 485-495 (1975) · Zbl 0345.05004 · doi:10.1017/S0305004100051306
[69] Shephard, G. C., Inequalities between mixed volumes of convex sets, Mathematika. Mathematika. A Journal of Pure and Applied Mathematics, 7, 125-138 (1960) · Zbl 0108.35203 · doi:10.1112/S0025579300001674
[70] Shioura, Akiyoshi, Matroid rank functions and discrete concavity, Jpn. J. Ind. Appl. Math.. Japan Journal of Industrial and Applied Mathematics, 29, 535-546 (2012) · Zbl 1254.90196 · doi:10.1007/s13160-012-0082-0
[71] Sokal, Alan D., The multivariate {T}utte polynomial (alias {P}otts model) for graphs and matroids. Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser., 327, 173-226 (2005) · Zbl 1110.05020 · doi:10.1017/CBO9780511734885.009
[72] Speyer, David E., Horn’s problem, {V}innikov curves, and the hive cone, Duke Math. J.. Duke Mathematical Journal, 127, 395-427 (2005) · Zbl 1069.14037 · doi:10.1215/S0012-7094-04-12731-0
[73] Timan, A. F.; Vestfrid, I. A., Any separable ultrametric space is isometrically embeddable in {\(l\sb{2} \)}, Funktsional. Anal. i Prilozhen.. Akademiya Nauk SSSR. Funktsional\cprime ny\u{\i} Analiz i ego Prilozheniya, 17, 85-86 (1983) · Zbl 0522.46017
[74] Wagner, David G., Rank-three matroids are {R}ayleigh, Electron. J. Combin.. Electronic Journal of Combinatorics, 12, 8-11 (2005) · Zbl 1075.05017 · doi:10.37236/1975
[75] Wagner, David G., Negatively correlated random variables and {M}ason’s conjecture for independent sets in matroids, Ann. Comb.. Annals of Combinatorics, 12, 211-239 (2008) · Zbl 1145.05003 · doi:10.1007/s00026-008-0348-z
[76] Wagner, David G., Multivariate stable polynomials: theory and applications, Bull. Amer. Math. Soc. (N.S.). Amer. Math. Soc.. Bulletin. New Series, 48, 53-84 (2011) · Zbl 1207.32006 · doi:10.1090/S0273-0979-2010-01321-5
[77] Welsh, D. J. A., Matroid Theory, L. M. S. Monographs, 8, xi+433 pp. (1976) · Zbl 0343.05002
[78] Zhao, Cui Kui, A conjecture on matroids, Neimenggu Daxue Xuebao. Neimenggu Daxue Xuebao. Ziran Kexue Ban. Acta Scientiarum Naturalium Universitatis Intramongolicae. Journal of Inner Mongolia University. Natural Sciences, 16, 321-326 (1985) · Zbl 1333.05070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.