Erdős Problem #780
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: combinatorics, hypergraphs, chromatic number.
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
Suppose all \(r\) element subsets of an \(n\) element set are assigned one of \(t\) colours. How large must \(n\) be to guarantee that one colour contains \(k\) pairwise disjoint \(r\) element subsets?
The exact answer is known. The threshold is
This is a generalized Kneser-colouring theorem, proved by Noga Alon, Peter Frankl and László Lovász in 1986. The classical Kneser graph corresponds to the special case \(k=2\); the general problem permits larger monochromatic disjoint families.
A small example
Take \(k=r=t=2\). The statement says that when \(n\geq5\), any red/blue colouring of the edges of \(K_n\) contains two disjoint edges of the same colour. At \(n=4\) this can fail. Put the vertices in groups \(X_0=\{1,2,3\}\) and \(X_1=\{4\}\). Colour every edge within \(X_0\) red, and each edge incident to 4 blue. The red edges form a triangle, so no two are disjoint; the blue edges form a star, so no two are disjoint either.
This example proves that the 5-vertex threshold cannot be lowered. It does not prove the upper theorem for all parameters.
What is known
The exact original statement is Theorem 1.1 on printed p. 359 of N. Alon, P. Frankl and L. Lovász, The chromatic number of Kneser hypergraphs, Transactions of the American Mathematical Society 298 (1986), 359–370. They prove that for positive integers \(r,t\) and \(k\geq2\), if \(n\geq kr+(t-1)(k-1)\), every partition of the \(r\) subsets into \(t\) families contains \(k\) pairwise disjoint members in one family.
The source immediately demonstrates sharpness. At one vertex fewer,
split the ground set into \(X_0\) of size \(kr-1\) and \(X_1,\ldots,X_{t-1}\) each of size \(k-1\). Colour an \(r\) set 0 if it lies completely in \(X_0\); otherwise give it the smallest positive colour \(i\) for which it intersects \(X_i\). In colour 0, \(k\) disjoint sets would need at least \(kr\) vertices inside \(X_0\), one more than is available. In each positive colour \(i\), \(k\) disjoint sets would require \(k\) distinct vertices from \(X_i\), while only \(k-1\) exist.
This verifies the lower-bound example directly. The opposite implication at the threshold is nontrivial and uses a topo\logical generalization of Lovász's proof of the Kneser conjecture. The original paper explicitly credits the Bárány–Shlosman–Szűcs extension of the Borsuk–Ulam theorem.
There is a minor but important indexing issue in the maintained catalogue's sharpness description: the partition should start with \(X_0\) and end with \(X_{t-1}\), as the original printed paper does. Otherwise the first block label is accidentally repeated.
GCL's current state
The authenticated original RESULT/1 source return records SOURCE_LOCK_READY and preserves its issue-bound mathematical source observations. This explanatory article is REVIEWED under the exact-hash EC-BULK-005-R6 editorial transaction, subject to the protected merge of PR #2676. Its original source-audit status is retained. Editorial acceptance and public MathJax validation do not certify any original research theorem, external Lean file, or complete historical proof.
Unclosed mathematical proof/source qualifications: FULL_TOPOLOGICAL_UPPER_PROOF_NOT_REPLAYED; INDEPENDENT_CRITICAL_REVIEW_PENDING.
What remains
Verify the \((k,r,t)=(2,2,2)\) obstruction by exhaustive edge-colouring, then check that all 2-colourings of the 5-vertex \(r=2\) case contain a same-colour matching of size two. Preserve the primary theorem's parameter order and X-block indexing. Editorial review and a baseline public-rendering audit are recorded; independent full-primary-proof validation remains separate.
For mathematical proof certification, the complete primary argument and any external formalization must undergo separate independent replay. The bounded finite calculation is recorded in the governed R6 fixture; editorial approval does not discharge the outstanding research obligations.
Sources and claim boundaries
- N. Alon, P. Frankl, L. Lovász, The chromatic number of Kneser hypergraphs, Transactions AMS 298 (1986), 359–370; DOI, Theorem 1.1 and sharpness construction, printed p. 359.
- Maintained Erdős #780; authenticated source return #2051. No new theorem certification is claimed; editorial acceptance is submitted through protected R6 PR #2676.
- Editorial decision: exact-hash reviewed explanatory article, protected R6 transaction. Mathematical theorem proof / external Lean certification: NOT CLAIMED. The original SOURCE_LOCK_READY return, primary-source attribution, and proof-review holds remain.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2051 — 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.