Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I'm not sure your interpretation of the characteristic polynomial of a matrix, in the last paragraph, is really all that profound. What do you mean by "how close"? –  Jack M Jul 4 at 20:09
    
Thanks. I mean "how far away". –  Tim Jul 4 at 20:57
    
Do not look at the characteristic polynomial of a matrix to try to understand the characteristic polynomial of a matroid. The proper polynomials to look at would be the Tutte polynomial of a graph and it's evaluations (i.e. the chromatic polynomial) and the characteristic polynomial of a graded poset. –  JMac31 Jul 4 at 21:41
    
@JMac31: thanks. What is the usage of characteristic polynomial of a matroid? WHat does it mean? –  Tim Jul 4 at 23:28

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.