Erdoes #835 - working report - Erdős Problem a Day

Erdős problem 835 — wave 7o

Audit date: 2026-07-27 UTC Live page: <https://www.erdosproblems.com/835> Re-verifier: runs/erdos835_wave7o_reverify.py

0. Mandatory live-page gate

I fetched the live page through the Bright Data browser route, rather than using the stale tracker YAML or a direct datacenter request.

Verbatim current statement

Does there exist a $k>2$ such that the $k$-sized subsets of $\{1,\ldots,2k\}$ can be coloured with $k+1$ colours such that for every $A\subset \{1,\ldots,2k\}$ with $\lvert A\rvert=k+1$ all $k+1$ colours appear among the $k$-sized subsets of $A$?

Status and collaboration fields seen on the live page

Status badge: VERIFIABLE, expanded by the page as “Open, but could be

proved with a finite example.”

The page carries its standard open-status disclaimer.
Claimed proofs: 0.
Currently working: None.
Interested in collaborating: Quanyu_Tang, eigensolver.
Formalised: Yes.
The page showed seven comments and explicitly said that no partial or

complete solution was claimed in them.

The page showed one like, from joriki.
The problem entry was shown as last edited on 2026-01-22.

Thus the user-specified stop condition did not fire: there is neither a claimed solution nor a current worker.

Known-results text on the page

The page attributes the problem to Erdős and Rosenfeld, says that $k=2$ is trivial and that they were unsure about $k=6$, and records the following equivalent formulation:

This is equivalent to asking whether there exists $k>2$ such that the chromatic number of the Johnson graph $J(2k,k)$ is $k+1$ (it is always at least $k+1$ and at most $2k$). The chromatic numbers listed at this website show that this is false for $3\leq k\leq8$.

It then records the Ma–Tang result:

Ma and Tang have proved that the chromatic number of the Johnson graph $J(2k,k)$ is $>k+1$ for all $k>2$ not of the form $p-1$ for prime $p$.

The source tag on the page is [Er74d, p.283].

All seven live comments

These are observations from the discussion page, not accepted results; the site itself warns that comments are unverified.

eigensolver, 2025-12-31. Relates the independence number of

$J(n,k)$ to the constant-weight-code number $A(n,4,k)$, reports that code tables rule out $3\leq k\leq14$, and initially proposed a recursive Johnson-bound computation through $k=500$. An edit explicitly retracts the latter inference because of floating-point precision and says that the recursive bound fails for most prime $k+1$. The comment points to Jørgensen's Sections 4.5 and 5.5 and suggests looking for a large set.

Quanyu Tang, 2025-12-31. Links the short Ma–Tang note proving the

composite-$k+1$ obstruction and also suggests the large-set formulation.

Thomas Bloom, 2025-12-31. Notes that there appears to be little useful

lower-bound literature and records the original source.

YaelDillies, 2026-01-26. Reports a formal/AlphaProof route that first

handled $k=9$ and then the general composite-$k+1$ case through the recursive Johnson bound. This is not a proof of the full problem.

edkirkby, 2026-03-14. Gives a Walsh–Hadamard argument that, for even

$k$, every colour class is closed under complementation.

athvedt, 2026-05-21. Identifies each colour class as an

$S(k-1,k,2k)$, hence the colouring as a large set. It derives $S(4,5,15)$ from $k=10$ and $S(4,5,17)$ from $k=12$, citing their nonexistence, and identifies $k=16$ and $S(4,5,21)$ as the first open barrier.

KentaKitamura, 2026-05-30. Gives an independent complement-pair

argument using the Hoffman bound/Johnson scheme, with references to Ma–Tang, Abiad–Bosma–van Veluw, and Brouwer et al.; the comment includes an AI-assistance disclosure.

1. Verified outcome

I use the labels requested in the task:

(a) elementary-rigorous;
(b) rigorous modulo the explicitly named theorem;
(c) plausible/structural-unverified;
(d) computational-only.

The concrete progress is:

(a) A requested colouring is exactly a large set

$\operatorname{LS}(k-1,k,2k)$.

