Erdős Problem #835
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: verifiable (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
The Johnson graph records whether equal-size subsets differ in precisely one element. A coloring of this graph encodes the older problem of using all colors on the k-subsets of every (k+1)-set. The known obstruction leaves prime-minus-one parameters as open candidates.
Does there exist k>2 with chi(J(2k,k))=k+1 where Johnson graph vertices are k-element subsets of [2k] and adjacent when intersection size k-1? The original coloring formulation asks that each (k+1)-vertex underlying set has all k+1 colors across its k-subsets. The lower bound k+1 follows from its (k+1)-cliques, but the existence question remains unresolved for potential k=p-1 where p is prime.
A small example
For k=2, J(4,2) is line graph of K4, and its chromatic number is three by 3-coloring the six edges in three disjoint matchings. Any three underlying elements give three mutually adjacent two-sets. For k=3, a four-element subset gives a clique of four in J(6,3), but this only proves chi>=4, not strict >4.
This finite calculation is not an asymptotic or all-parameter proof.
What is known
Maintained /latex/835 read 2026-10-14. It reports explicit negative computations for 3<=k<=8 and Ma–Tang proved chi(J(2k,k))>k+1 for all k>2 NOT of the form prime-minus-one. This leaves infinitely many candidate k=p-1 with p prime (not all automatically solved), and excludes many small ones separately. Registry special VERIFIABLE is NOT proof of the full existential claim. Exact source for 'this website' computed chromatic numbers and Ma–Tang paper requires source lock.
Fixing a (k+1)-element underlying set S creates k+1 distinct k-subsets. Every two differ by one element, forming a clique in the Johnson graph and forcing at least k+1 colors. For k=2, J(4,2) is the line graph of K4 and admits a three-coloring corresponding to the three perfect matchings. Ma–Tang's source-reported theorem excludes k>2 unless k+1 is prime; the necessity of primality does not prove sufficiency.
GCL's current state
The original authenticated RESULT/1 source return has historical disposition STATUS_CONFLICT. 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: Johnson-graph coloring lower and Ma-Tang prime-minus-one necessary condition do not certify the existence of k>2; candidate prime cases remain.
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
Implement Johnson-graph adjacency and exact k2 three-color assignment; if feasible finite chromatic backtracking at k3. Locate primary Ma–Tang result and computed k3..k8 data, avoid declaring the full problem solved.
The original primary mathematical proofs, quantified status, finite definitions and deployed rendering must be independently checked before protected admission. No such admission is claimed here.
Sources and claim boundaries
- Maintained Erdős problem #835, LaTeX/bibliography and authenticated issue source return, checked 14 October 2026.
- Pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml. Original papers and unresolved proof obligations are identified in the source comment.
- Critical review: PENDING. Protected publication: NONE. Deployed MathJax: NOT VERIFIED. GCL theorem certification: NONE.
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: #2106 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.