Z-polynomials of matroids

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

Polynomials

$M$

$Z_M(t)$

$U_{3,4}$:

t^3 + 6*t^2 + 6*t + 1

$U_{3,5}$:

t^3 + 10*t^2 + 10*t + 1

$M(K_{4})$:

t^3 + 7*t^2 + 7*t + 1

$U_{3,6}$:

t^3 + 15*t^2 + 15*t + 1

Fano:

t^3 + 7*t^2 + 7*t + 1

NonFano:

t^3 + 9*t^2 + 9*t + 1

$U_{3,7}$:

t^3 + 21*t^2 + 21*t + 1

NonPappus:

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

Pappus:

t^3 + 18*t^2 + 18*t + 1

$U_{4,5}$:

t^4 + 10*t^3 + 20*t^2 + 10*t + 1

$U_{4,6}$:

t^4 + 20*t^3 + 45*t^2 + 20*t + 1

$U_{4,7}$:

t^4 + 35*t^3 + 84*t^2 + 35*t + 1

$U_{4,8}$:

t^4 + 56*t^3 + 140*t^2 + 56*t + 1

Vámos:

t^4 + 41*t^3 + 100*t^2 + 41*t + 1

$M(K_{5})$:

t^4 + 15*t^3 + 35*t^2 + 15*t + 1

$U_{5,6}$:

t^5 + 15*t^4 + 50*t^3 + 50*t^2 + 15*t + 1

$U_{5,7}$:

t^5 + 35*t^4 + 140*t^3 + 140*t^2 + 35*t + 1

$U_{5,8}$:

t^5 + 70*t^4 + 308*t^3 + 308*t^2 + 70*t + 1

TicTacToe:

t^5 + 94*t^4 + 428*t^3 + 428*t^2 + 94*t + 1

$U_{5,9}$:

t^5 + 126*t^4 + 588*t^3 + 588*t^2 + 126*t + 1

$R_{10}$:

t^5 + 30*t^4 + 120*t^3 + 120*t^2 + 30*t + 1

$M(K_{6})$:

t^5 + 31*t^4 + 155*t^3 + 155*t^2 + 31*t + 1

$U_{6,7}$:

t^6 + 21*t^5 + 105*t^4 + 175*t^3 + 105*t^2 + 21*t + 1

$U_{6,8}$:

t^6 + 56*t^5 + 350*t^4 + 616*t^3 + 350*t^2 + 56*t + 1

$U_{6,9}$:

t^6 + 126*t^5 + 882*t^4 + 1596*t^3 + 882*t^2 + 126*t + 1

$M^*(K_5)$:

t^6 + 37*t^5 + 230*t^4 + 400*t^3 + 230*t^2 + 37*t + 1

$U_{6,10}$:

t^6 + 252*t^5 + 1890*t^4 + 3480*t^3 + 1890*t^2 + 252*t + 1

$M(K_{7})$:

t^6 + 63*t^5 + 651*t^4 + 1365*t^3 + 651*t^2 + 63*t + 1

$U_{7,8}$:

t^7 + 28*t^6 + 196*t^5 + 490*t^4 + 490*t^3 + 196*t^2 + 28*t + 1

$U_{7,9}$:

t^7 + 84*t^6 + 756*t^5 + 2058*t^4 + 2058*t^3 + 756*t^2 + 84*t + 1

$U_{7,10}$:

t^7 + 210*t^6 + 2142*t^5 + 6090*t^4 + 6090*t^3 + 2142*t^2 + 210*t + 1

$U_{7,11}$:

t^7 + 462*t^6 + 5082*t^5 + 14850*t^4 + 14850*t^3 + 5082*t^2 + 462*t + 1

$M(K_{8})$:

t^7 + 127*t^6 + 2667*t^5 + 10941*t^4 + 10941*t^3 + 2667*t^2 + 127*t + 1

$U_{8,9}$:

t^8 + 36*t^7 + 336*t^6 + 1176*t^5 + 1764*t^4 + 1176*t^3 + 336*t^2 + 36*t + 1

$U_{8,10}$:

t^8 + 120*t^7 + 1470*t^6 + 5712*t^5 + 8820*t^4 + 5712*t^3 + 1470*t^2 + 120*t + 1

$U_{8,11}$:

t^8 + 330*t^7 + 4620*t^6 + 18942*t^5 + 29700*t^4 + 18942*t^3 + 4620*t^2 + 330*t + 1

$U_{8,12}$:

t^8 + 792*t^7 + 12012*t^6 + 50952*t^5 + 80685*t^4 + 50952*t^3 + 12012*t^2 + 792*t + 1

Definition

