CharacteristicPolynomial - Maple Help

Home : Support : Online Help : Mathematics : Algebra : Polynomials : Matroids : CharacteristicPolynomial

Matroids

 CharacteristicPolynomial
 construct characteristic polynomial

 Calling Sequence CharacteristicPolynomial(M, k)

Parameters

 M - k - algebraic value

Description

 • The characteristic polynomial of a matroid is a polynomial $p\left(k\right)$ in one variable.
 • It is an evaluation of the Tutte polynomial $T\left(x,y\right)$ of that matroid, namely, $p\left(k\right)={\left(-1\right)}^{\mathrm{rank}\left(M\right)}T\left(1-k,0\right)$.
 • Consequently, it respects the operations of deletion and contraction in the same way as the Tutte polynomial.
 • When applied to a graphic matroid $M\left(G\right)$ associated to a graph $G$, the characteristic polynomial of $M\left(G\right)$ is related to the chromatic polynomial of $G$. Namely, the characteristic polynomial of $M\left(G\right)$ is ${k}^{c}$ (where $c$ is the number of connected components of $G$) times the chromatic polynomial of $G$.

Examples

 > $\mathrm{with}\left(\mathrm{Matroids}\right):$
 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$

Construct the chromatic polynomial of a graph

 > $G≔\mathrm{Graph}\left(\left\{\left\{a,x\right\},\left\{a,y\right\},\left\{b,x\right\},\left\{b,y\right\},\left\{c,x\right\},\left\{c,y\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 5 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{Chrome}≔\mathrm{ChromaticPolynomial}\left(G,k\right)$
 ${\mathrm{Chrome}}{≔}{k}{}\left({k}{-}{1}\right){}\left({{k}}^{{3}}{-}{5}{}{{k}}^{{2}}{+}{10}{}{k}{-}{7}\right)$ (2)

Compare to the characteristic polynomial of the matroid constructed from the graph

 > $M≔\mathrm{Matroid}\left(G\right)$
 ${M}{≔}⟨\begin{array}{c}{thⅇ graphic matroiⅆ on thⅇ graph:}\\ {\mathrm{PLOT}}{}\left({\mathrm{...}}\right)\end{array}⟩$ (3)
 > $C≔\mathrm{Matroids}:-\mathrm{CharacteristicPolynomial}\left(M,k\right)$
 ${C}{≔}{{k}}^{{4}}{-}{6}{}{{k}}^{{3}}{+}{15}{}{{k}}^{{2}}{-}{17}{}{k}{+}{7}$ (4)
 > $\mathrm{expand}\left(\mathrm{Chrome}-kC\right)$
 ${0}$ (5)

References

 James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.