Abstract
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, it turns out that this is essentially the *only* way of constructing dense triangle-free graphs. More precisely, for every $\varepsilon>0$, there exists some $M(\varepsilon)$ such that every triangle-free graph $G$ is $\varepsilon$-close to a blowup of a triangle-free graph $G_0$ on $M(\varepsilon)$ vertices. In other words, if we are willing to tolerate some small error, then every triangle-free graph is of the form described above.
Unfortunately, this result is of limited applicability, because the known bounds on $M(\varepsilon)$ are enormous, and it is moreover known that super-exponential bounds are necessary in general. In this talk, I will discuss this problem, and describe several settings in which we can prove much stronger bounds and provide efficient algorithms to compute $G_0$.
Based on joint work with Lior Gishboliner and Eoin Hurley.