科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-08-26· math.CO

Clique-saturating non-edges throughout the Turán range

Xiaolin Wang, Jiabao Yang, Ruilin Zheng

原始摘要(英文原文)· Original abstract
For an $F$-free graph $G$, a non-edge is $F$-saturating if adding it to $G$ creates a copy of $F$. We denote by $f_{p+1}(n,m)$ the minimum number of $K_{p+1}$-saturating non-edges in a $K_{p+1}$-free $n$-vertex graph with $m$ edges. Erdős and Tuza conjectured that $f_4\left(n,\mathrm{ex}(n,K_3)+ 1\right)= (1 + o(1)) \frac{n^2}{16}$. Balogh and Liu (JCTB, 2014) disproved this conjecture and determined the asymptotic value of $f_4(n,\mathrm{ex}(n,K_3)+1)$. He, Ma, Ma and Ye (JCTB, 2023) later determined $f_{p+1}(n,\mathrm{ex}(n,K_p)+1)$ asymptotically for every $p\ge 3$, and asked for the value of $f_{p+1}(n,m)$ for all $\mathrm{ex}(n,K_p)+1\le m\le \mathrm{ex}(n,K_{p+1})$ and every $p\ge 3$. In this paper, we answer their question asymptotically for all $\mathrm{ex}(n,K_p)+1\le m\le \mathrm{ex}(n,K_{p+1})$ and every $p\ge 3$. We also determine the exact value of $f_3(n,m)$ for all $0\le m\le \mathrm{ex}(n,K_3)$ by a different method.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

Clique-saturating non-edges throughout the Turán range — 科研速览 Science Skim