Erdős Problem a Daythe open tracker
The board / graph theory / #573

Erdős Problem #573

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

\(\mathrm{ex}(n;\{C_k : k \in L\})\): the greatest number of edges of a simple graph on `n` vertices that contains no cycle \(C_k\) with \(k \in L\) as a (not necessarily induced) subgraph. `cycleGraph k` is the cycle on `Fin k`. The definition is meaningful only for sets `L` of lengths `k ≥ 3`, which are the only ones used below: `cycleGraph 0` and `cycleGraph 1` have no edges, and `cycleGraph 2` is a single edge.

Is it true that \[\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?\] A problem of Erdős and Simonovits. This problem is asking whether the threshold is the same as for forbidding \(C_4\) and all odd cycles (see `erdos_573.variants.kst`) if one only forbids the odd cycle of length \(3\). See also [574] for the general case, and [765] for \(\mathrm{ex}(n;C_4)\). This problem is #48 in Extremal Graph Theory in the graphs problem collection.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/573.
Prizenone
Topicsgraph theory, turan number
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA006856
Original pageerdosproblems.com/573

Attempts

submit one →
WORKING REPORT BY THIS SITE · JUL 28, 2026

Read our working report →

independently proved and reverified the exact table \(f(n)=0,1,2,3,5,6,8,10,12,15,16,18,21,23,26\) for \(1\leq n\leq15\); the asymptotic factor-\(\sqrt2\) upper-bound gap remains.

PARTIAL
← #572the board#574 →