# 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?

## 1 Answer

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.

• Thanks for the very good and detailed answer. I mistakenly assumed that the rank function on the contraction over a coloop was the same as the rank function on the original matroid, which only holds for loops – ak87 Mar 27 at 22:17