Abstract
We present a combinatorial formula using skew Young tableaux for the coefficients of Kazhdan-Lusztig polynomials for sparse paving matroids. These matroids are known to be logarithmically almost all matroids, but are conjectured to be almost all matroids. We also show the positivity of these coefficients using our formula. In special cases, such as uniform matroids, our formula has a nice combinatorial interpretation.
Introduction
In algebraic combinatorics, Kazhdan–Lusztig (KL) polynomials are powerful but notoriously difficult-to-compute invariants. Originally developed for Coxeter groups, they were extended to the world of matroids—mathematical structures generalizing linear independence—in 2016. While high-level algebraic geometry has proven that the coefficients of these polynomials are non-negative, "enlightening" combinatorial interpretations of what these coefficients represent remain elusive for most matroids.
This research focuses on sparse paving matroids, a class conjectured to encompass "almost all" matroids as the number of elements grows. Previously, explicit formulas for their KL polynomials were known only for very restricted sub-classes. This paper provides a concrete combinatorial formula for these coefficients and proves their non-negativity using elementary methods.
Combinatorial Methods: The "Skyt" Shape
The authors employ skew Young tableaux, a standard tool in representation theory used to count ways of filling grid-like shapes with numbers under specific constraints (typically increasing along rows and columns).
Central to their approach is the definition of a specific shape termed a "Skyt." As illustrated in Figure 1, a Skyt consists of a tall left column of height $a$, a tall right column of height $b$, and a middle section of width $i$ and height 2.
The number of valid standard skew Young tableaux for such a shape is denoted as $\text{skyt}(a, i, b)$. The authors derive the $i$-th coefficient of the KL polynomial by relating it to these counts.
Key Insights
Structural Invariance
A surprising finding is that the KL polynomial of a sparse paving matroid depends only on the number of its circuit-hyperplanes ($|CH|$), not on their internal arrangement. This significantly simplifies the study of these complex structures.
Elementary Positivity
While non-negativity was previously established using "heavy machinery" like Hodge theory, this paper provides a proof using more elementary combinatorial and analytical methods, including integral identities and established bounds on the number of circuit-hyperplanes.
Geometric Connections
For special cases, the formula relates to Catalan numbers and polygon dissections, linking matroid theory to classical geometry. Furthermore, the results support the conjecture that the "uniform matroid" (the simplest type) has the largest KL coefficients among all matroids of the same size and rank.
Main Results
The $i$-th coefficient $c^i_{m,d}(CH)$ of the KL polynomial for a sparse paving matroid of rank $d$ on $n$ elements (where $m = n - d$) is given by: $$c^i_{m,d}(CH) = \text{skyt}(m + 1, i, d - 2i + 1) - |CH| \cdot \overline{\text{skyt}}(i, d - 2i + 1)$$ where $\overline{\text{skyt}}$ represents a related tableau count. The paper rigorously proves that this value is always non-negative. By providing closed-form expressions using factorials and binomial coefficients, the authors make these polynomials significantly easier to compute than the standard recursive definitions.
Limitations and Future Work
While the formula is proven non-negative, it involves subtraction. In combinatorics, a "manifestly positive" formula (involving only addition) is preferred as it directly counts a set of objects. Currently, such an interpretation is only available for the sub-case where circuit-hyperplanes are disjoint. Additionally, the formula is specific to sparse paving matroids; extending these results to other classes like graphic or algebraic matroids remains an open challenge. Finally, the "real-rootedness" of these polynomials—whether all their roots are real—remains a major unanswered question.
Summary updated