The local density problem for triangles: exact determination of $\beta(\alpha)$ and the Erdős–Faudree–Rousseau–Schelp conjecture

For $0<\alpha\le 1$, let $\beta(\alpha)$ be the least $\beta$ such that every sufficiently large $n$-vertex graph in which every $\lfloor\alpha n\rfloor$-vertex subset spans at least $\beta n^2$ edges must contain a triangle; equivalently, the largest normalized edge count that can be forced simultaneously in every $\lfloor\alpha n\rfloor$-subset of some triangle-free graph. Erdős, Faudree, Rousseau and Schelp (1994) conjectured a piecewise formula: $\beta(\alpha)=(5\alpha-2)/25$ on $53/120\le\alpha\le 17/30$ (5-cycle blow-up extremal) and $\beta(\alpha)=(2\alpha-1)/4$ on $17/30\le\alpha\le 1$ (bipartite extremal), and posed the analogous clique question for $K_4$ at $\alpha=1/2$. The upper range is proved only for $\alpha\ge 0.579$ (Balogh–Clemen–Lidický, flag algebras), leaving the window $17/30\le\alpha<0.579$; the lower range is refuted below $\alpha=0.474$ by the Higman–Sims graph (Brandt) and otherwise open, containing as the $\alpha=1/2$ case Erdős's sparse-half conjecture $\beta(1/2)=1/50$ (best bound $27/1024$, Razborov); below $53/120$ no formula is conjectured and only order-of-magnitude bounds $c\,\alpha^3/\log^5(1/\alpha)\le\beta(\alpha)\le\alpha^3/2$ are known; the clique question posed in the source — the $K_4$ instance at $\alpha=1/2$ (threshold $n^2/18$) — was resolved affirmatively by Reiher, while the general clique local-density problem, posed by Erdős, remains open as a distinct question. The problem is open.

Background

By Mantel's theorem, every graph on $n$ vertices with more than $n^2/4$ edges contains a triangle, and the balanced complete bipartite graph shows this is tight; Turán's theorem is the analogous statement forbidding a $K_{r+1}$ (a clique on $r+1$ vertices, i.e. $r+1$ pairwise adjacent vertices), with the balanced complete $r$-partite graph extremal. In the early 1990s Erdős, Faudree, Rousseau and Schelp asked what happens when the density assumption is imposed not globally but locally: an $n$-vertex graph is called $(\alpha,\beta)$-dense if every set of $\lfloor\alpha n\rfloor$ vertices spans at least $\beta n^2$ edges (floor versus ceiling is immaterial to the asymptotic value). Writing $e(S)$ for the number of edges inside a vertex set $S$, define

$$\beta(\alpha)=\limsup_{n\to\infty}\ \frac{1}{n^2}\ \max_{\substack{G\ \text{triangle-free}\\ |V(G)|=n}}\ \min_{|S|=\lfloor\alpha n\rfloor} e(S),$$

the largest normalized edge count that can be guaranteed simultaneously in every $\lfloor\alpha n\rfloor$-subset of some triangle-free graph; equivalently the infimum of those $\beta$ for which every $(\alpha,\beta)$-dense graph must contain a triangle (for all sufficiently large $n$). Mantel's theorem is the case $\alpha=1$, giving $\beta(1)=1/4$; Erdős had earlier posed the special case $\alpha=1/2$ — the sparse half conjecture, carrying a 250-dollar reward: every triangle-free graph has an $n/2$-vertex subset spanning at most $n^2/50$ edges, i.e. $\beta(1/2)=1/50$.

The candidate extremal graphs are blow-ups: replace each vertex of a small triangle-free graph $F$ by an independent set (a class), joining two classes completely exactly when the corresponding vertices of $F$ are adjacent; the blow-up is balanced when all classes have equal size. Balanced blow-ups of the 5-cycle $C_5$ (and, as observed by Simonovits, also of the Petersen graph) are triangle-free and force every half of the vertices to span at least $n^2/50$ edges — the origin of the constant $1/50$. The Andrásfai graph $F_3$ (an 8-vertex, 3-regular, triangle-free Möbius ladder, the third member of a family of dense triangle-free graphs with small independence number) gives better constructions for small $\alpha$; the Higman–Sims graph (a 100-vertex triangle-free strongly regular graph with parameters $(100,22,0,6)$; strongly regular means the number of common neighbors of two vertices depends only on whether they are adjacent) yields constructions beating the 5-cycle in a small range below $\alpha=0.474$.

