MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This topic of this question is a bit outside my comfort zone, and I should say that my end goal is to really understand how much "graph theory" is captured by contraction-deletion relations. It seems like K-theory is a good way to understand this, though I'm not entirely sure why. This material is mentioned in the article "Critical problems" by J.P.S. Kung. I will give a bit of background and ask the questions in the end.

To every matroid $M$ with ground set $[n]$, we can associate an algebra $A(M)$ defined as follows. Let $\mathbb k$ be a field and let $E=\mathbb k\langle e_1, e_2, \dots, e_n\rangle$ be the graded exterior algebra over $K$, where $\text{deg}(e_i)=1$ for all $i$. If for every $S=\lbrace j_1,j_2,\dots,j_t\rbrace\subset [n]$ we define $$\partial e_{S}=\sum_{i=1}^t (-1)^{i-1} e_{j_1}\wedge \cdots\wedge \widehat{e_{j_i}}\wedge\cdots \wedge e_{j_t},$$ and let $J$ be the ideal generated by all $\partial e_S$ with $S$ ranging over the dependent sets of the matroid, then $A(M)$ is defined as the quotient $E/J$.

$A$ is a functor from $\mathcal M$, the category of matroids with strong maps, to $\mathcal{OS}$ the category of Orlik-Solomon algebras over $\mathbb k$ and $\mathbb k$-algebra homomorphisms. It is proved in Orlik-Terao that $$0\to A(G\backslash a)\to A(G)\to A(G/a)\to 0$$ is an exact sequence whenever $a$ is not a loop or an isthmus. Hence by deletion-contraction we see that in $K_0(\mathcal{OS})$ every Orlik-Solomon algebra can be written as a linear combination of $A(B_n)$'s, where $B_n$'s are Boolean algebras (the lattice of flats of free geometries). On the other hand $A(B_n)=A(B_1)^{\otimes n}$, hence the Grothendieck ring over $\mathbb Z$ of $\mathcal{OS}$ is $\mathbb Z[x]$. Kung remarks that this shouldn't be a surprise since Orlik-Solomon algebras are essentially a categorification of the characteristic polynomial of a matroid (the Poinare polynomial of the Orlik-Solomon algebra is a small modification of the characteristic polynomial).

Now the natural questions after describing this set up are:

Question 1: Is there a similar K-theoretic picture for the Tutte polynomial of a matroid? Is there a category analogous to $\mathcal{OS}$ whose $K_0$ is $\mathbb Z[x,y]$?

Question 2: What is $K_1(\mathcal{OS})$? Is such a higher K-theory for matroids developed somewhere?

share|cite|improve this question
It's hardly an answer, but there's a very dissimilar K-theoretic picture for the Tutte polynomial in this paper by Alex Fink and David Speyer: – Allen Knutson Nov 9 '11 at 0:57
I found this preprint: – Ian Agol Oct 2 '13 at 22:57

Your Answer


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

Browse other questions tagged or ask your own question.