Skip to content

Erdős Problem #180

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

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

For a graph \(H\), \(\mathrm{ex}(n;H)\) is the maximum number of edges in an \(n\) vertex graph containing no copy of \(H\). For a finite family of graphs \(\mathcal F\), \(\mathrm{ex}(n;\mathcal F)\) is the maximum number of edges in an \(n\) vertex graph avoiding every member of \(\mathcal F\).

Erdős and Simonovits asked whether every finite forbidden family has some member \(G\in\mathcal F\) whose individual Turán number is bounded by a constant multiple of the joint extremal number:

\[ \mathrm{ex}(n;G)\ll_{\mathcal F}\mathrm{ex}(n;\mathcal F) \]

uniformly as \(n\) grows. The reverse inequality is automatic, so the conjecture asks whether one forbidden graph captures the order of the entire family's restriction.

A small example

Take \(\mathcal F=\{K_{1,2},2K_2\}\), consisting of a two-edge star and a two-edge matching. A graph that avoids the two-edge star has maximum degree at most one and is therefore a disjoint union of edges and isolated vertices. Avoiding the two-edge matching then limits the entire graph to at most one edge:

\[ \mathrm{ex}(n;\mathcal F)=1\quad(n\ge2). \]

Separately, graphs avoiding \(K_{1,2}\) have \(\lfloor n/2\rfloor\) edges at most (achieved by a matching); graphs avoiding \(2K_2\) may have \(n-1\) edges (a star). Thus each individual extremal number grows linearly while their joint maximum stays constant. No fixed multiplicative constant can compare them.

What is known

The literal universal conjecture is DISPROVED by this elementary finite-family counterexample. The maintained Erdős #180, edited January 2026, records the star-and-matching construction credited to Zach Hunter but continues to label the broader surviving problem OPEN, asking implicitly whether there are nondegenerate families for which the conjecture remains true.

For families in which every forbidden graph has chromatic number at least three, the Erdős–Stone theorem supplies a common quadratic leading term determined by the smallest chromatic number in the family. That positive restricted case does not rescue the universal quantifier over all finite families.

The older pinned catalogue classifies #180 DISPROVED. This is consistent with the literal counterexample; the live OPEN headline appears to reflect an unformalized revised question. Both descriptions must be retained rather than silently deciding that one status supersedes the other.

GCL's current state

Original source issue: #1449. Status boundary: PINNED DISPROVED / LIVE OPEN (residual classification). The two-graph counterexample is independently checkable; a proposed exclusion of degenerate configurations is not part of the protected original theorem statement. No GCL certification is asserted for an unspecified revision.

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 fixture enumerates graphs on up to eight vertices and computes the joint and individual extremal numbers for the two forbidden patterns. Acceptance: the joint extremal count equals one, the two-edge-star-free extremal count is \(\lfloor n/2\rfloor\), and a star gives linear growth when only \(2K_2\) is forbidden. A separate source-adjudication task must specify any revised restricted problem before treating it as OPEN.

Sources and claim boundaries

The literal conjecture is false; the unspecified surviving variant is open. No new theorem or protected editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1449 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider 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