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
Bibliographic Information
- Nima Anari
- Affiliation: Department of Computer Science, Stanford University, Stanford, California 94305
- MR Author ID: 1008588
- ORCID: 0000-0002-4394-3530
- Email: anari@cs.stanford.edu
- Kuikui Liu
- Affiliation: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- MR Author ID: 1346291
- Email: liukui@csail.mit.edu
- Shayan Oveis Gharan
- Affiliation: Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, Washington 98195
- MR Author ID: 821927
- ORCID: 0000-0002-5504-0849
- Email: shayan@cs.washington.edu
- Cynthia Vinzant
- Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195
- MR Author ID: 881696
- Email: vinzant@uw.edu
- Received by editor(s): February 4, 2021
- Received by editor(s) in revised form: February 8, 2021, September 25, 2023, and November 12, 2023
- Published electronically: March 20, 2024
- Communicated by: Patricia Hersh
- © Copyright 2024 by the authors
- Journal: Proc. Amer. Math. Soc. 152 (2024), 1969-1981
- MSC (2020): Primary 05B35, 05A20, 52A41
- DOI: https://doi.org/10.1090/proc/16724
- MathSciNet review: 4728467