(a) A short inclusion–exclusion identity proves from scratch that an

$S(k-1,k,2k)$ cannot exist for odd $k>1$, while for even $k$ every block occurs together with its complement.

(a) For every even $k$, there is a reversible reduction

\[ \operatorname{LS}(k-1,k,2k) \quad\Longleftrightarrow\quad \operatorname{LS}(k-2,k-1,2k-1). \] The inverse map is explicit and is checked by a second inclusion–exclusion identity.

(a) Repeated derivation then gives the necessary condition

\[ \operatorname{LS}(4,5,k+5) \] for every candidate $k\geq6$. It has exactly $k+1$ constituent Steiner systems.

(a) The Ma–Tang composite-$k+1$ obstruction has a two-line

from-scratch proof using the replication number of a Steiner system; no black-box theorem is needed for that obstruction here.

(d) An exact-cover enumeration finds all 30 labelled

$S(2,3,7)$'s. Their disjointness graph is 8-regular with 120 edges and no triangle, so its clique number is 2. This independently rules out $k=4$, for which five mutually disjoint systems would be required.

(b), corroborated by (d) Kramer–Mesner prove that at most two

$S(4,5,11)$'s can be mutually disjoint, ruling out $k=6$, for which seven are needed. Independently, the verifier constructs the Witt design, generates its 5,040 labelled relabellings, and obtains a 144-regular disjointness graph with 362,880 edges and no triangle. Completeness of that orbit as a list of all systems uses the named uniqueness theorem for the Witt $S(4,5,11)$.

(b) Nonexistence of $S(4,5,15)$ and $S(4,5,17)$ rules out

$k=10$ and $k=12$, respectively.

Consequently (a)+(b)+(d) every $3\leq k\leq15$ is impossible. The first value not excluded is $k=16$, where a solution would force the still-open large set $\operatorname{LS}(4,5,21)$, and in particular an $S(4,5,21)$. This does not solve the uniform existence question.

2. Large-set formulation

Write $S(t,b,v)$ for a family of $b$-subsets (“blocks”) of a $v$-set in which every $t$-subset lies in exactly one block. Write $\operatorname{LS}(t,b,v)$ for a partition of all $b$-subsets into such systems.

Proposition 1 — exact equivalence (a)

The colouring in the problem exists if and only if $\operatorname{LS}(k-1,k,2k)$ exists.

Proof. Fix a $(k-1)$-set $T$. Exactly $k+1$ $k$-sets contain it, obtained by adding one of the remaining $k+1$ points. Any two of these sets are $k$-subsets of the same $(k+1)$-set, so the problem's condition gives them all $k+1$ colours. Therefore each colour contains exactly one block over $T$, and each colour class is an $S(k-1,k,2k)$. The classes partition all $k$-sets.

Conversely, in a partition into $k+1$ such systems, the $k+1$ different $k$-subsets of any fixed $(k+1)$-set pairwise share a $(k-1)$-set. No two can lie in one constituent Steiner system. There are $k+1$ systems, so all colours occur exactly once. $\square$

This also directly proves the Johnson-graph equivalence: adjacency in $J(2k,k)$ means intersection size $k-1$, equivalently that the two vertices are $k$-subsets of their common $(k+1)$-element union.

3. Two elementary obstructions

Proposition 2 — composite $k+1$ (a)

If $k+1$ is composite, even a single $S(k-1,k,2k)$ is impossible.

Proof. In an $S(k-1,k,2k)$, the number of blocks containing a fixed $i$-set is

\lambda_i =\frac{\binom{2k-i}{k-1-i}}{\binom{k-i}{k-1-i}} =\frac{\binom{2k-i}{k-i}}{k+1}.

Let $p$ be a prime divisor of the composite number $k+1$. Then $p\leq k$. Putting $i=k-p$ in the first expression gives

\lambda_{k-p}=\frac1p\binom{k+p}{p-1}.

Since $k\equiv-1\pmod p$,

