Skip to content

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

\[ n\geq kr+(t-1)(k-1). \]

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,

\[ n=kr-1+(t-1)(k-1), \]

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

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.

Back to catalogue · Compendium introduction