Editing Matroid (section)

==Polynomial invariants==
There are two especially significant polynomials associated to a finite matroid ''M'' on the ground set ''E''.  Each is a ''matroid invariant'', which means that isomorphic matroids have the same polynomial.

===Characteristic polynomial===
The ''[[characteristic polynomial]]'' of ''M'' – sometimes called the ''chromatic polynomial'',<ref name=Wh87127/> although it does not count colorings – is defined to be
:<math>p_M(\lambda) := \sum_{S \subseteq E} (-1)^{|S|}\lambda^{r(E)-r(S)},</math>
or equivalently (as long as the empty set is closed in ''M'') as
:<math>p_M(\lambda) := \sum_{A} \mu(\emptyset,A) \lambda^{r(E)-r(A)} </math>,
where μ denotes the [[Möbius function (combinatorics)|Möbius function]] of the [[geometric lattice]] of the matroid and the sum is taken over all the flats A of the matroid.<ref name=Wh87120>{{harvp|White|1987|p=120}}</ref>

* When ''M'' is the cycle matroid ''M''(''G'') of a graph ''G'', the characteristic polynomial is a slight transformation of the [[chromatic polynomial]], which is given by χ<sub>''G''</sub>&nbsp;(λ) = λ<sup>c</sup>''p''<sub>''M''(''G'')</sub>&nbsp;(λ), where ''c'' is the number of connected components of ''G''.

* When ''M'' is the bond matroid ''M''*(''G'') of a graph ''G'', the characteristic polynomial equals the [[Tutte polynomial#Flow polynomial|flow polynomial]] of ''G''.

* When ''M'' is the matroid ''M''(''A'') of an [[Arrangement of hyperplanes|arrangement]] ''A'' of linear hyperplanes in {{math|ℝ{{sup|n}}}} (or ''F''<sup>''n''</sup> where ''F'' is any field), the characteristic polynomial of the arrangement is given by ''p''<sub>''A''</sub>&nbsp;(λ) = λ<sup>''n''&minus;''r''(''M'')</sup>''p''<sub>''M''</sub>&nbsp;(λ).

====Beta invariant====
The ''beta invariant'' of a matroid, introduced by [[Henry Crapo (mathematician)|Crapo]] (1967), may be expressed in terms of the characteristic polynomial <math> p </math> as an evaluation of the derivative<ref name=Wh87123>{{harvp|White|1987|p=123}}</ref>
:<math> \beta(M) = (-1)^{r(M)-1} p_M'(1) </math>
or directly as<ref name=Wh87124>{{harvp|White|1987|p=124}}</ref>
:<math> \beta(M) = (-1)^{r(M)} \sum_{X \subseteq E} (-1)^{|X|} r(X)</math>.
The beta invariant is non-negative, and is zero if and only if <math> M </math> is disconnected, or empty, or a loop.  Otherwise it depends only on the lattice of flats of <math> M</math>. If <math> M </math> has no loops and coloops then <math> \beta( M ) = \beta( M^* )</math>.<ref name=Wh87124/>

===Whitney numbers===
The ''Whitney numbers of the first kind'' of <math> M </math> are the coefficients of the powers of <math>\lambda</math> in the characteristic polynomial. Specifically, the <math>i</math>th Whitney number <math> w_i(M) </math> is the coefficient of <math>\lambda^{r(M)-i}</math> and is the sum of Möbius function values:
:<math>w_i(M) = \sum \{ \mu(\emptyset,A): r(A) = i \},</math>
summed over flats of the right rank. These numbers alternate in sign, so that <math>(-1)^i w_i(M) > 0</math> for <math>0 \leq i \leq r(M)</math>.

The ''Whitney numbers of the second kind'' of <math> M </math> are the numbers of flats of each rank. That is, <math> W_i(M) </math> is the number of rank&nbsp;<math>i</math> flats.

The Whitney numbers of both kinds generalize the [[Stirling number]]s of the first and second kind, which are the Whitney numbers of the cycle matroid of the [[complete graph]], and equivalently of the [[Partition of a set#Refinement_of_partitions|partition lattice]]. They were named after [[Hassler Whitney]], the (co)founder of matroid theory, by [[Gian-Carlo Rota]]. The name has been extended to the similar numbers for finite ranked [[partially ordered set]]s.

===Tutte polynomial===
The ''[[Tutte polynomial]]'' of a matroid, <math> T_M(x, y)</math>, generalizes the characteristic polynomial to two variables. This gives it more combinatorial interpretations, and also gives it the duality property
:<math> T_{M^*}(x,y) = T_M(y,x)</math>,
which implies a number of dualities between properties of <math> M </math> and properties of <math> M^*</math>. One definition of the Tutte polynomial is
:<math> T_M(x,y) = \sum_{S \subseteq E} (x-1)^{ r(M) - r(S) }\ (y-1)^{ |S| - r(S) }</math>.

This expresses the Tutte polynomial as an evaluation of the ''co-rank-nullity'' or ''rank generating polynomial'',<ref name=Wh87126>{{harvp|White|1987|p=126}}</ref>
:<math> R_M(u,v) = \sum_{S\subseteq E} u^{r(M)-r(S)}v^{|S| - r(S)}</math>.
From this definition it is easy to see that the characteristic polynomial is, up to a simple factor, an evaluation of <math> T_M</math>, specifically, 
:<math> p_M(\lambda) = (-1)^{r(M)} T_M(1-\lambda,0)</math>.

Another definition is in terms of internal and external activities and a sum over bases, reflecting the fact that <math> T(1,1) </math> is the number of bases.<ref name=Wh92188>{{harvp|White|1992b|p=188}}</ref> This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.

There is a further definition in terms of recursion by deletion and contraction.<ref name=Wh86260>{{harvp|White|1986|p=260}}</ref> The deletion-contraction identity is
:<math> F(M) = F( M - e ) + F( M / e ) </math>
when <math> e </math> is neither a loop nor a coloop.
An invariant of matroids (i.e., a function that takes the same value on isomorphic matroids) satisfying this recursion and the multiplicative condition
:<math> F(M \oplus M') = F(M) F(M')</math>
is said to be a ''Tutte-Grothendieck invariant''.<ref name=Wh87126/> The Tutte polynomial is the most general such invariant; that is, the Tutte polynomial is a Tutte-Grothendieck invariant and every such invariant is an evaluation of the Tutte polynomial.<ref name=Wh87127>{{harvp|White|1987|p=127}}</ref>

The [[Tutte polynomial]] <math> T_G </math> of a graph is the Tutte polynomial <math> T_{ M(G) } </math> of its cycle matroid.