[Math] Meaning of the characteristic polynomial of a matroid

combinatoricscomputer sciencediscrete mathematicsmatricesmatroids

From wikipedia

The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be
$$
p_M(\lambda) := \sum_{S \subseteq E} (-1)^{|S|}\lambda^{r(M)-r(S)}, $$

$p_M$ is defined in terms of the rank function $r$ of the matroid $M$. Questions:

  • For each $\lambda$ value, what does $p_M(\lambda)$ represent?
  • what does $\arg\min_\lambda p_M(\lambda)$ mean?
  • what is the purpose of introducing the characteristic polynomial of a matroid?

Compared to matrices, a characteristic polynomial $det (\lambda I – A)$ of a square matrix $A$, at each value $\lambda$, represents how far the matrix $A$ is away from the identity matrix scaled by $\lambda$ in terms of its determinant. It is the smallest when $\lambda$ is an eigenvalue of the matrix $A$.

Thanks.

Best Answer

Let $M$ be a matroid on ground set $E$, we have $$\rho_M(\lambda) = \sum_{S \subseteq E}(-1)^{|S|}\lambda^{r(M) - r(S)}$$ where notice we use the corank as our exponent instead of the rank. If our matroid has no loops then $r(\varnothing) = 0$ and $\varnothing$ is the only set of rank zero and we see that $\rho_M$ is monic with degree $r(M)$. (This property is shared by the characteristic polynomial of a graded poset; see the Mobius function definite of $\rho_M$ in the Wikipedia article you have linked to). We can go further in the case of no loop every singleton subset has rank one so the coefficient of $\lambda^{r(M)-1}$ is $-|E|$. Next notice any subset of size two has rank two unless we have a two element circuit. Simple matroids have no one or two element circuits. So, for a simple matroid the coefficient of $\lambda^{r(M)-2}$ is $\binom{|E|}{2}$. More generally the coefficients have an interpretation in terms of "no broken circuit" (NBC) sets. Whitney has a theorem about the coefficients of the chromatic polynomial of a graph (which is a special case of the characteristic polynomial of a matroid up to a factor of some power of $\lambda$) in terms of NBC sets. Also Rota had an NBC theorem of matroids/geometric lattices (here note geometric lattices are exactly lattices of flats for matroids).

Also in the Wikipedia article you linked to it discusses the the Tutte polynomial of a matroid. Notice the characteristic polynomial is just an evaluation of the Tutte polynomial. That is the Tutte polynomials in a more general two variable polynomial with lot of nice properties. Let $T_M(x,y)$ be the Tutte polynomial of a matroid. Then $T_{M^*}(x,y) = T_M(y,x)$ thus duality in the Tutte polynomial is just exchanging variable. Also $T_{G}(x,y) = T_{M_G}(x,y)$ so again matroid polynomial generalizes the graph polynomial. The Tutte polynomial behaves well with respect duality as we already saw and also there is a deletion contraction rule. Finally the Tutte polynomial can be used to count things. For example $T_G(1,1)$ is the number of spanning forest in a graph and $T_M(1,1)$ is the number of bases of your matroid. See Theorem 1.8 of this paper for more evaluations of the Tutte polynomial.

So, to directly answer some of your question. I do not know what specific evaluations $\rho_M(\lambda)$ are in the non-graphic case. I think the main motivation for the matroid polynomials are to generalize what we know for graphs.

Related Question