Erdős #128 — local edge density forces a triangle

Statement

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

Equivalently (contrapositive): must every triangle-free graph on $n$ vertices have a "sparse half" — an induced subgraph on $\geq \lfloor n/2\rfloor$ vertices with $\leq n^2/50$ edges? This is the Erdős sparse-halves conjecture. Forum clarification (Salvatore Mercuri / StijnC, erdosproblems.com/128 comments): "subgraph" means *induced* subgraph, and the $\lfloor n/2\rfloor$ floor is load-bearing — without it $C_5$ is a counterexample at odd $n$.

Facts

- Prize $250; status per erdosproblems.com/128 (site-owner belief, verified by direct fetch 2026-07-02): FALSIFIABLE, open — "Open, but could be disproved with a finite counterexample." - Falsifiable: yes — a single triangle-free graph $G$ on $n$ vertices where the sparsest induced subgraph on exactly $\lfloor n/2\rfloor$ vertices still has $>n^2/50$ edges disproves it outright (any larger $\geq\lfloor n/2\rfloor$-subset only has weakly more edges since induced-edge-count is monotone under vertex addition, so checking size exactly $\lfloor n/2\rfloor$ suffices). - Origin: #128 : [Er93,p.344] [ErRo93] [Er97b]. [Er93] = P. Erdős, "Some of my favorite solved and unsolved problems in graph theory," Quaestiones Math. (1993), 333-350. [ErRo93] = Erdős & Rousseau, "The size Ramsey number of a complete bipartite graph," Discrete Math. (1993), 259-262 (site's citation for the joint attribution, despite the title). [Er97b] = P. Erdős, "Some old and new problems in various branches of combinatorics," Discrete Math. (1997), 227-231. Per a forum comment (Alfaiz, 22 Feb 2026, erdosproblems.com/128), the problem traces back further to P. Erdős, "Problems and results in graph theory and combinatorial analysis," Congr. Numer. 15:169-192 (1976) (from the 1975 British Combinatorial Conference, Aberdeen). - Tight extremal witness (constant 50 is asymptotically best possible): a balanced blow-up of $C_5$, or the Petersen graph — both triangle-free — achieve density $n^2/50$ (erdosproblems.com/128 remarks). - Known results / best bounds, all sourced from erdosproblems.com/128 remarks + the underlying papers: - Erdős, Faudree, Rousseau, Schelp [EFRS94], "A local density condition for triangles," Discrete Math. (1994), 153-161: proved the statement true with $50$ replaced by $16$. More generally, for any $0<\alpha<1$, if every $\geq\alpha n$-subset has $>\alpha^3 n^2/2$ edges then $G$ has a triangle. - Krivelevich [Kr95], "On the edge distribution in triangle-free graphs," J. Combin. Theory Ser. B (1995), 245-260: proved it with $n/2$ replaced by $3n/5$ and $50$ replaced by $25$. - Keevash & Sudakov [KeSu06], "Sparse halves in triangle-free graphs," JCTB (2006), 614-620: proved the exact $n^2/50$ constant, but only under an extra edge-count assumption — either $G$ has $\leq n^2/12$ edges, or $G$ has $\geq n^2/5$ edges. Per forum comment (Wouter CvB, 29 Oct 2025), the $\geq n^2/5$ case was "the hard part." - Norin & Yepremyan [NoYe15], "Sparse halves in dense triangle-free graphs," JCTB (2015/16), arXiv:1311.5818: pushed the Keevash-Sudakov dense-side threshold down from $n^2/5$ to $(1/5-c)n^2$ for some absolute $c>0$; also proved the exact bound for minimum degree $\geq 5n/14$ (improving an earlier $2n/5$ minimum-degree result) and for graphs structurally close (in edit distance) to the Petersen graph. - Razborov [Ra22], "More about sparse halves in triangle-free graphs," Mat. Sb. (2022), 119-140, arXiv:2104.09406: current strongest general bound, true with $1/50$ replaced by $27/1024 \approx 0.02637$ (vs. conjectured $1/50=0.02$) — a flag-algebra proof. Fully proves the exact $n^2/50$ constant for triangle-free graphs of girth $\geq 5$, independence number $\geq 2n/5$, and strongly regular graphs. Per forum comment citing Balogh-Clemen-Lidický (2024), Razborov's $27/1024$ remains the best known general bound as of the page's last edit (31 Oct 2025). - Balogh, Clemen, Lidický, "10 Problems for Partitions of Triangle-free Graphs," Eur. J. Combin. 121 (2024) #103841, arXiv:2203.15764: solve a *companion* balanced-2-partition variant (every triangle-free $G$ has $A\cup B$, $|A|=|B|=n/2$, $e(G[A])+e(G[B])\leq n^2/16$, sharp) — related but a distinct sum-of-two-halves statement, not #128 itself. - Stephan Brandt, "The local density of triangle-free graphs," Discrete Math. 183 (1998), 17-25: developed a spectral method ($\mu_1+\mu_n \leq (3-2\sqrt2)n$ for regular triangle-free $G$) for local-density questions of this type and used the Higman-Sims graph's eigenvalues to refute a *related but different* Erdős et al. local-density conjecture. Flagged in the forum (Alfaiz) as "a surprising connection between the eigenvalues of regular graphs ... and this problem." - Formalized: Yes — erdosproblems.com marks "Formalised statement? Yes." Confirmed: FormalConjectures/ErdosProblems/128.lean in google-deepmind/formal-conjectures states erdos_128 as an iff-with-answer(sorry) (statement only, unproved, sorryd). - Related problems: no other erdosproblems.com-numbered problem was confirmed as a direct neighbor this pass (checked #127 = distinct, solved, max-cut/bipartite-subgraph problem; #129 = distinct open Ramsey problem $R(n;3,r)<C^{\sqrt n}$ — an unreliable web-search summary had misattributed #129's statement to #128, corrected by direct fetch). The $K_4$-free analogue of the sparse-halves question (arXiv:2007.14623, arXiv:2108.07297, arXiv:2412.13485, arXiv:2605.05346) is conceptually related but no erdosproblems.com number was found for it in this pass.

