Erdős Problem a Daythe open tracker

Erdős Problem #611

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).

`AllMaximalCliquesAtLeast G k` means that every maximal clique of `G` has at least `k` vertices.

`cliqueThreshold c n` is \(k_c(n)\): the least \(k\) such that every graph on \(n\) vertices whose maximal cliques all have at least \(k\) vertices satisfies \(\tau(G) < (1 - c)n\). For large \(n\) only \(k \geq 2\) matters, since some triangle-free graph has \(\tau(G) \geq (1 - c)n\); so ignoring maximal cliques on one vertex does not change \(k_c(n)\) asymptotically.

For a graph \(G\) let \(\tau(G)\) denote the minimal number of vertices that include at least one from each maximal clique of \(G\). Is it true that if all maximal cliques in \(G\) have at least \(cn\) vertices then \(\tau(G) = o_c(n)\)? Here \(n\) is the number of vertices, and \(o_c(n)\) is uniform over all such graphs on \(n\) vertices. \(\tau(G)\) is `SimpleGraph.cliqueTransversalNumber`, which (as in Erdős Problem 151) ignores maximal cliques on one vertex; this makes no difference here, since for large \(n\) every maximal clique has at least \(cn \geq 2\) vertices.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 3 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/611.
Prizenone
Topicsgraph theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/611
EARLY RUN BY THIS SITE · JUL 26, 2026

Open — a related variant was solved by others (Joret–Micek–Reed–Smid) while we worked it.

NO PROGRESS