Abstract:The classical supersaturation problem, originating in classical results of Rademacher and Erdős on complete graphs, asks for the minimum number of copies of an $r$-graph $\mathcal{F}$ in an $n$-vertex $r$-graph with $\ex(n,\mathcal{F})+q$ edges. Mubayi conjectured that, for every stable non-$r$-partite $r$-graph $\mathcal{F}$, this minimum is at least $q c(n,\mathcal{F})$, where $c(n,\mathcal{F})$ is the minimum number of copies created by adding one edge to the $n$-vertex extremal $\mathcal{F}$-free $r$-graph. Ma and Yuan recently constructed infinitely many graph counterexamples, with arbitrary chromatic number at least four.
We construct, for every $r\ge 2$ and every $K>1$, a stable non-$r$-partite $r$-graph $\mathcal{F}$ with the following property: for all sufficiently large $n$ and every integer $q$ with $1\le q\le \delta n$, there is an $n$-vertex $r$-graph with $\ex(n,\mathcal{F})+q$ edges and at most $K^{-1}q c(n,\mathcal{F})$ copies of $\mathcal{F}$. Thus Mubayi's conjectured lower bound can already fail at $q=1$, and the failure can be by an arbitrarily large constant factor in every uniformi
From: Heng Li [view email]
[v1]
Thu, 25 Jun 2026 08:16:56 UTC (37 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。