Abstract:In 1975, Bollobás, Erdős, and Szemerédi asked for the smallest $\tau$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + \tau$ must contain $K_{t, t, t}$, conjecturing that $\tau = \mathcal{O}(n^{1/2})$ for $t = 2$. We prove that $\tau = \mathcal{O}(n^{1 - 1/t})$ which confirms their conjecture and is best possible assuming the widely believed conjecture that the Zarankiewicz number satisfies $z(n; t) = \Theta(n^{2 - 1/t})$. Our proof uses a density increment argument.
We also construct an infinite family of extremal graphs that are pairwise far apart (requiring the change of $\Omega(n^2)$ edges to get between any two).
From: Freddie Illingworth Dr [view email]
[v1]
Wed, 4 Dec 2024 17:46:51 UTC (26 KB)
[v2]
Thu, 11 Jun 2026 19:54:44 UTC (335 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。