Log-concavity of characteristic polynomials and the Bergman fan of matroids

By June Huh, Eric Katz. 2011

140 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/4402318bf0c9db35dcb2deb854c8625a62524310

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Algebraic and Geometric Methods in Enumerative Combinatorics (2014, result): “induction using deletion-contraction. The second result is much deeper. It was conjectured by Rota in 1970 [Rot71], and recently proved by Huh [Huh12] for elds of characteristic 0 and by Huh and Katz [HK12] for arbitrary elds, drawing from toric geometry, tropical geometry, and matroid theory. This ”
Unimodality, log-concavity, real-rootedness and beyond (2015, background): “ characteristic polynomial by ˜ M(x) = ˜ M(x)=(x 1) =: rX 1 k=0 ( 1)kv k(M)xr(M) 1 k: Note that if fv k(M)g r(M) 1 k=0 is log{concave, then so is fw k(M)g r(M) k=0 , see [90]. Theorem 4.1 (Huh{Katz, [62]). If M is representable over some eld, then the sequence fv k(M)g r(M) 1 k=0 is log{concave. Sin”
A semi-small decomposition of the Chow ring of a matroid (2020, methodology): “The wonderful model XA was used in [19] to prove the log-concavity of the coefficients of the characteristic polynomial of realizable matroids.”
Lagrangian geometry of matroids (2020, methodology): “the maximal monomials in O have the same degree. See [BMMR 12] for a comprehensive survey of pure O-sequences. 10 FEDERICO ARDILA, GRAHAM DENHAM, AND JUNE HUH matroids representable over some ﬁeld in [HK12] and to all matroids in [AHK18]. An alternative proof of the same fact using the volume polyno”
Matroid Theory for Algebraic Geometers (2014, methodology): “The presentation of Huh-Katz’s proof of log-concavity of the characteristic polynomial differs from that of the published paper [45] but is similar to the exposition in Huh’s thesis [47].”
h-Vectors of matroids and logarithmic concavity (2012, background): “Since the cocycle matroid of a graph is representable over every field, Theorem 3 confirms a conjecture of Colbourn that the h-sequence of the reliability polynomial of a graph is log-concave [Col87].”
Tautological classes of matroids (2021, background): “[28] Let M be a loopless matroid (of rank r), and TM(x, y) the Tutte polynomial of M.”