In this language, the conjecture of Erdős–Faudree–Rousseau–Schelp (1994) — the central target of the source paper 'A local density condition for triangles' — predicts the piecewise formula

$$\beta(\alpha)=\begin{cases}\dfrac{2\alpha-1}{4}, & \dfrac{17}{30}\le\alpha\le 1,\\[4pt]\dfrac{5\alpha-2}{25}, & \dfrac{53}{120}\le\alpha\le\dfrac{17}{30},\end{cases}$$

with the balanced complete bipartite graph extremal on the upper range and the balanced $C_5$-blow-up extremal on the lower one; below $\alpha=53/120$ the 5-cycle blow-up ceases to be optimal and the paper offers no conjecture. The same paper proved the first formula for $\alpha\ge 0.648$, established the general upper bound $\beta(\alpha)\le\alpha^3/2$ (an averaging argument combined with Mantel's theorem), constructed triangle-free graphs showing $\beta(\alpha)\ge c\,\alpha^3/\log^5(1/\alpha)$ for small $\alpha$ (via Spencer's lower bound $r(3,k)>c\,(k/\log k)^2$ on the Ramsey number $r(3,k)$, the least $N$ such that every red/blue edge-coloring of $K_N$ contains a red triangle or a blue $K_k$), and posed the analogous clique question, shared with Chung–Graham — whether every graph whose every $\lfloor n/2\rfloor$-vertex subset spans more than $n^2/18$ edges must contain a $K_4$.

Modern attacks combine stability arguments (showing near-extremal graphs are structurally close to a blow-up) with flag algebras, a computer-assisted semidefinite-programming framework introduced by Razborov for computing extremal densities in graphs; this machinery underlies the current best ranges for the triangle problem. Reiher's theorem that every $K_4$-free graph has an $n/2$-vertex subset spanning at most $n^2/18$ edges, which resolved the $K_4$ instance just mentioned, instead builds on the regular case established by Liu–Ma and on a Ramsey–Turán-type analysis of vertex neighbourhoods.

Problem Statement

Objective: determine the local density function for triangles — for every $0<\alpha\le 1$, determine

$$\beta(\alpha)=\limsup_{n\to\infty}\ \frac{1}{n^2}\ \max_{\substack{G\ \text{triangle-free}\\ |V(G)|=n}}\ \min_{|S|=\lfloor\alpha n\rfloor} e(S),$$

equivalently the infimum of those $\beta$ such that, for all sufficiently large $n$, every $n$-vertex graph in which every $\lfloor\alpha n\rfloor$-vertex subset spans at least $\beta n^2$ edges contains a triangle.

Determine $\beta(\alpha)$ for every $0<\alpha\le 1$:

(i) Prove or disprove the conjecture of Erdős–Faudree–Rousseau–Schelp that $\beta(\alpha)=(2\alpha-1)/4$ on $17/30\le\alpha\le 1$ and $\beta(\alpha)=(5\alpha-2)/25$ on $53/120\le\alpha\le 17/30$ — specifically: close the still-unproved window $17/30\le\alpha<0.579$ of the first formula; settle the second formula on the surviving range $[0.474,17/30)$, and determine the true $\beta(\alpha)$ on the refuted band $53/120\le\alpha<0.474$, where the Higman–Sims blow-up shows $\beta(\alpha)>(5\alpha-2)/25$; and, in particular, resolve the $\alpha=1/2$ case, Erdős's sparse-half conjecture $\beta(1/2)=1/50$ (best current bounds: $1/50\le\beta(1/2)\le 27/1024$).

(ii) For $\alpha<53/120$, where no formula is conjectured, determine $\beta(\alpha)$: the known bounds $c\,\alpha^3/\log^5(1/\alpha)\le\beta(\alpha)\le\alpha^3/2$ leave both the logarithmic factor and the constant open, and the extremal constructions (Andrásfai-graph and Higman–Sims blow-ups, Ramsey graphs) are not classified.

References

