Chow polynomials of matroids

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

Polynomials

$M$

$\underline H_M(t)$

$U_{3,4}$:

t^2 + 7*t + 1

$U_{3,5}$:

t^2 + 11*t + 1

$M(K_{4})$:

t^2 + 8*t + 1

$U_{3,6}$:

t^2 + 16*t + 1

Fano:

t^2 + 8*t + 1

NonFano:

t^2 + 10*t + 1

$U_{3,7}$:

t^2 + 22*t + 1

NonPappus:

t^2 + 21*t + 1

Pappus:

t^2 + 19*t + 1

$U_{4,5}$:

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

$U_{4,6}$:

t^3 + 36*t^2 + 36*t + 1

$U_{4,7}$:

t^3 + 57*t^2 + 57*t + 1

$U_{4,8}$:

t^3 + 85*t^2 + 85*t + 1

Vámos:

t^3 + 70*t^2 + 70*t + 1

$M(K_{5})$:

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

$U_{5,6}$:

t^4 + 51*t^3 + 161*t^2 + 51*t + 1

$U_{5,7}$:

t^4 + 92*t^3 + 337*t^2 + 92*t + 1

$U_{5,8}$:

t^4 + 155*t^3 + 631*t^2 + 155*t + 1

TicTacToe:

t^4 + 215*t^3 + 895*t^2 + 215*t + 1

$U_{5,9}$:

t^4 + 247*t^3 + 1087*t^2 + 247*t + 1

$R_{10}$:

t^4 + 151*t^3 + 541*t^2 + 151*t + 1

$M(K_{6})$:

t^4 + 187*t^3 + 732*t^2 + 187*t + 1

$U_{6,7}$:

t^5 + 113*t^4 + 813*t^3 + 813*t^2 + 113*t + 1

$U_{6,8}$:

t^5 + 211*t^4 + 1877*t^3 + 1877*t^2 + 211*t + 1

$U_{6,9}$:

t^5 + 373*t^4 + 3859*t^3 + 3859*t^2 + 373*t + 1

$M^*(K_5)$:

t^5 + 303*t^4 + 2553*t^3 + 2553*t^2 + 303*t + 1

$U_{6,10}$:

t^5 + 628*t^4 + 7258*t^3 + 7258*t^2 + 628*t + 1

$M(K_{7})$:

t^5 + 855*t^4 + 9556*t^3 + 9556*t^2 + 855*t + 1

$U_{7,8}$:

t^6 + 239*t^5 + 3361*t^4 + 7631*t^3 + 3361*t^2 + 239*t + 1

$U_{7,9}$:

t^6 + 457*t^5 + 8269*t^4 + 20155*t^3 + 8269*t^2 + 457*t + 1

$U_{7,10}$:

t^6 + 838*t^5 + 18220*t^4 + 46570*t^3 + 18220*t^2 + 838*t + 1

$U_{7,11}$:

t^6 + 1475*t^5 + 36752*t^4 + 97142*t^3 + 36752*t^2 + 1475*t + 1

$M(K_{8})$:

t^6 + 4111*t^5 + 111211*t^4 + 299882*t^3 + 111211*t^2 + 4111*t + 1

$U_{8,9}$:

t^7 + 493*t^6 + 12421*t^5 + 53833*t^4 + 53833*t^3 + 12421*t^2 + 493*t + 1

$U_{8,10}$:

t^7 + 958*t^6 + 31990*t^5 + 155092*t^4 + 155092*t^3 + 31990*t^2 + 958*t + 1

$U_{8,11}$:

t^7 + 1805*t^6 + 74504*t^5 + 389456*t^4 + 389456*t^3 + 74504*t^2 + 1805*t + 1

$U_{8,12}$:

t^7 + 3290*t^6 + 159435*t^5 + 878802*t^4 + 878802*t^3 + 159435*t^2 + 3290*t + 1

Definition

For a finite simple matroid $M$, the Chow polynomial $\underline H_M(t)=\sum_{i\geq0}\dim_{\mathbb Q}A^i(M)t^i$ is the Hilbert–Poincaré series of its ordinary Chow ring $A^*(M)$ [1]. The ring uses the maximal building set of all nonempty flats, with every divisor generator in degree one.

