Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be the maximum number of different sizes of cliques that can occur in a graph on vertices. Estimate - in particular, is it true that
where is the number of iterated logarithms such that .
Source: erdosproblems.com/927
An accepted solution exists. The statement is false.
The site labels the problem DISPROVED (LEAN); its Lean clause is
treated under Formalization. The refuting paper is Spencer's [Sp71] (Israel J.
Math. 9 (1971), 419--421; a refereed journal): with a clique a maximal complete
subgraph and all logarithms to the base , "for sufficiently large
( will do) " (p. 419; paged at
Spencer 1971, Main bound (p. 419)).
Its result is also attested in print by Erdős himself, in the note added in
proof to item 10 of his 1971 problem list ([Er71], printed p. 101: "Spencer
proved ", where the paper's is this page's
), and the site's curator, Thomas Bloom, accepts it, crediting Spencer
with . With the upper bound of Moon and Moser,
for ([MoMo65], Theorem 4, printed p. 27; paged at
Moon and Moser 1965, Theorem 4 (p. 27);
its claim page (Moon and Moser, 1965)),
this gives , the site's estimate. The constant is the
paper's headline as printed; the construction's own counts realize only
clique sizes in the third of its three cases, the window
, and or better elsewhere, so
what the printed argument delivers for every is
(authored, from the two printed bounds,
the card's counts and the integrality of ); any fixed constant refutes the
conjecture. The bracket in the paper's closing bounds is undefined
in print, and the card records the reading the counts fix (a filing observation,
not a review verdict). The Lean file named in the site's discussion thread
encodes a construction with along a sequence
of (Formalization). The claim page is
Spencer
(accepted on the refereed publication, Erdős's attestation and the site's
acceptance); the bounds of
Moon and Moser
and of
Erdős 1966 are
accepted partial claims on the estimate. The Lean developments that declare
themselves formalizations of his disproof, the gist of June 2026 and the
lean-proofs copy that formal-conjectures names, are formalization links on
that page, not built by this project, and add no evidence. The frontmatter is
derived from it; the label's Lean clause is a separate matter (Formalization).