Matroids
CharacteristicPolynomial
construct characteristic polynomial
Calling Sequence
Parameters
Description
Examples
References
CharacteristicPolynomial(M, k)
M
-
Matroid
k
algebraic value
The characteristic polynomial of a matroid is a polynomial pk in one variable.
It is an evaluation of the Tutte polynomial Tx,y of that matroid, namely, pk=−1rankMT1−k,0.
Consequently, it respects the operations of deletion and contraction in the same way as the Tutte polynomial.
When applied to a graphic matroid MG associated to a graph G, the characteristic polynomial of MG is related to the chromatic polynomial of G. Namely, the characteristic polynomial of MG is kc (where c is the number of connected components of G) times the chromatic polynomial of G.
withMatroids:
withGraphTheory:
Construct the chromatic polynomial of a graph
G≔Grapha,x,a,y,b,x,b,y,c,x,c,y
G≔Graph 1: an undirected graph with 5 vertices and 6 edge(s)
Chrome≔ChromaticPolynomialG,k
Chrome≔kk−1k3−5k2+10k−7
Compare to the characteristic polynomial of the matroid constructed from the graph
M≔MatroidG
M≔thⅇ graphⅈc matroⅈⅆ on thⅇ graph:PLOT...
C≔Matroids:-CharacteristicPolynomialM,k
C≔k4−6k3+15k2−17k+7
expandChrome−kC
0
James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.
See Also
Matroids[Contraction]
Matroids[Deletion]
Matroids[TuttePolynomial]
Download Help Document