Augmented Chow polynomials of matroids

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

Polynomials

$M$

$H_M(t)$

$U_{3,4}$:

t^3 + 11*t^2 + 11*t + 1

$U_{3,5}$:

t^3 + 16*t^2 + 16*t + 1

$M(K_{4})$:

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

$U_{3,6}$:

t^3 + 22*t^2 + 22*t + 1

Fano:

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

NonFano:

t^3 + 17*t^2 + 17*t + 1

$U_{3,7}$:

t^3 + 29*t^2 + 29*t + 1

NonPappus:

t^3 + 30*t^2 + 30*t + 1

Pappus:

t^3 + 28*t^2 + 28*t + 1

$U_{4,5}$:

t^4 + 26*t^3 + 66*t^2 + 26*t + 1

$U_{4,6}$:

t^4 + 42*t^3 + 117*t^2 + 42*t + 1

$U_{4,7}$:

t^4 + 64*t^3 + 190*t^2 + 64*t + 1

$U_{4,8}$:

t^4 + 93*t^3 + 289*t^2 + 93*t + 1

Vámos:

t^4 + 78*t^3 + 234*t^2 + 78*t + 1

$M(K_{5})$:

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

$U_{5,6}$:

t^5 + 57*t^4 + 302*t^3 + 302*t^2 + 57*t + 1

$U_{5,7}$:

t^5 + 99*t^4 + 610*t^3 + 610*t^2 + 99*t + 1

$U_{5,8}$:

t^5 + 163*t^4 + 1115*t^3 + 1115*t^2 + 163*t + 1

TicTacToe:

t^5 + 224*t^4 + 1576*t^3 + 1576*t^2 + 224*t + 1

$U_{5,9}$:

t^5 + 256*t^4 + 1888*t^3 + 1888*t^2 + 256*t + 1

$R_{10}$:

t^5 + 161*t^4 + 986*t^3 + 986*t^2 + 161*t + 1

$M(K_{6})$:

t^5 + 202*t^4 + 1412*t^3 + 1412*t^2 + 202*t + 1

$U_{6,7}$:

t^6 + 120*t^5 + 1191*t^4 + 2416*t^3 + 1191*t^2 + 120*t + 1

$U_{6,8}$:

t^6 + 219*t^5 + 2641*t^4 + 5637*t^3 + 2641*t^2 + 219*t + 1

$U_{6,9}$:

t^6 + 382*t^5 + 5290*t^4 + 11674*t^3 + 5290*t^2 + 382*t + 1

$M^*(K_5)$:

t^6 + 313*t^5 + 3638*t^4 + 7628*t^3 + 3638*t^2 + 313*t + 1

$U_{6,10}$:

t^6 + 638*t^5 + 9773*t^4 + 22073*t^3 + 9773*t^2 + 638*t + 1

$M(K_{7})$:

t^6 + 876*t^5 + 13623*t^4 + 31018*t^3 + 13623*t^2 + 876*t + 1

$U_{7,8}$:

t^7 + 247*t^6 + 4293*t^5 + 15619*t^4 + 15619*t^3 + 4293*t^2 + 247*t + 1

$U_{7,9}$:

t^7 + 466*t^6 + 10204*t^5 + 40444*t^4 + 40444*t^3 + 10204*t^2 + 466*t + 1

$U_{7,10}$:

t^7 + 848*t^6 + 21995*t^5 + 92255*t^4 + 92255*t^3 + 21995*t^2 + 848*t + 1

$U_{7,11}$:

t^7 + 1486*t^6 + 43715*t^5 + 190730*t^4 + 190730*t^3 + 43715*t^2 + 1486*t + 1

$M(K_{8})$:

t^7 + 4139*t^6 + 135417*t^5 + 618242*t^4 + 618242*t^3 + 135417*t^2 + 4139*t + 1

$U_{8,9}$:

t^8 + 502*t^7 + 14608*t^6 + 88234*t^5 + 156190*t^4 + 88234*t^3 + 14608*t^2 + 502*t + 1

$U_{8,10}$:

t^8 + 968*t^7 + 36605*t^6 + 247397*t^5 + 452357*t^4 + 247397*t^3 + 36605*t^2 + 968*t + 1

$U_{8,11}$:

t^8 + 1816*t^7 + 83777*t^6 + 610556*t^5 + 1139876*t^4 + 610556*t^3 + 83777*t^2 + 1816*t + 1

$U_{8,12}$:

t^8 + 3302*t^7 + 177201*t^6 + 1361494*t^5 + 2578369*t^4 + 1361494*t^3 + 177201*t^2 + 3302*t + 1

Definition

For a finite simple matroid $M$, the augmented Chow polynomial $H_M(t)=\sum_{i\geq0}\dim_{\mathbb Q}\mathrm{CH}^i(M)t^i$ is the Hilbert–Poincaré series of its augmented Chow ring [1], Definition 3.2. Every divisor generator has degree one.