Literature state

Not resolved, but heavily worked: this is the classical "Erdős sparse-halves conjecture," continuously attacked since Erdős's 1975/76 original formulation, formalized jointly with Rousseau in 1993, and still actively studied as of 2024-2026 (Balogh-Clemen-Lidický 2024; the erdosproblems.com page's own remarks were last edited 31 Oct 2025, with a forum comment as recent as 22 Feb 2026). No finite counterexample and no full proof of the general statement is known. The unresolved gap is narrow but real: the best proven *general* bound (Razborov 2022, $27/1024n^2 \approx 0.02637n^2$) sits strictly above the conjectured $n^2/50=0.02n^2$, so a counterexample — a triangle-free graph whose sparsest $\lfloor n/2\rfloor$-half has more than $0.02n^2$ but at most $0.02637n^2$ edges — is not ruled out by any published theorem for *general* triangle-free graphs. The conjecture IS fully proved (exact $1/50$ constant) for several restricted classes: girth $\geq5$ graphs, graphs with independence number $\geq 2n/5$, strongly regular graphs (Razborov 2022), graphs with $\geq(1/5-c)n^2$ or $\leq n^2/12$ edges (Keevash-Sudakov 2006 / Norin-Yepremyan 2015), and minimum degree $\geq 5n/14$ (Norin-Yepremyan 2015) — so any counterexample construction must deliberately avoid all of these classes. I found no evidence of AI/LLM involvement on this specific problem: github.com/teorth/erdosproblems's "AI contributions to Erdős problems" wiki page, fetched and grepped in full, does not mention #128, despite listing other problems advanced by GPT-5-class models, AlphaEvolve, or Aristotle in 2025-2026.

Attack surface

