Ehrhart polynomials of rank two matroids

Luis Ferroni, Katharina Jochemko, Benjamin SchröterAdv. Appl. Math 2022 · OpenReview

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:

  1. Ehrhart Positivity: All coefficients of the Ehrhart polynomial are non-negative.
  2. $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

Abstract

Over a decade ago De Loera, Haws and Köppe conjectured that Ehrhart polynomials of matroid polytopes have only positive coefficients and that the coefficients of the corresponding ⁎h⁎<math><msup is="true"><mrow is="true"><mi is="true">h</mi></mrow><mrow is="true"><mo is="true">⁎</mo></mrow></msup></math>-polynomials form a unimodal sequence. The first of these intensively studied conjectures has recently been disproved by the first author who gave counterexamples in all ranks greater than or equal to three. In this article we complete the picture by showing that Ehrhart polynomials of matroids of lower rank have indeed only positive coefficients. Moreover, we show that they are coefficient-wise bounded by the Ehrhart polynomials of minimal and uniform matroids. We furthermore address the second conjecture by proving that ⁎h⁎<math><msup is="true"><mrow is="true"><mi is="true">h</mi></mrow><mrow is="true"><mo is="true">⁎</mo></mrow></msup></math>-polynomials of matroid polytopes of sparse paving matroids of rank two are real-rooted and therefore have log-concave and unimodal coefficients. In particular, this shows that the ⁎h⁎<math><msup is="true"><mrow is="true"><mi is="true">h</mi></mrow><mrow is="true"><mo is="true">⁎</mo></mrow></msup></math>-polynomial of the second hypersimplex is real-rooted, thereby strengthening a result of De Loera, Haws and Köppe.
BibTeX
@inproceedings{ferroni2022ehrhart,
  author = {Luis Ferroni and Katharina Jochemko and Benjamin Schröter},
  title = {{Ehrhart polynomials of rank two matroids}},
  booktitle = {Adv. Appl. Math},
  year = {2022},
  url = {https://openreview.net/forum?id=RIELldpiuX},
}
Figure