Abstract
In a recent paper, the first author proved the log-concavity of the coefficients of the characteristic polynomial of a matroid realizable over a field of characteristic 0, answering a long-standing conjecture of Read in graph theory. We extend the proof to all realizable matroids, making progress towards a more general conjecture of Rota–Heron–Welsh. Our proof follows from an identification of the coefficients of the reduced characteristic polynomial as answers to particular intersection problems on a toric variety. The log-concavity then follows from an inequality of Hodge type.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aigner, M.: Whitney numbers. In: Combinatorial Geometries. Encyclopedia of Mathematics and its Applications, vol. 29, pp. 139–160. Cambridge University Press, Cambridge (1987)
Ardila F., Klivans C.: The Bergman complex of a matroid and phylogenetic trees. J. Combin. Theory Ser. B 96(1), 38–49 (2006) (2006i:05034)
Allermann L., Rau J.: First steps in tropical intersection theory. Math. Z 264(3), 633–670 (2010) (2011e:14110)
Brylawski, T.: Constructions. In: Theory of Matroids. Encyclopedia of Mathematics and its Applications, vol. 26, pp. 127–223. Cambridge University Press, Cambridge (1986)
Brylawski T.: The broken-circuit complex. Trans. Am. Math. Soc 234(2), 417–433 (1977) (80a:05055)
Cox, D., Little, J., Schenck, H.: Toric Varieties, Graduate Studies in Mathematics, vol. 124. American Mathematical Society, Providence (2011)
Edidin D., Graham W.: Equivariant intersection theory. Invent. Math 131(3), 595–634 (1998) (99j:14003a)
Fulton W., Sturmfels B.: Intersection theory on toric varieties. Topology 36(2), 335–353 (1997) (97h:14070)
Huh, J.: Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. preprint, arXiv:1008.4749
Katz E.: A tropical toolkit. Expo. Math 27(1), 1–36 (2009) (2010f:14069)
Katz, E.: Tropical intersection theory from toric varieties, Collect. Math. (2011). doi:10.1007/s13348-010-0014-8
Katz, E., Payne, S.: Realization spaces for tropical fans. In: Proceedings of the Abel Symposium on Combinatorial Aspects of Commutative Algebra and Algebraic Geometry. vol. 6, pp. 73–88. Springer, Berlin (2011)
Lazarsfeld, R.: Positivity in Algebraic Geometry. I. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics, vol. 48. Springer, Berlin (2004) (2005k:14001a)
Lenz, M.: The f-vector of a realizable matroid complex is strictly log-concave, preprint, arXiv:1106.2944
Mason, J.H.: Matroids: unimodal conjectures and Motzkin’s theorem. In: Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 207–220. Institute of Mathematics and its Applications, Southend-on-Sea (1972) (50 #1939)
Mikhalkin, G.: Tropical geometry and its applications. In: International Congress of Mathematicians. vol. II, pp. 827–852. European Mathematical Soceity, Zürich (2006) (2008c:14077)
Read R.C.: An introduction to chromatic polynomials. J. Combin. Theory 4, 52–71 (1968) (37 #104)
Rota, G.-C.: Combinatorial theory, old and new, Actes du Congrs International des Mathmaticiens (Nice, 1970), Tome 3, pp. 229–233. Gauthier-Villars, Paris (1971) (58 #21703)
Speyer, D.: Tropical Geometry. PhD thesis, University of California, Berkeley (2005)
Stanley, R.: Enumerative Combinatorics. Vol. 1. Cambridge Studies in Advanced Mathematics, vol. 49. Cambridge University Press, Cambridge (1997) (98a:05001)
Stanley, R.: An introduction to hyperplane arrangements. In: Geometric Combinatorics. IAS/Park City Mathematics Series, vol. 13, pp. 389–496. American Mathematical Soceity, Providence (2007)
Sturmfels, B.: Solving systems of polynomial equations. In: CBMS Regional Conference Series in Mathematics, vol. 97. American Mathematical Society, Providence (2002) (2003i:13037)
Tevelev J.: Compactifications of subvarieties of tori. Am. J. Math 129(4), 1087–1104 (2007) (2008f:14068)
Welsh, D.J.A.: Combinatorial problems in matroid theory. In: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969). pp. 291–306. Academic Press, London (43 #4701)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Huh, J., Katz, E. Log-concavity of characteristic polynomials and the Bergman fan of matroids. Math. Ann. 354, 1103–1116 (2012). https://doi.org/10.1007/s00208-011-0777-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00208-011-0777-6