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

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?

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.