\binom{k+p}{p-1} =\frac{(k+2)(k+3)\cdots(k+p)}{(p-1)!} \equiv\frac{1\cdot2\cdots(p-1)}{(p-1)!} \equiv1\pmod p.

Thus $\lambda_{k-p}$ is not an integer, a contradiction. $\square$

This is the Ma–Tang obstruction reproduced from first principles. The standalone script also recomputes

t\mid\binom{k+t}{t-1}\quad(1\leq t\leq k)

through $k=100$, finding exactly the values for which $k+1$ is prime. That finite check is (d); the proof above is the uniform (a) result.

Proposition 3 — complement identity (a)

Let $\mathcal C$ be an $S(k-1,k,2k)$, and fix a $k$-set $X$. Put

x=\mathbf 1_{\{X\in\mathcal C\}},\qquad y=\mathbf 1_{\{X^c\in\mathcal C\}}.

Then

y=\frac{1-(-1)^k}{k+1}+(-1)^k x. \tag{1}

Consequently:

if $k>1$ is odd, no $S(k-1,k,2k)$ exists;
if $k$ is even, $X\in\mathcal C$ exactly when

$X^c\in\mathcal C$.

Proof. Inclusion–exclusion counts the blocks disjoint from $X$:

y=\sum_{i=0}^{k-1}(-1)^i\binom{k}{i}\lambda_i+(-1)^kx.

Using the expression for $\lambda_i$ above, the required finite sum follows from

\begin{aligned} \sum_{i=0}^{k}(-1)^i\binom{k}{i}\binom{2k-i}{k-i} &=[z^k]\sum_{i=0}^{k}(-1)^i\binom{k}{i} z^i(1+z)^{2k-i}\\ &=[z^k](1+z)^k=1. \end{aligned}

Removing the $i=k$ term and dividing by $k+1$ gives $(1-(-1)^k)/(k+1)$, proving (1). For odd $k>1$, its right side cannot be the integer $y$; for even $k$, it says $y=x$. $\square$

4. A reversible one-point reduction

Theorem 4 (a)

For even $k$,

\operatorname{LS}(k-1,k,2k) \quad\Longleftrightarrow\quad \operatorname{LS}(k-2,k-1,2k-1). \tag{2}

Forward map. Choose a point $\infty$. In every constituent $S(k-1,k,2k)$, retain the blocks containing $\infty$ and delete $\infty$. This is its derived $S(k-2,k-1,2k-1)$. Since the original systems partition all $k$-sets, the derived systems partition all $(k-1)$-sets on the other $2k-1$ points.

Explicit inverse map. Let $D$ be an $S(k-2,k-1,2k-1)$ on $V$, and add a new point $\infty$. Define

E(D)= \{B\cup\{\infty\}:B\in D\} \ \cup\ \{V\setminus B:B\in D\}. \tag{3}

Then $E(D)$ is an $S(k-1,k,2k)$.

Subsets containing $\infty$ are covered exactly once by the first half of (3). For a $(k-1)$-set $A\subseteq V$, put $r=k-1$, let $x=\mathbf1_{\{A\in D\}}$, and let $y$ be the number of blocks of $D$ disjoint from $A$. The same inclusion–exclusion calculation now uses

\lambda_i =\frac{\binom{2r+1-i}{r-i}}{r+2} \quad(0\leq i<r)

and

\begin{aligned} \sum_{i=0}^{r}(-1)^i\binom ri\binom{2r+1-i}{r-i} &=[z^r](1+z)^{r+1}\\ &=r+1. \end{aligned}

Here $r$ is odd. Removing its $i=r$ term gives

\[ y=1-x. \]

Thus exactly one of $A\cup\{\infty\}$ and a complement block covers $A$. So (3) is a Steiner system.

Finally, if the lower systems partition all $(k-1)$-sets, their extensions partition both kinds of $k$-sets: $B\cup\{\infty\}$ is assigned with $B$, while a $k$-set $C\subseteq V$ is assigned with its unique complement $V\setminus C$. This proves the reverse implication in (2). The complement lemma shows at the same time that these forward and reverse maps are mutual inverses. $\square$

