Skip to content

Erdős Problem #80

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey 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

Imagine a dense graph where every edge lies in at least one triangle. Must some edge lie in many triangles? Triangles sharing an edge form a book. For a fixed \(c>0\), Erdős #80 asks how large a book can always be guaranteed in an \(n\) vertex graph with at least \(cn^2\) edges and every edge in a triangle.

Writing \(f_c(n)\) for the largest universally guaranteed number of pages, the historical questions include whether \(f_c(n)>n^\varepsilon\) for some \(\varepsilon>0\), or at least whether \(f_c(n)\) is bounded below by a positive multiple of \(\log n\).

A small example

Every edge of the complete graph \(K_5\) belongs to exactly three different triangles: choose the third vertex among the other three. Thus the largest book in \(K_5\) has three pages. In a graph with triangles whose edges are used only once, the largest book may instead be one page.

The essential additional condition is that every edge belongs to a triangle. Mere existence of many triangles without that quantifier gives a different extremal problem. The density \(c\) is fixed independently of \(n\), and the interesting sparse-dense regime is \(0<c<1/4\).

What is known

The general estimation problem remains OPEN, but the proposed polynomial lower bound has been DISPROVED for every fixed \(c<1/4\). Jacob Fox and Po-Shen Loh, On a problem of Erdős and Rothschild on edges in triangles, Combinatorica 32 (2012), 619–628, establish the primary upper-bound construction

\[ f_c(n)\le n^{O_c(1/\log\log n)}. \]

This grows slower than every fixed positive power of \(n\). Their manuscript abstract explicitly describes the result as a negative answer to the 1987 question of Erdős. By contrast, for \(c>1/4\), the classical Edwards and Khadzhiivanov–Nikiforov theorem guarantees an edge in at least \(n/6\) triangles. Szemerédi's regularity lemma implies \(f_c(n)\to\infty\) for fixed \(c>0\), but the best general quantitative lower bound at fixed \(c<1/4\) is weak. The stated logarithmic lower-bound question remains open.

GCL's current state

GCL checked Fox–Loh's author-manuscript abstract, including its universal edge-in-triangle hypothesis and the strict \(c<1/4\) range. The pinned catalogue remains OPEN because estimating \(f_c(n)\) and the logarithmic lower bound are not settled. Original issue: #1349. The full proof of Fox–Loh's construction was not independently reproduced.

An authenticated RESULT/1 source report is posted on the original issue. It is unadjudicated source evidence, not independent proof certification or editorial admission.

What remains

A bounded computational task is to enumerate labelled graphs up to seven vertices and compute \(b(G)=\max_{uv\in E(G)}|N(u)\cap N(v)|\), rejecting graphs with an edge in no triangle. For each edge-density threshold, compute the minimum of \(b(G)\) over valid graphs. Acceptance: exact triangle counts and a witness for each extremal value; stop at the finite enumeration. Do not infer asymptotic \(\log n\) growth from these fixtures.

Sources and claim boundaries

No new upper or lower bound, full source-proof certification, or editorial acceptance is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1349 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
  • 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