Erdős Problem #80

The question

Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $c{n}^2$ edges, where each edge is contained in at least one triangle, must contain a book of size $m$, that is, an edge shared by at least $m$ different triangles. Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{ϵ}$ for some $ϵ>0$?

The bound $c<1/2$ is what makes the hypothesis satisfiable: a simple graph on $n$ vertices has at most $n(n-1)/2$ edges, so no graph has $c{n}^2$ of them once $c\ge 1/2$.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«80». answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem erdos_80 :
    answer(sorry) ↔ ∀ c : ℝ, 0 < c → c < 1 / 2 →
      ∃ ε > (0 : ℝ), ∀ᶠ n : ℕ in atTop, (n : ℝ) ^ ε < f c n

What counts as progress

• A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already — check erdosproblems.com/80. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

Variants

• erdos_80.variants.log — The weaker question from the same problem: is f_c(n) ≫ log n? Same feasibility bound on c as above.

References

• erdosproblems.com/80
• erdosproblems.com/600, stated in FormalConjectures/ErdosProblems/600.lean

600 asks the same question from the other side. Erdos600.eFunction n r is the least edge count forcing some edge into r triangles; f c n here is the largest book forced once the edge count is at least $c{n}^2$. So r ≤ f c n and Erdos600.eFunction n r ≤ c * n^2 say the same thing, and the two functions are inverse to each other in that sense. Both are built on SimpleGraph.trianglesContaining, which 600 introduced.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.