h-Vectors of matroids and logarithmic concavity

By June Huh. 2012

68 citations recorded by the source corpus.

Abstract Let M be a matroid on E, representable over a field of characteristic zero. We show that h-vectors of the following simplicial complexes are log-concave: 1. The matroid complex of independent subsets of E. 2. The broken circuit complex of M relative to an ordering of E. The first implies a conjecture of Colbourn on the reliability polynomial of a graph, and the second implies a conjecture of Hoggar on the chromatic polynomial of a graph. The proof is based on the geometric formula for the characteristic polynomial of Denham, Garrousian, and Schulze.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/1af901f301a775d58c01a518c64b4d197b15c348

How researchers see this paper

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

In Algebra and Number Theory

1. Federico Ardila
2. Graham C. Denham
3. June Huh
4. Paolo Aluffi
5. Petter Brand'en
6. Eric Katz
7. Christopher Eur
8. Karim A. Adiprasito

In Computational Theory and Mathematics

1. Federico Ardila
2. Graham C. Denham
3. June Huh
4. Eric Katz
5. Christopher Eur
6. Bernd Sturmfels

In Discrete Mathematics and Combinatorics

1. Federico Ardila
2. Graham C. Denham
3. June Huh
4. Eric Katz
5. Petter Brand'en
6. Christopher Eur
7. Paolo Aluffi
8. Karim A. Adiprasito

Citations in the corpus

• The maximum likelihood degree of a very affine variety (2012, methodology): “It can be shown that some multiple of ξ is the fundamental class of an irreducible subvariety if and only if the ei form a log-concave sequence of nonnegative integers with no internal zeros [Huh12a, Theorem 21].”
• COMBINATORIAL APPLICATIONS OF THE HODGE–RIEMANN RELATIONS (2017, methodology): “ context of reliability polynomials [7]. When M is the dual of a graphic matroid, or more generally when M is realizable over the complex numbers, the log-concavity conjecture for h ipMqwas proved in [30] by applying an algebraic analog of the Alexandrov-Fenchel inequality to the variety of critical”
• Lagrangian geometry of matroids (2020, methodology): “For matroids representable over a field of characteristic 0, the log-concavity of the h-vector of the broken circuit complex was proved in [Huh15].”