The approximate structure of triangle-free graphs

A natural way of constructing a dense triangle-free graph is to start with a triangle-free graph $G_0$ of bounded size, blow it up, and then delete some edges. Many of the natural triangle-free graphs we encounter, such as all bipartite graphs, can be obtained in this way.

Astonishingly, deep results in extremal graph theory imply that this is essentially the *only* way of constructing dense triangle-free graphs (up to a small error). Unfortunately, such results are of limited applicability, due to the poor quantitative aspects of known proof techniques. In this talk, I will discuss this problem, and describe several settings in which we can prove much stronger bounds. No background in extremal graph theory will be assumed.

Based on joint work with Lior Gishboliner and Eoin Hurley.