5. The hereditary obstruction and the first wall

Corollary 5 (a)

Deriving every constituent system at a fixed point takes

\operatorname{LS}(t,b,v) \longrightarrow \operatorname{LS}(t-1,b-1,v-1)

and preserves the number of constituent systems. Applying this $k-6$ times after (2) gives, for every even candidate $k\geq6$,

\operatorname{LS}(k-1,k,2k) \Longrightarrow \operatorname{LS}(4,5,k+5). \tag{4}

The latter contains $k+1$ mutually disjoint $S(4,5,k+5)$'s and partitions all 5-subsets.

The exclusions now line up as follows:

$k$	obstruction	classification
odd $k>2$	Proposition 3 (also covered by composite $k+1$)	(a)
$k+1$ composite	Proposition 2	(a)
$4$	$\operatorname{LS}(2,3,7)$ would need 5 systems; exact maximum is 2	(d)
$6$	$\operatorname{LS}(4,5,11)$ would need 7 systems; exact maximum is 2	(b), independently mirrored by (d)
$10$	(4) would contain an $S(4,5,15)$, which does not exist	(b)
$12$	(4) would contain an $S(4,5,17)$, which does not exist	(b)
$16$	requires $\operatorname{LS}(4,5,21)$; even one $S(4,5,21)$ is open	unresolved

Therefore every $3\leq k\leq15$ is excluded. This extends the live page's listed small-case range with an independently checkable chain.

For $k=16$, the exact reduction is

\operatorname{LS}(15,16,32) \Longleftrightarrow \operatorname{LS}(14,15,31) \Longrightarrow \operatorname{LS}(4,5,21). \tag{5}

The last arrow is only one-way. Finding a single $S(4,5,21)$, or even an $\operatorname{LS}(4,5,21)$, would not by itself solve problem 835: one would still need a compatible chain of simultaneous extensions

\operatorname{LS}(4,5,21)\to \operatorname{LS}(5,6,22)\to\cdots\to \operatorname{LS}(14,15,31).

No such extension theorem was located. This is the exact missing uniformity step, and it is why the report does not promote the necessary large-set condition to a solution.

6. Exact small-case computation

All code is in the standalone, standard-library-only verifier. It is deterministic and takes under ten seconds on this VM.

$k=4$ (d)

The script formulates $S(2,3,7)$ as an exact-cover problem:

21 pair constraints;
35 candidate triples;
each solution has 7 triples.

It recursively chooses an uncovered pair with the fewest compatible triples. It enumerates exactly 30 distinct labelled systems and validates every pair count in every output. It then constructs the full graph whose vertices are these systems and whose edges join block-disjoint systems. The graph has

|V|=30,\qquad |E|=120,\qquad \deg=8,

and the script checks every edge for a common neighbour. None has one, so there is no triangle; because edges exist, the clique number is exactly 2. An $\operatorname{LS}(2,3,7)$ would be a clique of size 5.

$k=6$ (d), with completeness (b)

The verifier develops these six starters modulo 11:

01239  01247  01256  01348  01357  01469

Their 66 translates are checked directly to form an $S(4,5,11)$. Adjacent transpositions generate its entire relabelling orbit:

|{\cal O}|=5040=\frac{11!}{7920}.

Every one of the 5,040 images is rechecked from its 4-subset incidences. Their disjointness graph has

|E|=362{,}880,\qquad \deg=144,

and again no edge has a common neighbour, so its clique number is 2. The assertion that this orbit contains every $S(4,5,11)$ uses the classical uniqueness of the small Witt design; independently, Kramer–Mesner's named theorem directly states the maximum-disjoint-family result.

The verifier also applies the explicit inverse (3) to one $S(2,3,7)$ and to the displayed $S(4,5,11)$, then recounts every required subset to verify the resulting $S(3,4,8)$ and $S(5,6,12)$ from scratch.

Reproduction

cd /home/exedev/MathDyad
python3 runs/erdos835_wave7o_reverify.py

Observed output:

binomial identities: verified for parameters <= 50
k=2 explicit colouring: verified
k=4 lower systems: 30 labelled S(2,3,7), 120 disjointness edges, clique number 2
k=6 lower systems (modulo uniqueness of S(4,5,11)): 5040 labelled copies, 362880 disjointness edges, clique number 2
explicit complement extensions for k=4 and k=6: verified
Ma--Tang divisibility passers through k=100: [2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100]
cyclic S(4,5,21) quotient (4-orbits, 5-orbits, suitable columns, min degree, max degree): (285, 969, 954, 14, 17)
full LS(4,5,21) direct encoding: 345933 variables, 122094 exact-one groups, 16604784 pairwise at-most-one clauses
equivalent LS(14,15,31) direct encoding: 5109183315 variables, 4808643120 exact-one groups, 653975464320 pairwise at-most-one clauses
original 17-colour incidence encoding: 10218366630 variables
ALL CHECKS PASSED

7. Literature audit

The following are the primary sources actually checked. No arXiv identifier or paper below is inferred from a secondary citation.

Original source. Claude Berge and Dijen Ray-Chaudhuri,

“Unsolved problems”, pp. 278–287 in Hypergraph Seminar, Lecture Notes in Mathematics 411 (1974); the question is on p. 283 and is attributed there to Erdős and Rosenfeld. The whole proceedings volume is indexed at <https://doi.org/10.1007/BFb0066173>.

Composite obstruction. Ma and Tang,

short note on problem 835. Its Proposition 2.1 gives $t\mid\binom{k+t}{t-1}$, Theorem 2.2 rules out composite $k+1$, and Lemma 2.3 observes that the divisibility test itself passes when $k+1$ is prime. Proposition 2 above independently proves the obstruction.

Johnson-graph context. Søren Fuglede Jørgensen,

“On the clique covering numbers of Johnson graphs,” arXiv:2502.15019. This is the [Jor25] linked from the live discussion; the relevant items are Proposition 4.5 and Theorem 5.5.

The $k=6$ disjointness theorem. Earl S. Kramer and Dale M. Mesner,

“Intersections among Steiner systems,” JCTA 16 (1974), 273–28590054-5). Its abstract explicitly states that the maximum number of mutually disjoint $S(4,5,11)$'s is two.

The $k=10$ obstruction. N. S. Mendelsohn and S. H. Y. Hung,

“On the Steiner systems $S(3,4,14)$ and $S(4,5,15)$”, Utilitas Mathematica 1 (1972), 5–95. The paper proves that no $S(4,5,15)$ exists. The bibliographic record is also reproduced in the later primary paper in item 6.

The $k=12$ obstruction. P. R. J. Östergård and O. Pottonen,

“There exists no Steiner system $S(4,5,17)$”, JCTA 115 (2008), 1570–1573, DOI. The paper describes an exhaustive search based on the classification of $S(3,4,16)$, with two independently generated seed sets. It explicitly identifies $S(4,5,21)$ as the next open quintuple-system parameter.

Current $S(4,5,21)$ status. Michael Kiermaier, Vedran Krčadinac,

and Alfred Wassermann, “Steiner 3-designs as extensions”, Designs, Codes and Cryptography 94, article 157 (published 2026-07-07); preprint arXiv:2509.23483. They report extensive extension searches with prescribed groups of order at least 10, finding no $S(4,5,21)$, but explicitly warn that this is “very little evidence” for nonexistence. This supports, rather than resolves, the wall.

A symmetry-restricted negative result. Y. M. Chee and D. L. Kreher,

“4-(21,5,$\lambda$) designs from a group of order 171”, Ars Combinatoria 36 (1993), 199–205. It excludes an $S(4,5,21)$ having a specified order-57 subgroup of their order-171 Frobenius group; it does not exclude an asymmetric system.

(c), search-negative only: Exact-title, parameter, citation, and forward citation searches found no construction or nonexistence proof for $S(4,5,21)$, no $\operatorname{LS}(4,5,21)$, and no later claimed solution of problem 835. A literature miss is not a theorem; the authoritative live page and the July 2026 Kiermaier–Krčadinac–Wassermann paper are the positive evidence for the stated current status.

