Kazhdan–Lusztig polynomials of matroids

edit · history · discussion · files · short url · combinatorics algebra polynomial

Polynomials

$M$

$P_M(t)$

$U_{5,6}$:

5*t^2 + 9*t + 1

$U_{5,7}$:

21*t^2 + 28*t + 1

$U_{5,8}$:

56*t^2 + 62*t + 1

TicTacToe:

80*t^2 + 85*t + 1

$U_{5,9}$:

120*t^2 + 117*t + 1

$R_{10}$:

15*t^2 + 20*t + 1

$M(K_{6})$:

15*t^2 + 16*t + 1

$U_{6,7}$:

21*t^2 + 14*t + 1

$U_{6,8}$:

98*t^2 + 48*t + 1

$U_{6,9}$:

288*t^2 + 117*t + 1

$M^*(K_5)$:

55*t^2 + 27*t + 1

$U_{6,10}$:

675*t^2 + 242*t + 1

$M(K_{7})$:

175*t^2 + 42*t + 1

$U_{7,8}$:

14*t^3 + 56*t^2 + 20*t + 1

$U_{7,9}$:

84*t^3 + 288*t^2 + 75*t + 1

$U_{7,10}$:

300*t^3 + 927*t^2 + 200*t + 1

$U_{7,11}$:

825*t^3 + 2365*t^2 + 451*t + 1

$M(K_{8})$:

735*t^3 + 1225*t^2 + 99*t + 1

$U_{8,9}$:

84*t^3 + 120*t^2 + 27*t + 1

$U_{8,10}$:

552*t^3 + 675*t^2 + 110*t + 1

$U_{8,11}$:

2145*t^3 + 2365*t^2 + 319*t + 1

$U_{8,12}$:

6380*t^3 + 6534*t^2 + 780*t + 1

Definition

The Kazhdan–Lusztig polynomial $P_M(t)\in\mathbb Z[t]$ of a matroid $M$ is the unique assignment to loopless matroids satisfying $P_{\varnothing}(t)=1$, $2\deg P_M<\operatorname{rk}M$ in positive rank, and the flat-lattice recursion (1) [1]. This table stores it for finite simple matroids.

Parameters

$M$

— matroid (a finite simple matroid)

Formulas

(1)

$t^rP_M(t^{-1})=\sum_{F\in L(M)}\chi_{M|F}(t)P_{M/F}(t)$, where $r=\operatorname{rk}M$ [1].

(2)

$P_M(0)=1$ and, for $r\geq2$, $[t]P_M(t)=|\{F\in L(M):\operatorname{rk}F=r-1\}|-|\{F\in L(M):\operatorname{rk}F=1\}|$ [1], Propositions 2.11–2.12.

Comments

(3)

Write $r=\operatorname{rk}M$, let $L(M)$ be the lattice of flats, and let $\mu$ be its Möbius function. The restriction to a flat $F$ is $M|F$ and the contraction is $M/F$. The characteristic polynomial is $\chi_M(t)=\sum_{F\in L(M)}\mu(\varnothing,F)t^{r-\operatorname{rk}F}$.

(4)

The key $U(r,n)$ names the uniform matroid $U_{r,n}$ of rank $r$ on $n$ elements. The key $K(m)$ names the cycle matroid $M(K_m)$ of the complete graph on $m$ vertices, with rank $m-1$ and $\binom m2$ elements. Its lattice of flats is the partition lattice [1]. The named objects R10, TicTacToe and K5dual are exactly the Sage catalogue matroids [3] [4]; K5dual is the matroid dual $M^*(K_5)$.

(5)

The variable $t$ has the grading of [1]; cohomological degree $2i$ contributes $t^i$ in the intersection-cohomology interpretation. Contraction by a flat can introduce parallel elements; its actual lattice of flats is used in the recursion. The rank-zero contraction is the empty matroid and has polynomial $1$.

Programs

(P1)

Sage

# Place the attached generate.py in the working directory.
from generate import MatroidKazhdanLusztig, uniform_kl, braid_kl
uniform_kl(8, 12)
braid_kl(8)

# Reproduce the table in its displayed order.
generator = MatroidKazhdanLusztig()
[(p["matroid"], generator.value(p, 100)) for p in generator.enumerate()]

References

[1]

Ben Elias, Nicholas Proudfoot and Max Wakefield, The Kazhdan–Lusztig polynomial of a matroid, Advances in Mathematics 299 (2016), 36–70. (arXiv) (doi)

[2]

Nicholas Proudfoot, Yuan Xu and Ben Young, The Z-polynomial of a matroid, Electronic Journal of Combinatorics 25(1) (2018), P1.26. (arXiv) (doi)

Links

[3]

SageMath: catalog of matroids

[4]

SageMath: database of matroids

Similar tables

Characteristic polynomials of matroids — holds the characteristic polynomials used for restrictions in (1); the same matroid keys identify the shared objects

Data properties

Entries are of type: integral polynomial

How well the digits are known: exact

Table is complete: no (it holds the 16 uniform matroids $U_{r,r+c}$ with $5\leq r\leq8$ and $1\leq c\leq4$, the three braid matroids $M(K_m)$ with $6\leq m\leq8$, and the three Sage catalogue objects R10, TicTacToe and K5dual. The four low-corank uniform slices and the braid family give distinct discrete reference families, starting where quadratic coefficients can occur. The named selection is a noncanonical exploratory comparison of regular, paving and cographic structures. These practical bounds keep the independent full-lattice checks small, with at most $4140$ flats for the braid examples and at most ten elements for the named examples; they do not assert completeness over all matroids of a rank or size)

How they were obtained:

All 22 entries are exact polynomials in $\mathbb Z[t]$. The generator uses the characteristic-polynomial recursion in [1], grouping uniform flats by cardinality and braid flats by block sizes. The named examples use the actual ranked flat lattices and their interval Möbius functions.

A separate implementation checks every coefficient using palindromicity of $Z_M(t)=\sum_{F\in L(M)}t^{\operatorname{rk}F}P_{M/F}(t)$ from [2], Proposition 2.3 and Corollary 2.5. It uses no characteristic-polynomial calculation; for the named objects it independently enumerates flats by testing every ground-set subset. Four known-value controls precede these comparisons. Fifteen entries also agree with the published tables in [1], Appendix A. All entries satisfy the degree bound, constant term, linear-coefficient identity and coefficient nonnegativity. The attached argument-selection.md records the family choices and finite bounds.