Parameters

$M$

— matroid (a finite simple matroid)

Formulas

(1)

$\underline H_M(t)=\sum_{\varnothing\ne F\in L(M)}\bar\chi_{M|F}(t)\underline H_{M/F}(t)$ for positive rank [1], Theorem 3.12.

(2)

Put $w_d(t)=\sum_{j=1}^{d-1}t^j$, with $w_1(t)=0$. Then $\underline H_M(t)=1+\sum_{\varnothing\ne F\in L(M)}w_{\operatorname{rk}F}(t)\underline H_{M/F}(t)$. This follows by grouping the weighted chains of [1], Proposition 3.5, by their first nonempty flat; the sum includes $F=E$.

(3)

For $r>0$, $\deg\underline H_M=r-1$, $\underline H_M(0)=1$, and $t^{r-1}\underline H_M(t^{-1})=\underline H_M(t)$ [1], Section 3.1.

(4)

For a simple matroid of rank at least two, $[t]\underline H_M(t)=|L(M)|-|E|-1$. In the degree-one presentation, the $|L(M)|-2$ generators have $|E|-1$ independent linear relations.

Comments

(5)

Let $E$ be the ground set, $L(M)$ the lattice of flats, and $r=\operatorname{rk}M$. Equivalently, $A^*(M)$ is generated over $\mathbb Q$ by $x_F$ for nonempty proper flats $F$, with $x_Fx_G=0$ for incomparable flats and with $\sum_{F\ni e}x_F$ independent of $e\in E$ [1], Definition 3.1. This is the ordinary Chow ring; the augmented ring and the ring for the minimal building set are different objects.

(6)

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}$, where $\mu$ is the Möbius function. For positive rank write $\bar\chi_M(t)=\chi_M(t)/(t-1)$. The empty matroid has $\underline H=1$. Contractions can have parallel elements; their actual flat lattices are used, and looped inputs are outside the domain.

(7)

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 5.2. Fano, NonFano, Pappus, NonPappus, Vamos, R10, TicTacToe and K5dual name the exact Sage catalogue objects [2]; K5dual is the matroid dual $M^*(K_5)$.

(8)

The variable $t$ records algebraic grading, so cohomological degree $2i$ contributes $t^i$ in a geometric realization. The coefficients are nonnegative, palindromic and unimodal [1], Section 3.1.

Programs

(P1)

Sage

# Place the attached generate.py in the working directory.
from generate import MatroidChow, uniform_chow, braid_chow
uniform_chow(8, 12)
braid_chow(8)

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

References

[1]

Luis Ferroni, Jacob P. Matherne, Matthew Stevens and Lorenzo Vecchi, Hilbert–Poincaré series of matroid Chow rings and intersection cohomology, Advances in Mathematics 449 (2024), 109733. (arXiv) (doi)

Links

[2]

SageMath: database of matroids

Similar tables

Characteristic polynomials of matroids — holds $\chi_M(t)$, whose reduced form on restrictions appears 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 circuits and compare generic dependence across ranks; the braid family supplies contrasting partition lattices. 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 favor breadth before further depth, keeping independent full-lattice checks manageable: the named objects have at most ten elements and $K(8)$ has $4140$ flats. They do not claim completeness over all matroids of any rank or size)

How they were obtained:

All 37 entries are exact polynomials in $\mathbb Z[t]$. The generator uses (2), grouping uniform flats by size and braid flats by block count, and retaining the actual flat lattices for the named objects.

The separate checks.py computes (1), independently enumerating partitions for braid restrictions and all ground-set subsets for the named objects. Known-answer controls precede full-coefficient agreement checks on all 37 values. All 24 uniform cases also agree with the derangement formula of [1], Theorem 3.21, using explicitly counted permutations. Degree, endpoint coefficients, positivity, symmetry, unimodality and (4) are checked on every entry. The standard dry run reports a longest entry of 79 characters and about 3 KB of entries. The attached argument-selection.md records the finite coverage and its rationale.