Friday, June 6, 2014 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Dense Triangle-free Binary Matroids
Speaker: | Peter Nelson |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics 3 (M3) 3103 |
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.