Sparse halves in triangle-free graphs

If a graph has no triangles, must some half of its vertices span few edges? Erdős and Rousseau conjectured that every triangle-free graph on $n$ vertices has a set of $\lfloor n/2\rfloor$ vertices spanning at most $n^2/50$ edges, a bound attained by blow-ups of the 5-cycle and of the Petersen graph. The constant has been improved several times but $1/50$ is still out of reach.

Problem

Let $G$ be a graph on $n$ vertices such that every induced subgraph on at least $\lfloor n/2\rfloor$ vertices has more than $n^2/50$ edges. Must $G$ contain a triangle?

Equivalently: does every triangle-free graph on $n$ vertices contain a set of $\lfloor n/2\rfloor$ vertices that spans at most $n^2/50$ edges? Erdős offered $250 for this problem.

Background

The question is due to Erdős and Rousseau and is known as the sparse halves conjecture. The constant $50$ would be best possible: in the balanced blow-up of the 5-cycle, or of the Petersen graph, every half spans at least $n^2/50$ edges. Erdős, Faudree, Rousseau and Schelp (1994) proved the statement with $50$ replaced by $16$ , and more generally that if every set of at least $\alpha n$ vertices spans more than $\alpha^3n^2/2$ edges, then $G$ contains a triangle. The problem is linked, through work of Brandt on eigenvalues of regular graphs, to the question of making triangle-free graphs bipartite.

What is known

Weaker constants. Krivelevich (1995) proved the analogous statement for sets of $3n/5$ vertices (with $25$ in place of $50$ ). Razborov (2022) proved the conjecture with $1/50$ replaced by $27/1024$ .
Dense or sparse graphs. Keevash and Sudakov (2006) proved the conjecture when $G$ has at most $n^2/12$ or at least $n^2/5$ edges, and Norin and Yepremyan (2015) extended this to graphs with at least $(1/5-c)n^2$ edges for some $c>0$ .
Computation. Searches reported on the problem's forum in 2026, over small triangle-free graphs and blow-ups of known strongly regular graphs, found no counterexample.
Claims. A proof claim posted in August 2026 (A. Sarid) improves $27/1024\approx0.02637$ to $0.0262$ , combining flag algebras for dense graphs with a theorem of Balogh, Clemen and Lidický for sparse ones; its Lean formalisation takes that theorem as an assumption. It has not been refereed.

What would count as progress

A proof of the conjecture for a new range of edge densities, or with a constant closer to $1/50$ than $27/1024$ .
A counterexample: a triangle-free graph on $n$ vertices in which every set of $\lfloor n/2\rfloor$ vertices spans more than $n^2/50$ edges; for moderate $n$ this can be verified exactly by computer.
A formal proof against the Lean statement in formal-conjectures.

References

P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, A local density condition for triangles, Discrete Math. 127 (1994), 153–161. doi:10.1016/0012-365X(92)00474-6
M. Krivelevich, On the edge distribution in triangle-free graphs, J. Combin. Theory Ser. B 63 (1995), 245–260. doi:10.1006/jctb.1995.1018
P. Keevash and B. Sudakov, Sparse halves in triangle-free graphs, J. Combin. Theory Ser. B 96 (2006), 614–620. doi:10.1016/j.jctb.2005.11.003
S. Norin and L. Yepremyan, Sparse halves in dense triangle-free graphs, J. Combin. Theory Ser. B 115 (2015), 1–25. doi:10.1016/j.jctb.2015.04.006
A. A. Razborov, More about sparse halves in triangle-free graphs, Sb. Math. 213 (2022), 109–128. doi:10.1070/SM9615

Source

Imported from Erdős Problems 128, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.