8. Exact computational wall and cost

Smallest necessary projected model (a)

A direct Boolean encoding of $\operatorname{LS}(4,5,21)$ has a variable $x_{c,B}$ for each of 17 colours and each 5-set $B$:

17\binom{21}{5}=345{,}933\quad\text{variables}.

For every colour and 4-set, exactly one of its 17 containing 5-sets is chosen; for every 5-set, exactly one of its 17 colours is chosen. Hence there are

17\binom{21}{4}+\binom{21}{5}=122{,}094

exact-one groups, all of size 17. Naive pairwise at-most-one encoding alone has

122{,}094\binom{17}{2}=16{,}604{,}784

binary clauses. These counts are independently recomputed by the verifier.

A cyclic $S(4,5,21)$ restriction under $\mathbb Z_{21}$ reduces one constituent-system search to 285 four-set orbits and 969 five-set orbits. Of the latter, 954 do not internally repeat a four-set orbit; quotient constraint degrees range from 14 to 17. These are exact (d) counts from the verifier, but the restriction tests only cyclic systems. A negative answer there says nothing about asymmetric systems, and a positive single system would still be far short of a large set and of the extension tower in (5).

Direct model for what is actually equivalent (a)

The equivalent $\operatorname{LS}(14,15,31)$ model has

17\binom{31}{15}=5{,}109{,}183{,}315

Boolean incidence variables and

17\binom{31}{14}+\binom{31}{15}=4{,}808{,}643{,}120

size-17 exact-one groups. A pairwise encoding would already contain 653,975,464,320 binary at-most-one clauses. Encoding the original colouring without the reduction has

17\binom{32}{16}=10{,}218{,}366{,}630

incidence variables. These sizes make a naive direct run inappropriate on this VM.

The precise missing object is therefore not merely one quintuple system. It is either:

a proof that no $S(4,5,21)$ exists, which would rule out $k=16$; or
a compatible 17-way extension tower from

$\operatorname{LS}(4,5,21)$ to $\operatorname{LS}(14,15,31)$; or

a structural theorem that bypasses that tower and constructs or excludes

$\operatorname{LS}(14,15,31)$ directly.

A reasonable next pilot, not an estimated complete proof, would be a symmetry-aware exact-cover/SAT portfolio on the 345,933-variable projected large-set model, budgeted at roughly 1,000 core-hours. At an illustrative \$0.04–\$0.10 per core-hour this is about \$40–\$100. For scale, the current Google Cloud price sheet lists a two-vCPU c4-highcpu-2 instance at \$0.085052/hour in its default column, or about \$0.0425 per vCPU-hour; a vCPU is not necessarily a physical core, so the wider range is intentional. There is no defensible finite cost estimate for an unrestricted exhaustive proof: the 2008 $S(4,5,17)$ work depended on a classification that took years of CPU time, and both that paper and the 2026 extension study explain why the corresponding order-21 classification/low-symmetry cases evade the same machinery. I did not launch such a computation here.

PARTIAL: Proved an elementary complement/extension equivalence and a hereditary LS(4,5,k+5) obstruction, independently verified the k=4,6 exceptional cases, and isolated k=16 at the open LS(4,5,21) barrier; problem 835 remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger

\(k\)	obstruction	classification
odd \(k>2\)	Proposition 3 (also covered by composite \(k+1\))	(a)
\(k+1\) composite	Proposition 2	(a)
\(4\)	\(\operatorname{LS}(2,3,7)\) would need 5 systems; exact maximum is 2	(d)
\(6\)	\(\operatorname{LS}(4,5,11)\) would need 7 systems; exact maximum is 2	(b), independently mirrored by (d)
\(10\)	(4) would contain an \(S(4,5,15)\), which does not exist	(b)
\(12\)	(4) would contain an \(S(4,5,17)\), which does not exist	(b)
\(16\)	requires \(\operatorname{LS}(4,5,21)\); even one \(S(4,5,21)\) is open	unresolved