Strict log-concavity of the Kirchhoff polynomial and its applications. (English) Zbl 1447.05051
Summary: N. Anari et al. [“Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids”, Preprint, arXiv:1807.00929] showed that the basis generating functions for all matroids are log-concave. In this paper, we show that Kirchhoff polynomials, i.e. the basis generating functions for simple graphic matroids, are strictly log-concave. Our key observation is that the Kirchhoff polynomial of a complete graph can be seen as the irreducible relative invariant of a certain prehomogeneous vector space. Furthermore, we prove that an algebra associated to a graphic matroid satisfies the strong Lefschetz property and Hodge-Riemann bilinear relation at degree one.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
| 13E10 | Commutative Artinian rings and modules, finite-dimensional algebras |
| 13H10 | Special types (Cohen-Macaulay, Gorenstein, Buchsbaum, etc.) |
Keywords:
complete graph; graphic matroids; Artinian Gorenstein algebras; strong Lefshcetz property; Hodge-Riemann relation; prehomogeneous vector spacesReferences:
| [1] | N. Anari, S. Oveis Gharan, and C. Vinzant.Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 35-46. |
| [2] | R. A. Horn and C. R. Johnson.Matrix analysis. Second. Cambridge University Press, Cambridge, 2013, pp. xviii+643. · Zbl 1267.15001 |
| [3] | J. Huh and B. Wang. “Enumeration of points, lines, planes, etc”.Acta Math.218.2 (2017), pp. 297-317.Link. · Zbl 1386.05021 |
| [4] | T. Maeno and Y. Numata.Sperner property, matroids and finite-dimensional Gorenstein algebras. Vol. 580. Contemp. Math. Amer. Math. Soc., Providence, RI, 2012, pp. 73-84.Link. · Zbl 1317.13059 |
| [5] | T. Maeno and Y. Numata. “Sperner property and finite-dimensional Gorenstein algebras associated to matroids”.J. Commut. Algebra8.4 (2016), pp. 549-570.Link. · Zbl 1360.13048 |
| [6] | T. Maeno and J. Watanabe. “Lefschetz elements of Artinian Gorenstein algebras and Hessians of homogeneous polynomials”.Illinois J. Math.53.2 (2009), pp. 591-603.Link. · Zbl 1200.13031 |
| [7] | S. Murai, T. Nagaoka, and A. Yazawa. “Strictness of the log-concavity of generating polynomials of matroids”.arXiv:2003.09568. |
| [8] | T. Nagaoka and A. Yazawa. “Strict log-concavity of the Kirchhoff polynomial and its applications to the strong Lefschetz property”.arXiv:1904.01800. |
| [9] | J. Oxley.Matroid theory. Second. Vol. 21. Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, 2011, pp. xiv+684.Link. · Zbl 1254.05002 |
| [10] | M. Sato and T. Kimura. “A classification of irreducible prehomogeneous vector spaces and their relative invariants”.Nagoya Math. J.65(1977), pp. 1-155.Link. · Zbl 0321.14030 |
| [11] | W. T. Tutte.Graph theory. Vol. 21. Encyclopedia of Mathematics and its Applications. With a foreword by Crispin St. J. A. Nash-Williams, Reprint of the 1984 original. Cambridge University Press, Cambridge, 2001, pp. xxii+335. · Zbl 0964.05001 |
| [12] | J. Watanabe.A remark on the Hessian of homogeneous polynomials. Vol. 119. Queen’s Papers in Pure and Appl. Math. Queen’s Univ., Kingston, ON, 2000, pp. 171-178. · Zbl 1196.13009 |
| [13] | A. |
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.
