Abstract
Let $\rho$ be a non-negative integer. A $\rho$-removed uniform matroid is a matroid obtained from a uniform matroid by removing a collection of $\rho$ disjoint bases. We present a combinatorial formula for Kazhdan–Lusztig polynomials of $\rho$-removed uniform matroids, using skew Young Tableaux. Even for uniform matroids, our formula is new, gives manifestly positive integer coefficients, and is more manageable than known formulas.
Introduction
In the study of matroids—mathematical structures that generalize linear independence—Kazhdan-Lusztig (KL) polynomials have become a central object of interest since their introduction by Elias, Proudfoot, and Wakefield in 2016. A long-standing conjecture in this field is that the coefficients of these polynomials are non-negative integers, a property known as "positivity." However, calculating these coefficients is computationally intensive, and existing formulas often lack a clear combinatorial intuition.
This paper addresses these challenges by focusing on a specific class: $\rho$-removed uniform matroids ($U_{m,d}(\rho)$). These are derived from uniform matroids of rank $d$ by removing $\rho$ disjoint bases. The authors provide a new, "manifestly positive" formula that connects these abstract polynomials to the concrete geometry of skew Young Tableaux.
The Combinatorial Approach
The core of the paper's methodology lies in identifying the coefficients of the KL polynomials with the number of "legal fillings" of specific skew Young diagrams. A skew Young diagram is a "hook-like" arrangement of boxes. A filling is considered legal if the numbers placed in the boxes strictly increase along both rows and columns.
By defining the $i$-th coefficient $c^i_{m,d}$ as the number of such fillings for a diagram of a specific shape (determined by parameters $m, d,$ and $i$), the authors prove that these counts satisfy the recursive definitions required for KL polynomials. This approach transforms an algebraic problem into a counting problem, making the positivity of the coefficients self-evident.
Key Insights and Symmetry
One of the most significant contributions of this work is providing a "philosophical reason" for a known symmetry in KL coefficients. It was previously observed that $c^i_{m,d} = c^i_{d-2i, m+2i}$, but the underlying cause was obscure. The authors demonstrate that this symmetry corresponds exactly to a 180-degree rotation of the skew Young diagram. This geometric interpretation provides a deep link between the algebraic properties of the matroid and the combinatorial properties of the tableaux.
Furthermore, the paper utilizes inclusion-exclusion principles to relate these complex skew shapes back to standard Young tableaux. This allows for the application of the well-known "hook length formula," making the new formula significantly more manageable and computationally efficient than its predecessors.
Main Results
The research culminates in several key theorems:
- Theorem 1 & 14: Establish the explicit combinatorial formula for $U_{m,d}(\rho)$. The $i$-th coefficient is the number of legal fillings of the associated skew Young diagram, subject to three boundary restrictions related to the parameter $\rho$.
- Theorem 2: Simplifies the result for standard uniform matroids ($\rho=0$), where the coefficient is simply the total number of legal fillings of the diagram without additional restrictions.
- Corollary 15: Proves a monotonicity result, showing that as more bases are removed (increasing $\rho$), the KL coefficients become "weakly smaller."
Conclusion and Future Directions
While this work provides a powerful tool for uniform and $\rho$-removed uniform matroids, the broader goal remains a combinatorial interpretation for all matroids. The authors propose a new conjecture (Conjecture 16) regarding the relationship between the sets of bases of two matroids and their respective KL coefficients. Proving this conjecture would be a significant step toward a universal understanding of matroid KL polynomials. Additionally, extending this combinatorial framework to equivariant KL polynomials presents an exciting avenue for future research.
Summary updated