TL;DR
This paper proves that Ehrhart polynomials for rank 2 matroids always have positive coefficients, settling a long-standing conjecture for this important class of matroids. It also shows that the related $h^*$-polynomials for a specific type of rank 2 matroid (sparse paving matroids) are real-rooted, implying unimodal coefficients.
What Problem Does This Paper Address?
Matroid theory is a fundamental area of combinatorics with deep connections to geometry and algebra. A key object of study is the matroid polytope, which is the convex hull of indicator vectors of the bases of a matroid. The Ehrhart polynomial of a lattice polytope counts the number of integer points within scaled versions of the polytope.
A decade ago, a conjecture by De Loera, Haws, and Köppe proposed two properties for Ehrhart polynomials of matroid polytopes:
- Ehrhart Positivity: All coefficients of the Ehrhart polynomial are non-negative.
- $h^*$-Polynomial Unimodality: The coefficients of the associated $h^*$-polynomial form a unimodal sequence.
While counterexamples to the first conjecture have been found for ranks 3 and higher, the status for lower ranks remained open. This paper focuses on rank 2 matroids, aiming to complete the picture for Ehrhart positivity and investigate the $h^*$-polynomial conjecture for a specific subclass.
Methods
The paper employs a combination of geometric and combinatorial techniques.
- Polytope Description: The authors utilize the known description of matroid polytopes and simplify it for rank 2 matroids, relating it to inequalities involving sums of coordinates.
- Ehrhart Polynomial Formulas: A central contribution is deriving a concrete formula for the Ehrhart polynomial of rank 2 matroids, which generalizes known formulas for hypersimplices. This formula is then used to prove Ehrhart positivity for rank 2 matroids.
- Bounding Techniques: They establish bounds for the Ehrhart polynomials of rank 2 matroids, showing they lie between those of the minimal and uniform matroids. This involves proving a superadditivity property for certain polynomials ($P_{a,n}$).
- $h^*$-Polynomial Analysis: For sparse paving matroids of rank 2, they derive a formula for the $h^*$-polynomial and use it to prove real-rootedness. This involves a clever substitution ($x = -\tan^2 \theta$) and analysis of trigonometric functions, leveraging inequalities and the Intermediate Value Theorem.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Rank 2 is Special: While higher-rank matroids can violate Ehrhart positivity, rank 2 matroids are "well-behaved" in this regard, always exhibiting positive coefficients. This suggests that rank 2 might be a critical threshold for certain combinatorial properties.
- Minimal and Uniform Matroids as Bounds: The paper shows that the Ehrhart polynomials of any rank 2 matroid are coefficient-wise bounded by those of the minimal and uniform matroids. This provides a concrete range for these polynomials.
- Real-Rootedness Implies Unimodality: A key strategy for proving unimodality of coefficients is to show that the polynomial is real-rooted (all its roots are real numbers). This paper successfully demonstrates real-rootedness for $h^*$-polynomials of sparse paving matroids.
- Trigonometric Substitution for $h^*$-Polynomials: The use of $x = -\tan^2 \theta$ to analyze the $h^*$-polynomials is a novel and powerful technique, transforming algebraic problems into geometric ones involving trigonometric identities.
Key Results
- Theorem 1.1: Ehrhart polynomials of all rank 2 matroids have only positive coefficients.
- Theorem 1.2: For any connected rank 2 matroid $M$, its Ehrhart polynomial $ehr(P(M), t)$ satisfies $ehr(P(T_{2,n}), t) \leq ehr(P(M), t) \leq ehr(P(U_{2,n}), t)$, where $T_{2,n}$ is the minimal matroid and $U_{2,n}$ is the uniform matroid.
- Theorem 1.3: For sparse paving matroids of rank 2, the $h^*$-polynomial is either $1$, $1+x$, or a real-rooted polynomial with positive coefficients. This implies unimodality and log-concavity for their coefficients.
Limitations and Future Work
- Generalizing Real-Rootedness: The paper proves real-rootedness for $h^*$-polynomials of sparse paving matroids of rank 2. A major open question is whether this holds for all rank 2 matroids, and potentially for higher ranks. The authors suggest that their trigonometric approach might be extendable.
- Positroids: The paper connects rank 2 matroids to positroids and conjectures that all positroids are Ehrhart positive. This is a broad generalization that would require new techniques.
- Rank vs. Hyperplane Size: The proof of real-rootedness relies on the degree of the $h^*$-polynomial, which can be lower than the rank if a hyperplane is large. Understanding how hyperplane sizes affect the degree and the real-rootedness property is an ongoing area of interest.
Summary updated