





















We construct $n$-vertex graphs $G$ where $εn^2$ edges must be deleted to become triangle-free, which contain less than $ε^{(C_{\text{new}}-o(1))\log_2 1/ε}n^3$ triangles for $C_{\text{new}}= \frac{1}{4\log_2(4/3)} \approx 1.6601$. Previously, a bound of the same shape was known, but with $C_{\text{new}}$ replaced by $C_{\text{old}} := C_{\text{new}}/2$. Our construction uses ideas from additive combinatorics, drawing especially from the corners problem, but does not yield new bounds for those problems.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。