1. P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, 'A local density condition for triangles', Discrete Mathematics 127 (1994) 153–161. doi:10.1016/0012-365X(92)00474-6, https://doi.org/10.1016/0012-365X(92)00474-6
2. Michael Krivelevich, 'On the edge distribution in triangle-free graphs', Journal of Combinatorial Theory, Series B 63 (1995) 245–260. doi:10.1006/jctb.1995.1018, https://doi.org/10.1006/jctb.1995.1018
3. Joel Spencer, 'Asymptotic lower bounds for Ramsey functions', Discrete Mathematics 20 (1977) 69–76. doi:10.1016/0012-365X(77)90044-9, https://doi.org/10.1016/0012-365X(77)90044-9
4. F. R. K. Chung, R. L. Graham, 'On graphs not containing prescribed induced subgraphs', in: A Tribute to Paul Erdős, Cambridge University Press, Cambridge, 1990, pp. 111–120. doi:10.1017/cbo9780511983917.009, https://doi.org/10.1017/cbo9780511983917.009
5. S. Brandt, 'The local density of triangle-free graphs', Discrete Mathematics 183 (1998) 17–25. doi:10.1016/S0012-365X(97)00074-5, https://doi.org/10.1016/S0012-365X(97)00074-5
6. Peter Keevash, Benny Sudakov, 'Local density in graphs with forbidden subgraphs', Combinatorics, Probability and Computing 12 (2003) 139–153. doi:10.1017/S0963548302005539, https://doi.org/10.1017/S0963548302005539
7. Peter Keevash, Benny Sudakov, 'Sparse halves in triangle-free graphs', Journal of Combinatorial Theory, Series B 96 (2006) 614–620. doi:10.1016/j.jctb.2005.11.003, https://doi.org/10.1016/j.jctb.2005.11.003
8. Sergey Norin, Liana Yepremyan, 'Sparse halves in dense triangle-free graphs', Journal of Combinatorial Theory, Series B 115 (2015) 1–25. doi:10.1016/j.jctb.2015.04.006, https://doi.org/10.1016/j.jctb.2015.04.006
9. Wiebke Bedenknecht, Guilherme Oliveira Mota, Christian Reiher, Mathias Schacht, 'On the local density problem for graphs of given odd-girth', Journal of Graph Theory 90 (2019) 137–149. doi:10.1002/jgt.22372, https://doi.org/10.1002/jgt.22372, arXiv:1609.05712, https://arxiv.org/abs/1609.05712
10. Alexander A. Razborov, 'More about sparse halves in triangle-free graphs', Sbornik: Mathematics 213 (2022) 109–128. doi:10.1070/SM9615, https://doi.org/10.1070/SM9615, arXiv:2104.09406, https://arxiv.org/abs/2104.09406
11. Xizhi Liu, Jie Ma, 'Sparse halves in K4-free graphs', Journal of Graph Theory 99 (2022) 5–25. doi:10.1002/jgt.22722, https://doi.org/10.1002/jgt.22722, arXiv:2007.14623, https://arxiv.org/abs/2007.14623
12. Christian Reiher, 'K4-free graphs have sparse halves', Bulletin of the London Mathematical Society 55 (2023) 1178–1195. doi:10.1112/blms.12782, https://doi.org/10.1112/blms.12782, arXiv:2108.07297, https://arxiv.org/abs/2108.07297
13. József Balogh, Felix Christian Clemen, Bernard Lidický, '10 Problems for Partitions of Triangle-free Graphs', European Journal of Combinatorics 121 (2024) 103841. doi:10.1016/j.ejc.2023.103841, https://doi.org/10.1016/j.ejc.2023.103841, arXiv:2203.15764, https://arxiv.org/abs/2203.15764
14. József Balogh, Ignacy Buczek, Andrzej Grzesik, Piotr Kuc, 'Balanced bipartite distance of K4-free graphs', arXiv preprint (2026). arXiv:2605.05346, https://arxiv.org/abs/2605.05346
15. József Balogh, Ce Chen, Bernard Lidický, 'Bipartite cuts in Ramsey–Turán style', arXiv preprint (2026). arXiv:2606.20397, https://arxiv.org/abs/2606.20397
16. Jiaao Li, Xinyuan Li, Yan Wang, Zhouningxin Wang, 'A local clique density theorem in H-free graphs', arXiv preprint (2026). arXiv:2608.18663, https://arxiv.org/abs/2608.18663