Parameters

$M$

— matroid (a finite simple matroid)

Formulas

(1)

With $\underline H_N(t)$ denoting the ordinary Chow polynomial, $H_M(t)=\sum_{F\in L(M)}t^{\operatorname{rk}F}\underline H_{M/F}(t)$ [1], Proposition 3.7. Equivalently, $H_M(t)=1+t\sum_{F\ne E}\underline H_{M/F}(t)$, by Remark 3.8.

(2)

For positive rank, $H_M(t)=-\sum_{\varnothing\ne F\in L(M)}\mu(\varnothing,F)(1+t+\cdots+t^{\operatorname{rk}F})H_{M/F}(t)$ [1], Theorem 3.14.

(3)

$H_{U_{r,n}}(t)=1+t\sum_{j=0}^{r-1}\binom nj A_j(t)(1+t+\cdots+t^{r-1-j})$, where $A_j(t)=\sum_{\sigma\in S_j}t^{\operatorname{des}\sigma}$, $\operatorname{des}\sigma$ counts descents and $A_0(t)=1$ [1], Theorem 3.21.

(4)

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

(5)

$[t]H_M(t)=|L(M)|-1$. Eliminating the variables $y_e$ in the augmented ring presentation leaves one independent degree-one generator for each proper flat.

Comments

(6)

Write $E$ for the ground set and $L(M)$ for the lattice of flats. The augmented ring is generated over $\mathbb Q$ by $x_F$ for all proper flats $F$, including $\varnothing$, and by $y_e$ for $e\in E$. Its relations are $y_e=\sum_{F\not\ni e}x_F$, $x_Fx_G=0$ for incomparable flats, and $y_ex_F=0$ when $e\notin F$ [1], Definition 3.2. This is distinct from the ordinary Chow ring with the maximal building set of all nonempty flats; a minimal building set gives a different construction.

(7)

Let $r=\operatorname{rk}M$ and let $\mu$ be the Möbius function of $L(M)$. Contraction $M/F$ corresponds to the upper interval $[F,E]$, whereas restriction $M|F$ corresponds to $[\varnothing,F]$. Empty minors have $H=1$. Contractions can have parallel elements, and their actual flat lattices determine the values. The parameter domain excludes looped inputs.

(8)

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

(9)

The variable $t$ records algebraic degree, 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

import numberdb.sage
from sage.rings.rational_field import QQ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.matroids import database_matroids as catalog

# Initialize Sage's multivariate polynomial implementation.
PolynomialRing(QQ, 2, 'x')
P = PolynomialRing(QQ, 't')
t = P.gen()

def augmented_chow(M):
    """Return H_M(t) for a finite simple matroid M."""
    if not M.is_simple():
        raise ValueError('M must be simple')
    A = M.chow_ring(QQ, True, 'fy')
    return sum((t**b.homogeneous_degree() for b in A.basis()), P.zero())

print(augmented_chow(catalog.Fano()))

(P2)

Sage

# Place the attached generate.py in the working directory.
from generate import MatroidAugmentedChow, uniform_augmented, braid_augmented
uniform_augmented(8, 12)
braid_augmented(8)

generator = MatroidAugmentedChow()
[(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

Chow polynomials of matroids — holds the ordinary Chow polynomials $\underline H_M(t)$, which determine $H_M(t)$ through their values on contractions in (1)

Z-polynomials of matroids — holds the Hilbert series of the matroid intersection cohomology modules, indexed by the same matroids

Characteristic polynomials of matroids — holds $\chi_M(t)$, whose constant term is $\mu(\varnothing,E)$; restrictions supply the Möbius coefficients in (2)

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 contributes contrasting partition lattices. The eight named objects are a noncanonical exploratory reference selection spanning finite geometry, representability contrasts, regular, paving and cographic structures. The selection is independent of numeral base and ground-set labels. These practical bounds favor breadth across these families before further depth; the named objects have at most ten elements and $K(8)$ has $4140$ flats. No completeness over all matroids of any rank or size is claimed)

How they were obtained:

All 37 values are exact polynomials in $\mathbb Z[t]$. The generator evaluates the weighted-chain formula of [1], Proposition 3.6, by dynamic programming on upper flat intervals, with symmetry reductions for uniform and braid matroids.

The separate checks.py uses (2) for the eight catalogue objects, constructing flats independently from all subset ranks, and permutation-cycle counts for the five braid objects. It checks all 24 uniform values using (3), with Eulerian coefficients counted directly from permutations. Ten complete polynomials also agree with published Table 1(b,d). Known-answer controls precede the comparisons. Degree, endpoint coefficients, nonnegativity, symmetry, unimodality and (5) are checked on every entry, as are both expressions in (1). The standard dry run measures a longest entry of 95 characters and about 3.4 KB of entries. The attached argument-selection.md records the coverage rationale, and numerical-evidence.md records the commands and results.