NumberDB$^\beta$ Advanced search Tags Tables Help Login
Characteristic polynomials of matroids
edit · history · discussion · files · long url · combinatorics polynomial
Polynomials
$M$ 
$\chi_M(q)$
$U_{2,2}$:
q^2 - 2*q + 1
$U_{2,3}$:
q^2 - 3*q + 2
$U_{2,4}$:
q^2 - 4*q + 3
$U_{2,5}$:
q^2 - 5*q + 4
$U_{2,6}$:
q^2 - 6*q + 5
$U_{2,7}$:
q^2 - 7*q + 6
$U_{2,8}$:
q^2 - 8*q + 7
$U_{2,9}$:
q^2 - 9*q + 8
$U_{2,10}$:
q^2 - 10*q + 9
$U_{2,11}$:
q^2 - 11*q + 10
$U_{3,3}$:
q^3 - 3*q^2 + 3*q - 1
$U_{3,4}$:
q^3 - 4*q^2 + 6*q - 3
$U_{3,5}$:
q^3 - 5*q^2 + 10*q - 6
$U_{3,6}$:
q^3 - 6*q^2 + 15*q - 10
P6:
q^3 - 6*q^2 + 14*q - 9
Q6:
q^3 - 6*q^2 + 13*q - 8
R6:
q^3 - 6*q^2 + 13*q - 8
Whirl3:
q^3 - 6*q^2 + 12*q - 7
$U_{3,7}$:
q^3 - 7*q^2 + 21*q - 15
Fano:
q^3 - 7*q^2 + 14*q - 8
NonFano:
q^3 - 7*q^2 + 15*q - 9
O7:
q^3 - 7*q^2 + 15*q - 9
P7:
q^3 - 7*q^2 + 16*q - 10
RelaxedNonFano:
q^3 - 7*q^2 + 16*q - 10
TippedFree3spike:
q^3 - 7*q^2 + 18*q - 12
$U_{3,8}$:
q^3 - 8*q^2 + 28*q - 21
AG23minus:
q^3 - 8*q^2 + 20*q - 13
$U_{3,9}$:
q^3 - 9*q^2 + 36*q - 28
A9:
q^3 - 9*q^2 + 25*q - 17
AG23:
q^3 - 9*q^2 + 24*q - 16
BB9:
q^3 - 9*q^2 + 25*q - 17
FN9:
q^3 - 9*q^2 + 26*q - 18
NonPappus:
q^3 - 9*q^2 + 28*q - 20
Pappus:
q^3 - 9*q^2 + 27*q - 19
R9:
q^3 - 9*q^2 + 23*q - 15
TernaryDowling3:
q^3 - 9*q^2 + 23*q - 15
$U_{3,10}$:
q^3 - 10*q^2 + 45*q - 36
NonDesargues:
q^3 - 10*q^2 + 36*q - 27
$U_{3,11}$:
q^3 - 11*q^2 + 55*q - 45
BetsyRoss:
q^3 - 11*q^2 + 35*q - 25
PG23:
q^3 - 13*q^2 + 39*q - 27
$U_{4,4}$:
q^4 - 4*q^3 + 6*q^2 - 4*q + 1
$U_{4,5}$:
q^4 - 5*q^3 + 10*q^2 - 10*q + 4
$U_{4,6}$:
q^4 - 6*q^3 + 15*q^2 - 20*q + 10
$U_{4,7}$:
q^4 - 7*q^3 + 21*q^2 - 35*q + 20
FanoDual:
q^4 - 7*q^3 + 21*q^2 - 28*q + 13
NonFanoDual:
q^4 - 7*q^3 + 21*q^2 - 29*q + 14
$U_{4,8}$:
q^4 - 8*q^3 + 28*q^2 - 56*q + 35
AG23minusDY:
q^4 - 8*q^3 + 27*q^2 - 42*q + 22
AG32:
q^4 - 8*q^3 + 28*q^2 - 42*q + 21
AG32prime:
q^4 - 8*q^3 + 28*q^2 - 43*q + 22
F8:
q^4 - 8*q^3 + 28*q^2 - 44*q + 23
J:
q^4 - 8*q^3 + 25*q^2 - 36*q + 18
KP8:
q^4 - 8*q^3 + 28*q^2 - 47*q + 26
L8:
q^4 - 8*q^3 + 28*q^2 - 48*q + 27
LP8:
q^4 - 8*q^3 + 28*q^2 - 47*q + 26
NonVamos:
q^4 - 8*q^3 + 28*q^2 - 50*q + 29
NotP8:
q^4 - 8*q^3 + 28*q^2 - 45*q + 24
P8:
q^4 - 8*q^3 + 28*q^2 - 46*q + 25
P8p:
q^4 - 8*q^3 + 28*q^2 - 47*q + 26
P8pp:
q^4 - 8*q^3 + 28*q^2 - 48*q + 27
Q8:
q^4 - 8*q^3 + 28*q^2 - 45*q + 24
R8:
q^4 - 8*q^3 + 28*q^2 - 44*q + 23
S8:
q^4 - 8*q^3 + 25*q^2 - 34*q + 16
Sp8:
q^4 - 8*q^3 + 28*q^2 - 46*q + 25
Sp8pp:
q^4 - 8*q^3 + 28*q^2 - 48*q + 27
T8:
q^4 - 8*q^3 + 28*q^2 - 45*q + 24
TQ8:
q^4 - 8*q^3 + 28*q^2 - 48*q + 27
Vamos:
q^4 - 8*q^3 + 28*q^2 - 51*q + 30
WQ8:
q^4 - 8*q^3 + 28*q^2 - 48*q + 27
Whirl4:
q^4 - 8*q^3 + 24*q^2 - 32*q + 15
$U_{4,9}$:
q^4 - 9*q^3 + 36*q^2 - 84*q + 56
Block_9_4:
q^4 - 9*q^3 + 36*q^2 - 66*q + 38
FX9:
q^4 - 9*q^3 + 36*q^2 - 68*q + 40
K33dual:
q^4 - 9*q^3 + 30*q^2 - 42*q + 20
KQ9:
q^4 - 9*q^3 + 36*q^2 - 68*q + 40
KR9:
q^4 - 9*q^3 + 34*q^2 - 60*q + 34
M8591:
q^4 - 9*q^3 + 33*q^2 - 55*q + 30
P9:
q^4 - 9*q^3 + 30*q^2 - 42*q + 20
PP9:
q^4 - 9*q^3 + 34*q^2 - 60*q + 34
R9A:
q^4 - 9*q^3 + 36*q^2 - 71*q + 43
R9B:
q^4 - 9*q^3 + 36*q^2 - 71*q + 43
TQ9:
q^4 - 9*q^3 + 34*q^2 - 61*q + 35
TQ9p:
q^4 - 9*q^3 + 34*q^2 - 60*q + 34
$U_{4,10}$:
q^4 - 10*q^3 + 45*q^2 - 120*q + 84
D10:
q^4 - 10*q^3 + 41*q^2 - 77*q + 45
$U_{4,11}$:
q^4 - 11*q^3 + 55*q^2 - 165*q + 120
$U_{5,5}$:
q^5 - 5*q^4 + 10*q^3 - 10*q^2 + 5*q - 1
$U_{5,6}$:
q^5 - 6*q^4 + 15*q^3 - 20*q^2 + 15*q - 5
$U_{5,7}$:
q^5 - 7*q^4 + 21*q^3 - 35*q^2 + 35*q - 15
$U_{5,8}$:
q^5 - 8*q^4 + 28*q^3 - 56*q^2 + 70*q - 35
$U_{5,9}$:
q^5 - 9*q^4 + 36*q^3 - 84*q^2 + 126*q - 70
BB9gDY:
q^5 - 9*q^4 + 36*q^3 - 80*q^2 + 97*q - 45
TicTacToe:
q^5 - 9*q^4 + 36*q^3 - 84*q^2 + 118*q - 62
$U_{5,10}$:
q^5 - 10*q^4 + 45*q^3 - 120*q^2 + 210*q - 126
Block_10_5:
q^5 - 10*q^4 + 45*q^3 - 120*q^2 + 174*q - 90
FF10:
q^5 - 10*q^4 + 45*q^3 - 111*q^2 + 144*q - 69
FK10:
q^5 - 10*q^4 + 45*q^3 - 113*q^2 + 152*q - 75
FP10:
q^5 - 10*q^4 + 45*q^3 - 112*q^2 + 148*q - 72
FT10:
q^5 - 10*q^4 + 45*q^3 - 113*q^2 + 152*q - 75
FU10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 155*q - 77
FY10:
q^5 - 10*q^4 + 45*q^3 - 113*q^2 + 153*q - 76
FZ10:
q^5 - 10*q^4 + 45*q^3 - 112*q^2 + 149*q - 73
GK10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 155*q - 77
GP10:
q^5 - 10*q^4 + 45*q^3 - 113*q^2 + 152*q - 75
KF10:
q^5 - 10*q^4 + 45*q^3 - 113*q^2 + 152*q - 75
KT10:
q^5 - 10*q^4 + 45*q^3 - 113*q^2 + 153*q - 76
N1:
q^5 - 10*q^4 + 45*q^3 - 111*q^2 + 142*q - 67
PK10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 157*q - 79
PP10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 156*q - 78
Q10:
q^5 - 10*q^4 + 45*q^3 - 110*q^2 + 139*q - 65
R10:
q^5 - 10*q^4 + 45*q^3 - 105*q^2 + 120*q - 51
TK10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 156*q - 78
TQ10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 158*q - 80
TU10:
q^5 - 10*q^4 + 45*q^3 - 115*q^2 + 160*q - 81
UG10:
q^5 - 10*q^4 + 45*q^3 - 115*q^2 + 160*q - 81
UK10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 156*q - 78
UQ10:
q^5 - 10*q^4 + 45*q^3 - 112*q^2 + 150*q - 74
UT10:
q^5 - 10*q^4 + 45*q^3 - 114*q^2 + 155*q - 77
$U_{5,11}$:
q^5 - 11*q^4 + 55*q^3 - 165*q^2 + 330*q - 210
FA11:
q^5 - 11*q^4 + 54*q^3 - 143*q^2 + 195*q - 96
FS12:
q^5 - 12*q^4 + 66*q^3 - 196*q^2 + 290*q - 149
$U_{6,6}$:
q^6 - 6*q^5 + 15*q^4 - 20*q^3 + 15*q^2 - 6*q + 1
$U_{6,7}$:
q^6 - 7*q^5 + 21*q^4 - 35*q^3 + 35*q^2 - 21*q + 6
$U_{6,8}$:
q^6 - 8*q^5 + 28*q^4 - 56*q^3 + 70*q^2 - 56*q + 21
$U_{6,9}$:
q^6 - 9*q^5 + 36*q^4 - 84*q^3 + 126*q^2 - 126*q + 56
$U_{6,10}$:
q^6 - 10*q^5 + 45*q^4 - 120*q^3 + 210*q^2 - 252*q + 126
K5dual:
q^6 - 10*q^5 + 45*q^4 - 115*q^3 + 175*q^2 - 147*q + 51
$U_{6,11}$:
q^6 - 11*q^5 + 55*q^4 - 165*q^3 + 330*q^2 - 462*q + 252
NestOfTwistedCubes:
q^6 - 12*q^5 + 66*q^4 - 205*q^3 + 370*q^2 - 357*q + 137
R12:
q^6 - 12*q^5 + 64*q^4 - 191*q^3 + 329*q^2 - 301*q + 110
T12:
q^6 - 12*q^5 + 66*q^4 - 205*q^3 + 370*q^2 - 355*q + 135
$U_{7,7}$:
q^7 - 7*q^6 + 21*q^5 - 35*q^4 + 35*q^3 - 21*q^2 + 7*q - 1
$U_{7,8}$:
q^7 - 8*q^6 + 28*q^5 - 56*q^4 + 70*q^3 - 56*q^2 + 28*q - 7
$U_{7,9}$:
q^7 - 9*q^6 + 36*q^5 - 84*q^4 + 126*q^3 - 126*q^2 + 84*q - 28
$U_{7,10}$:
q^7 - 10*q^6 + 45*q^5 - 120*q^4 + 210*q^3 - 252*q^2 + 210*q - 84
$U_{7,11}$:
q^7 - 11*q^6 + 55*q^5 - 165*q^4 + 330*q^3 - 462*q^2 + 462*q - 210
$U_{8,8}$:
q^8 - 8*q^7 + 28*q^6 - 56*q^5 + 70*q^4 - 56*q^3 + 28*q^2 - 8*q + 1
$U_{8,9}$:
q^8 - 9*q^7 + 36*q^6 - 84*q^5 + 126*q^4 - 126*q^3 + 84*q^2 - 36*q + 8
$U_{8,10}$:
q^8 - 10*q^7 + 45*q^6 - 120*q^5 + 210*q^4 - 252*q^3 + 210*q^2 - 120*q + 36
$U_{8,11}$:
q^8 - 11*q^7 + 55*q^6 - 165*q^5 + 330*q^4 - 462*q^3 + 462*q^2 - 330*q + 120
$U_{9,9}$:
q^9 - 9*q^8 + 36*q^7 - 84*q^6 + 126*q^5 - 126*q^4 + 84*q^3 - 36*q^2 + 9*q - 1
$U_{9,10}$:
q^9 - 10*q^8 + 45*q^7 - 120*q^6 + 210*q^5 - 252*q^4 + 210*q^3 - 120*q^2 + 45*q - 9
$U_{9,11}$:
q^9 - 11*q^8 + 55*q^7 - 165*q^6 + 330*q^5 - 462*q^4 + 462*q^3 - 330*q^2 + 165*q - 45
$U_{10,10}$:
q^10 - 10*q^9 + 45*q^8 - 120*q^7 + 210*q^6 - 252*q^5 + 210*q^4 - 120*q^3 + 45*q^2 - 10*q + 1
$U_{10,11}$:
q^10 - 11*q^9 + 55*q^8 - 165*q^7 + 330*q^6 - 462*q^5 + 462*q^4 - 330*q^3 + 165*q^2 - 55*q + 10
$U_{11,11}$:
q^11 - 11*q^10 + 55*q^9 - 165*q^8 + 330*q^7 - 462*q^6 + 462*q^5 - 330*q^4 + 165*q^3 - 55*q^2 + 11*q - 1
Definition
For a finite matroid $M$ on ground set $E$ with rank function $r$, this table stores the characteristic polynomial $\chi_M(q)=\sum_{S\subseteq E}(-1)^{|S|}q^{r(E)-r(S)}$ [2].
Parameters
$M$
—   matroid (a simple uniform matroid $U_{r,n}$, or a simple matroid named as sage.matroids.catalog names it)
Formulas
(1)
If $T_M(x,y)$ is the Tutte polynomial of a rank $r(M)$ matroid, then $\chi_M(q)=(-1)^{r(M)}T_M(1-q,0)$. For cycle matroids of connected graphs, $T_M(x,y)$ is stored in Tutte polynomials of connected graphs.
(2)
For $1\leq r\leq n$, $\chi_{U_{r,n}}(q)=\sum_{k=0}^{r-1}(-1)^k\binom{n}{k}q^{r-k} +(-1)^r\binom{n-1}{r-1}$.
(3)
If $G$ has $c$ connected components and $M(G)$ is its cycle matroid, then $P_G(q)=q^c\chi_{M(G)}(q)$, where $P_G(q)$ is the chromatic polynomial of $G$.
Comments
(4)
Uniform matroids are written U(r,n) for $U_{r,n}$. The named matroids use the constructors in Sage's matroid catalog [3], which includes Oxley's appendix [1]. The catalog's uniform aliases U24, U25, U35, and U36 are represented here by U(2,4), U(2,5), U(3,5), and U(3,6).
(5)
A loop makes $\chi_M(q)=0$. For a loopless matroid, parallel elements do not change the lattice of flats, so $\chi_M(q)$ is the characteristic polynomial of the simplification. This table stores simple matroids.
(6)
Equivalently, for a loopless matroid, $\chi_M(q)=\sum_{F\in L(M)}\mu(\varnothing,F)q^{r(E)-r(F)}$, where $L(M)$ is the lattice of flats and $\mu$ is its Möbius function [4].
(7)
The variable is $q$. Sage prints the same polynomial in a variable called l unless another variable is supplied.
(8)
The coefficients are the Whitney numbers of the first kind: $\chi_M(q)=\sum_{i=0}^{r(E)}w_i(M)q^{r(E)-i}$, where $w_i(M)=\sum_{F\in L(M),\,r(F)=i}\mu(\varnothing,F)$.
Programs
(P1)
Sage
from sage.matroids.catalog import Fano
from sage.matroids.matroids_catalog import Uniform
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

