Erdős Problem #1078
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
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.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Partition a graph's vertices into \(r\) disjoint classes, with exactly \(n\) vertices in each. Edges may join different classes but not vertices in the same class.
How large must the minimum vertex degree be to ensure that the graph contains a complete graph \(K_r\), with one vertex chosen from each class?
Erdős Problem #1078 asked whether a minimum degree of about
would suffice. The maximum possible degree is \((r-1)n\), since a vertex can join every vertex outside its own class.
A small example
Take \(r=3\) parts containing two vertices each. The complete tripartite graph \(K_{2,2,2}\) connects every vertex to all four vertices outside its class. Its minimum degree is \(4\) and it contains
triangles, one from each choice of three vertices, one per part.
Now remove every edge between the second and third classes, retaining edges from the first class to both others. No triangle remains, since a potential triangle would require an edge between the second and third classes. Vertices in those classes now have degree \(2\); those in the first class still have degree \(4\). This simple comparison illustrates why a global minimum-degree condition, rather than merely a large total number of edges, is relevant.
What is known
The conjectured sufficient threshold is proved. The maintained catalogue attributes the affirmative result to Haxell (2001). A later paper by Haxell and Szabó (2006) determined a sharper threshold, expressed in the catalogue with an integer ceiling:
The equality/strictness convention and exact small‑\(r\) hypotheses of this sharper expression require checking against the original theorem rather than inferring a finite-n statement from the catalogue synopsis.
GCL's current state
Authenticated source audit #2349 identifies the proved status, the historical sources and the difference between a sufficient asymptotic threshold and a sharp integer threshold. It independently verifies the small complete-tripartite and triangle-free examples.
The pinned formal-conjectures snapshot contains no protected statement for #1078. GCL has not reconstructed Haxell's proof or independently adjudicated the exact endpoint convention.
What remains
The remaining editorial task is to read the 1975 conjecture and the 2001 and 2006 proofs page by page, verifying the range of \(r\), the rounding, equality versus strict inequality and explicit extremal constructions. Small multipartite cases can be checked with exhaustive graph enumeration, but they do not certify the entire theorem.
Sources and claim boundaries
- Erdős Problem #1078, proved status, threshold formula and historical references.
- B. Bollobás, P. Erdős and E. Szemerédi (1975), original multipartite-clique problem.
- P. Haxell (2001), affirmative solution; P. Haxell and T. Szabó (2006), sharp-threshold theorem.
- Authenticated GCL audit #2349.
The mathematical theorem is externally established, but this article has not passed GCL's final source-fidelity or protected editorial admission.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2349 — 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.