---

Claim. Two results of P. Keevash and B. Sudakov, Sparse halves in triangle-free graphs, J. Combin. Theory Ser. B 96 (2006), no. 4, 614--620, cited as [KeSu06] on the problem page. Proposition 1.2: every triangle-free graph on $n$ vertices with at most $n^2/12$ edges has a set of $n/2$ vertices spanning at most $n^2/50$ edges. Theorem 1.1: if a triangle-free graph $G$ on $n$ vertices has at least $n^2/5$ edges and every $n/2$ of its vertices span at least $n^2/50$ edges, then $n=10m$ and $G$ is the balanced blow-up $C_5(2m)$ of the $5$-cycle. Since $C_5(2m)$ has $n/2$ vertices spanning exactly $n^2/50$ edges, every triangle-free graph with at least $n^2/5$ edges has $n/2$ vertices spanning at most $n^2/50$ edges, the balanced blow-up of $C_5$ being the only graph in that range meeting the bound. In the contrapositive form of Problem 128, a graph on $n$ vertices with at most $n^2/12$ or at least $n^2/5$ edges whose every $n/2$ vertices span more than $n^2/50$ edges contains a triangle. The dense case removes the regularity hypothesis of Krivelevich's Theorem 3. Library home keevash_2006_sparse_halves_triangle_free_graphs.

Covers. Triangle-free graphs on $n$ vertices with at most $n^2/12$ edges or with at least $n^2/5$ edges. Not covered: the edge range between $n^2/12$ and $n^2/5$, which contains the balanced blow-up of the Petersen graph; the question as posed stays open.

Depends on. Nothing in this wiki; the proofs are self-contained.

Acceptance. Refereed: the paper appeared in the Journal of Combinatorial Theory, Series B. The site's commentary credits both edge ranges to the paper but labels the problem FALSIFIABLE, which settles nothing, so that credit is not listed as reviewed.

Dating. The article prints that it was available online on 5 January 2006, the page's date; the print issue is dated July 2006.