R = PolynomialRing(ZZ, "q")
q = R.gen()
R(Fano().characteristic_polynomial(q))
R(Uniform(3, 12).characteristic_polynomial(q))
References
[1]
James Oxley, Matroid Theory, second ed., Oxford Graduate Texts in Mathematics 21, Oxford University Press, Oxford, 2011. (doi)
Links
Similar tables
Chromatic polynomials of connected graphs —   holds $P_G(q)$ for connected graphs on at most seven vertices; formula (3) gives $\chi_{M(G)}(q)$
Tutte polynomials of connected graphs —   holds $T_G(x,y)$ for connected graphs on at most seven vertices; $T_G(x,y)=T_{M(G)}(x,y)$, so formula (1) gives $\chi_{M(G)}(q)$
Ehrhart polynomials of the hypersimplices —   holds the Ehrhart polynomial of the hypersimplex $\Delta(k,n)$, the matroid polytope of the uniform matroid $U_{k,n}$ whose characteristic polynomial is stored here
Ehrhart $h^*$-polynomials of the hypersimplices —   holds the Ehrhart $h^*$-polynomial of the hypersimplex $\Delta(k,n)$, the matroid polytope of the uniform matroid $U_{k,n}$
Data properties
Entries are of type: integral polynomial
How well the digits are known: exact
Table is complete: no (it holds every simple uniform matroid $U_{r,n}$ with $2\leq r\leq n\leq11$, and every simple non-graphic Sage catalog matroid whose lattice-of-flats computation stayed within the build cutoff of $600$ flats; graphic catalog matroids are omitted because $P_G(q)=q^c\chi_{M(G)}(q)$ puts their values in the graph-indexed chromatic-polynomial table, and catalog aliases for uniform matroids are listed as U(r,n))
How they were obtained:

Every entry is an exact polynomial with integer coefficients. The generator computes Sage's characteristic polynomial for each finite matroid and coerces it to $\mathbb{Z}[q]$.

more

Before the values were written, the build checked exactness, compared every uniform row with formula (2), checked every row against an independent computation from the Möbius function of the lattice of flats, and, as a control on matroids this table does not hold, computed $\chi_{M(K_4)}$ and $\chi_{M(K_5)}$ and checked them against formula (3).



API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.