Proving the recurrence relation of the rank polynomial (or Tutte's) on a matroid.

Question

I'm reading through chapter 15 on Algebraic Graph Theory by Godsil and Royle.

The $\mathit{rank \ polynomial}$ for a matroid $M$ is defined as

$$R_M(x,y)=\sum_{A \subseteq\Omega} x^{rk(\Omega)-rk(A)}y^{|A|-rk(A)}, $$

where $rk(X)$ is the the rank function of a subset $X$ of the ground set $\Omega$ of the matroid $M$.

A $\mathit{loop}$ is defined as an element $e$ of the ground set such that $rk(e)=0$ and a $\mathit{coloop}$ is defined as an element $f$ of the amtroid such that $f$ is a loop in the dual matroid $M^*$. The dual matroid $M^*$ is defined as the matroid with the same ground set as $M$ and with rank function

$$ rk^*(A)= |A| +rk(\Omega \setminus A) - rk(\Omega). $$

There follows this theorem which I'm trying to prove:

Let $M$ be a matroid on $\Omega$ and let $e \in \Omega$. Then:

$$ R_M(x,y) = (1+y)R_{M \setminus e}(x,y), \ \ \mathrm{if \ e \ is \ a \ loop;}$$

$$ R_M(x,y) = (1+x)R_{M / e}(x,y), \ \ \mathrm{if \ e \ is \ a \ coloop;}$$

$$ R_M(x,y) = R_{M \setminus e}(x,y) + R_{M / e}(x,y), \ \ \mathrm{otherwise.} $$

I'm okay with the first statement:

\begin{align} R_M(x,y) &= \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A)}y^{|A|-rk(A)} + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A \cup e)}y^{|A \cup e|-rk(A \cup e)} \\ &= R_{M \setminus e} (x,y) + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A)}y^{|A|+1 -rk(A)} \\ &= R_{M \setminus e} (x,y) + yR_{M \setminus e} (x,y) \\ &= (1+y)R_{M \setminus e} (x,y). \end{align}

by observing that since $e$ is a loop it will not contribute to the rank of any subset.

I don't see the second statement.

First, I'll restate the definition of a contraction. Let $M$ be a matroid with ground set $\Omega$ and let $T \subset \Omega$. Define $ \rho$ on $\Omega \setminus T$ as $\rho(A)=rk(A \cup T)- rk(T)$. Then $M/T$ is the matroid with rank function $\rho$ defined on $\Omega \setminus T$.

Since $e$ is a coloop:

$$\rho(A)=rk(A \cup e)- rk(e)=rk(A) +rk(e)- rk(e)=rk(A)$$

As well, for loops and coloops, $M/e = M \setminus e$, so

\begin{align} R_M(x,y) &= \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A)}y^{|A|-rk(A)} + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A \cup e)}y^{|A \cup e|-rk(A \cup e)} \\ &= R_{M / e} (x,y) + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A \cup e)}y^{|A \cup e| -rk(A \cup e)} \\ &= R_{M / e} (x,y) + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A) -1}y^{|A|+1 -rk(A) -1}\\ &= (1+x^{-1})R_{M /e} (x,y) \\ &\neq (1+x)R_{M / e} (x,y). \end{align}

I understand the third statement for a graph matroid but it's not clear to me why for a general matroid $R_{M/e}$ accounts for all subsets that contain e.

Also, I'd appreciate some feedback regarding the statement of the question. Was it too detailed?

Answer 1

The trick to proving these results is to break up the defining sum of the Tutte polynomial into two sums: one over all sets that do not contain $e$ and the other for all sets that do.

$$R_{M}(x,y) = \sum_{e \notin A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}+ \sum_{e \in A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)} $$

When $e$ is a loop the rank function of $M-e$ is $r'(A) = r(A) = r(A \cup e)$. So $$ x^{r(\Omega) - r(A)}y^{|A|-r(A)} = \begin{cases} x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)} &\text{ if $e \notin A$} \\ x^{r'(\Omega-e) - r'(A-e)}y^{|A-e|+1-r'(A)}&\text{ if $e \in A$} \end{cases} $$ So we have \begin{align} R_{M}(x,y) &= \sum_{e \notin A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}+ \sum_{e \in A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)} \\ &= \sum_{e \notin A \subset \Omega}x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)}+ \sum_{e \in A \subset \Omega}x^{r'(\Omega-e) - r'(A-e)}y^{|A-e|+1-r'(A)} \\ &= R_{M-e}(x,y) + yR_{M-e}(x,y) \end{align} and the first result holds.

When $e$ is a coloop the rank function of $M/e$ is $r''(A) = r(A \cup e) - r(e) = r(A \cup e) - 1$. So $$ x^{r(\Omega) - r(A)}y^{|A|-r(A)} = \begin{cases} x^{r''(\Omega-e) + 1 - r''(A)}y^{|A|-r''(A)} &\text{ if $e \notin A$} \\ x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A)} &\text{ if $e \in A$} \end{cases} $$ So we have \begin{align} R_{M}(x,y) &= \sum_{e \notin A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}+ \sum_{e \in A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}\\ &= \sum_{e \notin A \subset \Omega}x^{r''(\Omega-e) + 1 - r''(A)}y^{|A|-r''(A)}+ \sum_{e \in A \subset \Omega}x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A)}\\ &= xR_{M/e}(x,y) + R_{M/e}(x,y) \end{align} and the second result holds.

Finally when $e$ is neither a loop nor coloop we have $$ x^{r(\Omega) - r(A)}y^{|A|-r(A)} = \begin{cases} x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)} &\text{ if $e \notin A$} \\ x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A-e)} &\text{ if $e \in A$} \end{cases} $$ where $r', r''$ are the rank functions of $M-e$ and $M/e$ respectively. So we have \begin{align} R_{M}(x,y) &= \sum_{e \notin A \subset \Omega}x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)}+ \sum_{e \in A \subset \Omega}x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A)}\\ &= R_{M/e}(x,y) + R_{M/e}(x,y) \end{align} and the final result holds.