Skip to content

Erdős Problem #128

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: falsifiable (not automatically the live result).
Subject areas: graph theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

An induced subgraph is formed by selecting vertices and keeping every edge between them. Erdős and Rousseau asked whether a graph \(G\) on \(n\) vertices must contain a triangle if every induced subgraph on at least \(\lfloor n/2\rfloor\) vertices has more than \(n^2/50\) edges.

Equivalently, does every triangle-free graph admit a set of at least half its vertices spanning at most \(n^2/50\) edges? This is the sparse-half conjecture. The bound is normalized by the original \(n\), not by the chosen subset's size. The strict inequality and the floor convention affect finite cases.

A small example

A five-cycle is triangle-free. Replacing every vertex by \(t\) mutually nonadjacent vertices and every cycle edge by a complete bipartite graph gives a triangle-free graph on \(5t\) vertices. Its carefully chosen half-sized subsets have edge counts of order \(n^2/50\). This blow-up explains why the conjectured constant is sharp if the assertion holds.

One must search over all eligible vertex subsets. Checking only randomly chosen halves could miss the sparsest one; checking a non-induced subgraph would permit deleting edges and change the problem.

What is known

The universal threshold \(1/50\) remains OPEN/FALSIFIABLE. Erdős, Faudree, Rousseau and Schelp (1994) established a weaker universal criterion, with \(50\) replaced by \(16\). Alexander Razborov's primary 2022 journal article, More about sparse halves in triangle-free graphs, proves that a triangle-free graph always has a half-sized subset spanning at most

\[ \frac{27}{1024}n^2 \]

edges, versus the conjectured \(n^2/50\). Since \(27/1024\) exceeds \(1/50\), this is progress, not the desired universal inequality.

Razborov separately proves the conjectured threshold for graphs of girth at least five, for independence number at least \(2n/5\), and for strongly regular graphs. These are restricted classes; they do not collectively cover all triangle-free graphs.

GCL's current state

The pinned and maintained Erdős #128, last edited October 2025, label the exact conjecture FALSIFIABLE. The original source task is #1397. The primary Razborov publisher abstract and constants were checked, but his full flag-algebra argument was not independently reconstructed.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task is to enumerate balanced blow-ups of \(C_5\) for \(t=2,4\), list every vertex subset of size at least \(\lfloor5t/2\rfloor\), and calculate its induced-edge count exactly. Acceptance: graph is triangle-free, the minimum induced count is reported with an explicit subset, and comparisons distinguish equality from strict inequality at \(n^2/50\). Stop at finite sharpness fixtures; no universal theorem follows.

Sources and claim boundaries

No proof of the universal sharp threshold, independent flag-algebra certification, or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1397 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction