---

Claim. Problem 835 asks whether some $k>2$ admits a coloring of the $k$-subsets of $\{1,\ldots,2k\}$ with $k+1$ colors in which every $(k+1)$-subset sees all $k+1$ colors on the $k$-subsets it contains, which is to say whether $\chi(J(2k,k))=k+1$ for some $k>2$. Ma and Tang prove that no such $k$ has $k+1$ composite: for every $k>2$ with $k+1$ not prime, $\chi(J(2k,k))\ge k+2$ (Theorem 2.2 of the note). The argument takes a maximum independent set of $J(2k,k)$, which has at least $\binom{2k}{k}/(k+1)$ members when $\chi(J(2k,k))=k+1$; its members through a fixed $(k-t)$-subset give edge-disjoint copies of $K^{(t-1)}_t$ in the complete $(t-1)$-uniform hypergraph on the remaining $k+t$ points, and double counting against the trivial packing bound shows that the largest such packing has exactly $\binom{k+t}{t-1}/t$ copies, so $t$ divides $\binom{k+t}{t-1}$ for every $1\le t\le k$ (Proposition 2.1). Theorem 2.2 then takes a prime divisor $p\le(k+1)/2$ of $k+1$ and shows with Lucas's theorem that one of these divisibilities fails. The note is J. Ma and Q. Tang, A note on Erdős Problem #835, an undated manuscript posted in the site's discussion thread on 31 December 2025 and revised on 1 January 2026; the link above is pinned to the revision.

Submission note. Posted to the site's forum by Quanyu Tang on 31 December 2025:

Jie Ma and I wrote a short note on this problem. We prove that if $k>2$ and $k+1$ is not prime, then $\chi(J(2k,k))\neq k+1$.

To fully resolve this problem, one may need to investigate the existence of a large set of Steiner system $S(2k,k,k−1)$.

(The site has been updated to address this comment.)

Covers. Every $k>2$ with $k+1$ composite, which includes every odd $k>2$. For these $k$ the answer to the question is no. Not covered: the $k$ with $k+1$ prime, among them $k=4$ and $k=6$, which Brouwer's table of Johnson-graph chromatic numbers excludes separately, as the problem page records.

Depends on. No page of this wiki.

Acceptance. None recorded. The site's commentary credits Ma and Tang with the result, and the site's curator, Thomas Bloom, replied in the thread on 31 December 2025 that the note looked good, regretting that it leaves the case $k+1$ prime open; the site labels the problem VERIFIABLE, an open label, so this commentary is not an acceptance of the claim. No journal or arXiv version of the note was found in a search. The formal-conjectures statement file, linked from the problem page, states the result as johnson_chromaticNumber_composite with a sorry body. The argument is not checked step by step here; nothing on this page is this project's own review.