Erdős Problem #775
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory, hypergraphs.
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
Can a 3-uniform hypergraph on \(n\) vertices have maximal cliques of almost every possible size, missing only a fixed number of sizes? Here each edge contains three vertices. A vertex set is complete when every triple of its vertices is an edge, and a maximal clique is a complete set that cannot be enlarged while remaining complete. Counting all complete subsets instead of maximal ones would make this a different problem.
Erdős asked for \(n-O(1)\) distinct maximal-clique sizes. The conjectured existence is DISPROVED by Jun Gao. An external Lean proof has been reported, but GCL has not replayed that certificate.
A small example
Consider the complete 3-uniform hypergraph on the vertex set \(\{1,2,3,4\}\): all four triples are edges. Every subset is complete, but only the full four-vertex set is inclusion-maximal. Consequently there is one maximal-clique size, namely four, rather than four different sizes.
In the empty 3-uniform hypergraph on four vertices, each pair is vacuously complete, and adding any third vertex makes an incomplete triple. Thus every maximal clique has size two. There are many maximal cliques, but still only one size. The distinction between the number of cliques and the number of distinct sizes is essential.
What is known
Jun Gao, On cliques in hypergraphs, arXiv:2510.14804v3 (2025), Theorem 1.1 on p. 1, proves a stronger statement for every fixed uniformity \(k\geq3\): for every fixed integer \(C\geq0\), all sufficiently large \(k\) uniform hypergraphs on \(n\) vertices have at most \(n-C\) different sizes of maximal cliques. Crucially, the lower threshold on \(n\) is allowed to depend on both \(k\) and \(C\). This says the number of missing sizes grows without bound as \(n\) grows.
Equivalently, for fixed \(k\geq3\) there is a function \(f_k(n)\) tending to infinity such that the number of distinct maximal clique sizes is at most
$$
n-f_k(n).
$$
The theorem does not itself license a particular numerical rate for \(f_k(n)\). Erdős's earlier construction obtained at least \(n-\log_*n\) different sizes, where \(\log_*n\) counts successive applications of the \logarithm needed to reach a bounded value. That lower construction is compatible with Gao's qualitative obstruction. Gao's later journal article appeared in Journal of Combinatorial Theory, Series B 180 (2026), 84–93, DOI 10.1016/j.jctb.2026.07.001.
The contrast with ordinary graphs matters: for graphs, Moon–Moser and Spencer studied the related maximal-clique spectrum and its \logarithmic deficit. Gao's theorem specifically treats \(k\geq3\).
GCL's current state
The original authenticated RESULT/1 source return has historical disposition SOURCE_LOCK_READY. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.
Source interpretation and unresolved mathematical qualification: Gao's theorem excludes n-O(1) distinct clique-size spectra for all large n depending on k,C; external Lean status is not internal certification.
The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.
What remains
Use finite hypergraph enumeration to test the distinction between complete sets and inclusion-maximal complete sets for \(n\leq5\), including empty and complete hypergraphs. Check conventions for cliques smaller than \(k\). Independently review the full combinatorial proof, the latest journal theorem statement, and the external Lean source environment before recording any formal certification. Full editorial review, protected merge, and real-browser mathematics rendering are still pending.
Sources and claim boundaries
- Erdős problem #775, pinned status DISPROVED; original catalogue [Ga25] citation.
- J. Gao, On cliques in hypergraphs, arXiv:2510.14804v3, Theorem 1.1, p. 1; Journal of Combinatorial Theory, Series B 180 (2026), 84–93, DOI.
- Authenticated GCL source return. No GCL Lean replay, protected admission, or deployed-browser verification.
Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2046 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.