- Mode: finite-search (primary, since falsifiable) + literature-resolution (the general upper bound is still being incrementally improved: $16\to25\to\text{[degree-conditional exact]}\to27/1024$, 1994-2022, so tracking the next improvement is also live). - Concrete first experiment: search for a triangle-free graph $G$ on $n$ vertices (start with $n$ a multiple of 10-20 for symmetry, sweep $n \in [20,80]$) whose sparsest $\lfloor n/2\rfloor$-vertex induced subgraph has $>n^2/50$ edges, i.e. $\min_{|S|=\lfloor n/2\rfloor} e(G[S]) > n^2/50$. Two complementary tracks: 1. Structured/algebraic candidates (mirrors how EFRS94/Krivelevich/Razborov's extremal examples were found): circulant/Cayley graphs on $\mathbb Z_n$ with a triangle-free connection set, generalized $C_5$-blow-ups with unequal part sizes, Kneser graphs $K(m,2)$, incidence graphs of small designs, and strongly-regular-adjacent triangle-free graphs (Petersen, Clebsch, Higman-Sims — note Razborov already proves strongly regular graphs exactly at $1/50$, so these are *ruled out* and should be used only as a sanity check, not a candidate source). For each vertex-transitive/edge-transitive candidate, exploit the automorphism group to reduce the $\binom{n}{\lfloor n/2\rfloor}$ subset space to a small number of orbit representatives before computing $e(G[S])$. 2. CP-SAT / ILP direct search: encode $G$ with edge variables $x_{ij}\in\{0,1\}$, add the triangle-free constraint $x_{ij}+x_{jk}+x_{ik}\leq 2$ for every triple, then for a fixed candidate $G$ solve the inner "sparsest-$k$-subgraph" problem — membership variables $y_i\in\{0,1\}$, $\sum y_i = \lfloor n/2\rfloor$, linearize $z_{ij}=x_{ij}\wedge y_i\wedge y_j$ via standard McCormick constraints, minimize $\sum z_{ij}$ — using OR-Tools CP-SAT or an ILP solver (Gurobi/CBC). Nest this inside an outer local-search/simulated-annealing loop over $G$ (start from a near-extremal $C_5$-blow-up or random triangle-free graph, greedily add/remove edges preserving triangle-freeness while re-solving the inner sparsest-subset ILP to push its optimum above $n^2/50$). - Oracle: fully mechanical. For a candidate $G$: (a) verify triangle-freeness by brute force ($O(n^3)$ triple check, or trace of $A^3$); (b) solve $\min_{|S|=\lfloor n/2\rfloor}e(G[S])$ to *proven optimality* via ILP/CP-SAT (not a heuristic — the claim requires the true minimum, not a sample); (c) cross-validate the ILP optimum against brute-force enumeration over all $\binom{n}{\lfloor n/2\rfloor}$ subsets for small $n$ (say $n\leq 24$) to rule out solver bugs; (d) if the optimum exceeds $n^2/50$, the pair $(G, n)$ is a complete, independently reproducible disproof — no further theory needed. - Feasibility: honest read: hard, but well-posed and worth a bounded first pass. This has been actively narrowed by strong mathematicians for ~30 years (Erdős-Rousseau 1993 → Razborov 2022) using flag algebras, a technique specifically designed to find both extremal constructions and matching upper bounds; a counterexample would have to beat $27/1024\approx0.02637$ while exceeding $0.02$, a narrow $0.0064n^2$-edge window, and must avoid every already-solved subclass (girth $\geq5$, high independence number, strongly regular, degree $\geq5n/14$, edge-count extremes). The sparsest-$k$-subgraph inner problem is itself NP-hard for general graphs but tractable for small/structured $n$ (the Norin-Yepremyan paper cites informal exhaustive triangle-free-graph enumeration up to $n=17$ taking about a week on a laptop, giving a rough scale for what unrestricted brute force can reach; restricting to vertex-transitive candidates or using ILP with symmetry-breaking should comfortably reach $n$ in the tens to low hundreds). A realistic first contribution is not full resolution but: (1) a clean, reproducible computational sanity check that $n^2/50$ is not beatable by any of the classical extremal families up to moderate $n$ (reinforcing, not contradicting, the conjecture — negative but citable result), or (2) a targeted local-search push specifically inside the $[0.02,0.02637]n^2$ gap using flag-algebra-adjacent SAT/ILP tooling, which is the one area (per literature check) where no one has reported an exhaustive computational counterexample search.

Related

- concept/sparse-halves-conjecture — the general phenomenon (this problem is its triangle/$K_3$ instance; $K_4$-free analogue studied separately, arXiv:2007.14623, arXiv:2108.07297, arXiv:2412.13485, arXiv:2605.05346) - Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities — Razborov's technique, used to prove the current best general bound ($27/1024$) and the exact classes (girth $\geq5$, strongly regular, high independence number) - SAT/CP-SAT-based finite counterexample search and verification / concept/cp-sat — proposed mechanism for the finite-counterexample attack surface (sparsest-$k$-subgraph ILP nested in a triangle-free edge-search) - concept/vertex-transitive-graphs — Cayley/circulant/Kneser candidate constructions that make the inner sparsest-subset search tractable via symmetry - concept/spectral-graph-theory — Brandt's eigenvalue method ($\mu_1+\mu_n\leq(3-2\sqrt2)n$) connecting regular triangle-free graph spectra to local-density questions