The $Z$-polynomial of a finite simple matroid $M$ is $Z_M(t)=\sum_{F\in L(M)}t^{\operatorname{rk}F}P_{M/F}(t)$, where $L(M)$ is its lattice of flats, $M/F$ is contraction by $F$, and $P$ is the matroid Kazhdan–Lusztig polynomial [1], Definition 2.1.

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)$ [1], Section 2.

(2)

$t^rZ_M(t^{-1})=Z_M(t)$ [1], Proposition 2.3.

(3)

$Z_M(0)=1$ and, for $r\geq2$, $[t]Z_M(t)=|\{F\in L(M):\operatorname{rk}F=r-1\}|$. The coefficient of $t^{r-1}$ in the defining sum counts hyperplanes, and (2) gives the coefficient of $t$.

(4)

$Z_{U_{r,r+1}}(t)=\sum_{i=0}^r\frac{1}{r+1}\binom{r+1}{i}\binom{r+1}{i+1}t^i$. The coefficient of $t^i$ is the Narayana number $N(r+1,i+1)$ [1], Proposition 4.9.

Comments

(5)

Write $r=\operatorname{rk}M$ and let $M|F$ denote restriction to a flat $F$. The Kazhdan–Lusztig polynomial $P_M(t)$ is characterized by $P_{\varnothing}(t)=1$, $2\deg P_M<r$ for $r>0$, and (1). The characteristic polynomial is $\chi_M(t)=\sum_{F\in L(M)}\mu(\varnothing,F)t^{r-\operatorname{rk}F}$, where $\mu$ is the Möbius function of $L(M)$.

(6)

The key $U(r,n)$ denotes the uniform matroid $U_{r,n}$ of rank $r$ on $n$ elements. The key $K(m)$ denotes the cycle matroid $M(K_m)$ of the complete graph on $m$ vertices, of rank $m-1$ and size $\binom m2$. These braid matroids have partition lattices of flats [1], Section 4. Fano, NonFano, Pappus, NonPappus, Vamos, R10, TicTacToe and K5dual name the exact Sage catalogue objects [2]; K5dual is $M^*(K_5)$.

(7)

The variable $t$ records algebraic grading. Cohomological degree $2i$ contributes $t^i$ in the interpretation of [1], Theorem 7.2. The empty matroid has $P=Z=1$. Contraction by a flat can introduce parallel elements; the full lattice of flats of each contraction is used. Looped input matroids are outside this table’s domain.

Programs

(P1)

Sage

# Place the attached generate.py in the working directory.
from generate import MatroidZ, uniform_pair, braid_pair
uniform_pair(8, 12)[1]
braid_pair(8)[1]

generator = MatroidZ()
[(p["matroid"], generator.value(p, 100)) for p in generator.enumerate()]

References

[1]

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

[2]

SageMath: database of matroids

Similar tables

Kazhdan–Lusztig polynomials of matroids — holds $P_M(t)$, whose values on contractions define $Z_M(t)$; shared matroid keys identify the same objects

Characteristic polynomials of matroids — holds $\chi_M(t)$, used for restrictions in (1)

Data properties

Entries are of type: integral polynomial

How well the digits are known: exact

Table is complete: no (it holds all 24 uniform matroids $U_{r,r+c}$ with $3\leq r\leq8$ and $1\leq c\leq4$, all five braid matroids $M(K_m)$ with $4\leq m\leq8$, and the eight Sage catalogue objects Fano, NonFano, Pappus, NonPappus, Vamos, R10, TicTacToe and K5dual. The four low-corank uniform slices include the circuit case and compare generic dependence across ranks. The braid family supplies the contrasting partition-lattice structure. The eight named objects form a noncanonical exploratory reference selection across finite geometry, representability contrasts, regular, paving and cographic structures, independent of ground-set labels and numeral base. These practical bounds broaden coverage while keeping polynomials short and full-lattice checks manageable, with at most ten elements in each named object and $4140$ partitions for $K(8)$. They do not assert completeness over all matroids of a rank or size)

How they were obtained:

All 37 entries are exact polynomials in $\mathbb Z[t]$. The generator applies the symmetry recursion of [1], Corollary 2.5, grouping uniform flats by size and braid flats by block count. For the named objects it uses the complete actual flat lattice, with each contraction indexed by its flat.

The separate checks.py implements the characteristic-polynomial recursion (1), without using $Z$-symmetry to compute its answers. It independently enumerates set partitions for braid restrictions and tests every ground-set subset to find the named objects’ flats. Seven known-answer controls precede full-coefficient comparisons for all 37 entries. The six circuit cases also agree with explicitly counted Dyck paths by number of peaks. All entries satisfy the degree, constant-term, leading-term, nonnegativity, symmetry and hyperplane-coefficient checks. The attached argument-selection.md explains the finite selection; dry_run.py reports a longest entry of 85 characters and an entries block of about 3 KB.