Tutte seminar - Peter Nelson

The structure of triangle-free graphs and geometries

Abstract:

Brandt and Thomass\'{e} proved that a triangle-free graph $G$ of minimum degree greater than $\frac{1}{3}|V(G)|$ has chromatic number at most $4$. Moreover, Luczak showed that for all $\epsilon > 0$, there exists $N = N(\epsilon)$ so that every triangle-free graph $G$ is obtained from a triangle-free graph on at most $N$ vertices by duplicating vertices. On the other hand, Hajnal proved that for all $\epsilon > 0$ and every integer $t$, there is a triangle-free graph $G$ with minimum degree at least $(\frac{1}{3}-\epsilon)|V(G)|$ and chromatic number at least $t$. Thus, the constant $\frac{1}{3}$ plays a very special role for the class of triangle-free graphs. I will discuss the above problems and recent work with Rutger Campbell and Jim Geelen where we obtain surprisingly similar results for triangle-free binary geometries.