The approximate structure of triangle-free graphs скачать в хорошем качестве

The approximate structure of triangle-free graphs

Yuval Wigderson (ETH Zurich) https://simons.berkeley.edu/talks/yuv... Sublinear Graph Simplification 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.