The Approximate Structure of Triangle-Free Graphs

Explore a 35-minute lecture on the approximate structure of triangle-free graphs presented by Yuval Wigderson from ETH Zurich at the Simons Institute. Delve into the fascinating discovery that dense triangle-free graphs can essentially only be constructed by starting with a bounded-size triangle-free graph, blowing it up, and deleting some edges. Examine the limitations of this result due to enormous bounds on M(ε) and learn about settings where stronger bounds and efficient algorithms for computing G0 can be achieved. Gain insights from joint work with Lior Gishboliner and Eoin Hurley on sublinear graph simplification and its applications to understanding the structure of triangle-free graphs.

The approximate structure of triangle-free graphs