Tutte seminar - Peter Nelson

Dense Triangle-free Binary Matroids

Abstract:

Brandt and Thomassé proved that a triangle-free graph $G$ with minimum degree greater than $\frac{1}{3}|V(G)|$ has chromatic number at most 4. On the other hand, Hajnal proved that for all real $\alpha > 0$ there exist triangle-free graphs G with minimum degree at least $(\frac{1}{3} - \alpha)|V(G)|$ and arbitrarily large chromatic number. I discuss a surprisingly similar theorem for triangle-free binary matroids, where we consider their 'critical number' in place of chromatic number. This is joint work with Jim Geelen. No knowledge of matroid theory will be assumed.