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.

1. 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.

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

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

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

lower-bound literature and records the original source.

4. 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.

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

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

6. 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.

7. 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:

1. (a) A requested colouring is exactly a large set

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

2. (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.

3. (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.

4. (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.

5. (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.

6. (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.

7. (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)$.

8. (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 iand

\[ \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.

1. 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>.

2. 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.

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

[“On the clique covering numbers of Johnson graphs,”

arXiv:2502.15019](https://arxiv.org/abs/2502.15019). This is the [Jor25]

linked from the live discussion; the relevant items are Proposition 4.5

and Theorem 5.5.

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

[“Intersections among Steiner systems,” JCTA 16 (1974),

273–285](https://doi.org/10.1016/0097-3165(74)90054-5). Its abstract

explicitly states that the maximum number of mutually disjoint

$S(4,5,11)$'s is two.

5. 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)$”](https://combinatorialpress.com/um/vol1/),

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.

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.

7. 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.

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

[“4-(21,5,$\lambda$) designs from a group of order

171”](https://combinatorialpress.com/article/ars/Volume%20036/volume-36-paper-19.pdf),

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:

1. a proof that no $S(4,5,21)$ exists, which would rule out $k=16$; or

2. a compatible 17-way extension tower from

$\operatorname{LS}(4,5,21)$ to

$\operatorname{LS}(14,15,31)$; or

3. 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](https://cloud.google.com/products/compute/pricing/general-purpose)

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