Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroids

Anari, Nima; Liu, Kuikui; Oveis Gharan, Shayan; Vinzant, Cynthia

doi:10.1090/proc/16724

Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroids
HTML articles powered by AMS MathViewer

by Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant;

Proc. Amer. Math. Soc. 152 (2024), 1969-1981

DOI: https://doi.org/10.1090/proc/16724

Published electronically: March 20, 2024

HTML | PDF

Abstract:

We give a self-contained proof of the strongest version of Mason’s conjecture, namely that for any matroid the sequence of the number of independent sets of given sizes is ultra log-concave. To do this, we introduce a class of polynomials, called completely log-concave polynomials, whose bivariate restrictions have ultra log-concave coefficients. At the heart of our proof we show that for any matroid, the homogenization of the generating polynomial of its independent sets is completely log-concave.

References

Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, Ann. of Math. (2) 188 (2018), no. 2, 381–452. MR 3862944, DOI 10.4007/annals.2018.188.2.1
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid, STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, pp. 1–12. MR 4003314, DOI 10.1145/3313276.3316385
Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant, Log-concave polynomials, I: entropy and a deterministic approximation algorithm for counting bases of matroids, Duke Math. J. 170 (2021), no. 16, 3459–3504. MR 4332671, DOI 10.1215/00127094-2020-0091
Federico Ardila, The geometry of matroids, Notices Amer. Math. Soc. 65 (2018), no. 8, 902–908. MR 3823027
Karim A. Adiprasito and Raman Sanyal, Whitney numbers of arrangements via measure concentration of intrinsic volumes, Preprint, arXiv:1606.09412, 2016.
Julius Borcea, Petter Brändén, and Thomas M. Liggett, Negative dependence and the geometry of polynomials, J. Amer. Math. Soc. 22 (2009), no. 2, 521–567. MR 2476782, DOI 10.1090/S0894-0347-08-00618-8
Spencer Backman, Christopher Eur, and Connor Simpson, Simplicial generation of Chow rings of matroids, Sém. Lothar. Combin. 84B (2020), Art. 52, 11. MR 4138680
Petter Brändén and June Huh, Hodge-riemann relations for potts model partition functions, Preprint, arXiv:1811.01696, 2018.
Petter Brändén and June Huh, Lorentzian polynomials, Ann. of Math. (2) 192 (2020), no. 3, 821–891. MR 4172622, DOI 10.4007/annals.2020.192.3.4
Swee Hong Chan and Igor Pak, Log-concave poset inequalities: extended abstract, Sém. Lothar. Combin. 86B (2022), Art. 9, 12. MR 4490850
T. A. Dowling, On the independent set numbers of a finite matroid, Ann. Discrete Math. 8 (1980), 21–28. MR 597151, DOI 10.1016/S0167-5060(08)70842-2
T. Feder and M. Mihail, Balanced matroids, Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992, pp. 26–38, DOI 10.1145/129712.129716.
Leonid Gurvits, On multivariate Newton-like inequalities, Advances in combinatorial mathematics, Springer, Berlin, 2009, pp. 61–78. MR 2683227, DOI 10.1007/978-3-642-03562-3_{4}
June Huh and Eric Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids, Math. Ann. 354 (2012), no. 3, 1103–1116. MR 2983081, DOI 10.1007/s00208-011-0777-6
Yahya Ould Hamidoune and Isabelle Salaün, On the independence numbers of a matroid, J. Combin. Theory Ser. B 47 (1989), no. 2, 146–152. MR 1047782, DOI 10.1016/0095-8956(89)90015-4
June Huh, Benjamin Schröter, and Botong Wang, Correlation bounds for fields and matroids, J. Eur. Math. Soc. (JEMS) 24 (2022), no. 4, 1335–1351. MR 4397042, DOI 10.4171/JEMS/1119
June Huh, Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, J. Amer. Math. Soc. 25 (2012), no. 3, 907–927. MR 2904577, DOI 10.1090/S0894-0347-2012-00731-0
June Huh and Botong Wang, Enumeration of points, lines, planes, etc, Acta Math. 218 (2017), no. 2, 297–317. MR 3733101, DOI 10.4310/ACTA.2017.v218.n2.a2
J. Kahn and M. Neiman, Negative correlation and log-concavity, Random Structures Algorithms 37 (2010), no. 3, 367–388. MR 2724667, DOI 10.1002/rsa.20292
J. Kahn and M. Neiman, A strong log-concavity property for measures on Boolean algebras, J. Combin. Theory Ser. A 118 (2011), no. 6, 1749–1760. MR 2793607, DOI 10.1016/j.jcta.2011.02.007
Matthias Lenz, The $f$-vector of a representable-matroid complex is log-concave, Adv. in Appl. Math. 51 (2013), no. 5, 543–545. MR 3118543, DOI 10.1016/j.aam.2013.07.001
Carolyn Mahoney, On the unimodality of the independent set numbers of a class of matroids, J. Combin. Theory Ser. B 39 (1985), no. 1, 77–85. MR 805457, DOI 10.1016/0095-8956(85)90038-3
J. H. Mason, Matroids: unimodal conjectures and Motzkin’s theorem, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) Inst. Math. Appl., Southend-on-Sea, 1972, pp. 207–220. MR 349445
James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819, DOI 10.1093/acprof:oso/9780198566946.001.0001
Robin Pemantle, Towards a theory of negative dependence, J. Math. Phys. 41 (2000), no. 3, 1371–1390. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. MR 1757964, DOI 10.1063/1.533200
Paul Seymour, Matroids, hypergraphs, and the max-flow min-cut theorem, Ph.D. Thesis, University of Oxford, 1975.
P. D. Seymour and D. J. A. Welsh, Combinatorial applications of an inequality from statistical mechanics, Math. Proc. Cambridge Philos. Soc. 77 (1975), 485–495. MR 376378, DOI 10.1017/S0305004100051306
David G. Wagner, Negatively correlated random variables and Mason’s conjecture for independent sets in matroids, Ann. Comb. 12 (2008), no. 2, 211–239. MR 2428906, DOI 10.1007/s00026-008-0348-z
D. J. A. Welsh, Combinatorial problems in matroid theory, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) Academic Press, London-New York, 1971, pp. 291–306. MR 278975
Cui Kui Zhao, A conjecture on matroids, Neimenggu Daxue Xuebao 16 (1985), no. 3, 321–326 (Chinese, with English summary). MR 827685