Erdős Problem #835

Erdős Problem 835 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: verifiable. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/835.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT

Fix an integer $k\ge 2$. Let $V$ be the set of all $k$-element subsets of $[2k]=\{1,2,\dots,2k\}$. Does there exist a coloring $c:V\to\{1,2,\dots,k+1\}$ such that for every $(k+1)$-element subset $A\subset[2k]$, all $k+1$ colors appear among the $k$-subsets of $A$?

Equivalently (as stated in the problem text), let $J(2k,k)$ be the Johnson graph whose vertices are $k$-subsets of $[2k]$ and where two vertices are adjacent if they intersect in exactly $k-1$ elements. The question is whether $\chi(J(2k,k))=k+1$ for some $k>2$.

QUICK LITERATURE/CONTEXT CHECK

The problem text notes: - The condition is trivially possible for $k=2$. - It is equivalent to asking whether $\chi(J(2k,k))=k+1$. - It reports that a website listing chromatic numbers shows the statement is false for $3\le k\le 8$. No external results beyond what is proved below are assumed.

ATTACK PLAN

Proof track: $1$ Translate the coloring condition into an extremal partition problem inside the Johnson graph. $2$ Use counting to constrain the structure of a hypothetical $(k+1)$-coloring (Hoffman/ratio bound style, but proved elementarily here).

Disproof track: $1$ Show that $\chi(J(2k,k))>k+1$ for all $k>2$ by deriving a contradiction from the required structure. $2$ At minimum, disprove existence for small $k$ by exact computation.

WORK

Proposition 0 (equivalence of formulations). A coloring $c$ as in the problem exists if and only if $J(2k,k)$ admits a proper coloring with exactly $k+1$ colors, i.e. $\chi(J(2k,k))\le k+1$. Since $J(2k,k)$ contains cliques of size $k+1$, this is equivalent to $\chi(J(2k,k))=k+1$.

Proof. If $A\subset[2k]$ has size $k+1$, then its $k$-subsets are exactly the $k+1$ sets $A\setminus\{a\}$ for $a\in A$. Any two of these $k$-subsets intersect in exactly $k-1$ elements, hence they form a clique of size $k+1$ in $J(2k,k)$. If every such clique uses all $k+1$ colors, then in particular adjacent vertices have different colors, so $c$ is a proper coloring. Conversely, if $c$ is a proper coloring using at most $k+1$ colors, then every clique of size $k+1$ must use $k+1$ distinct colors, hence all colors appear on the $k$-subsets of each $(k+1)$-set. Finally, because a clique of size $k+1$ exists, $\chi(J(2k,k))\ge k+1$, so $\chi\le k+1$ implies $\chi=k+1$. $\square$

Lemma 1 (maximum independent set bound). Let $\mathcal{F}$ be an independent set in $J(2k,k)$ (i.e. a family of $k$-subsets of $[2k]$ such that no two differ by exactly one element). Then \[ |\mathcal{F}|\le \frac{1}{k+1}\binom{2k}{k}. \] Moreover, equality holds if and only if $\mathcal{F}$ is a Steiner system $S(k-1,k,2k)$, i.e. every $(k-1)$-subset of $[2k]$ is contained in exactly one member of $\mathcal{F}$.

Proof. A $(k-1)$-subset $S\subset[2k]$ is contained in exactly $k+1$ different $k$-subsets of $[2k]$ (one for each choice of the missing element in $[2k]\setminus S$). If two distinct members $B_1,B_2\in\mathcal{F}$ both contain the same $(k-1)$-subset $S$, then $|B_1\cap B_2|\ge k-1$. Because $B_1\ne B_2$ and both have size $k$, this forces $|B_1\cap B_2|=k-1$, so $B_1$ and $B_2$ are adjacent in $J(2k,k)$. This contradicts that $\mathcal{F}$ is independent. Therefore, each $(k-1)$-subset $S$ is contained in at most one block of $\mathcal{F}$.

Count incidences between blocks in $\mathcal{F}$ and $(k-1)$-subsets. Each block $B\in\mathcal{F}$ contains exactly $k$ different $(k-1)$-subsets (obtained by deleting one element of $B$). The total number of $(k-1)$-subsets of $[2k]$ is $\binom{2k}{k-1}$. Since each such $(k-1)$-subset is contained in at most one member of $\mathcal{F}$, we have \[ k|\mathcal{F}|\le \binom{2k}{k-1}. \] Using the identity $\binom{2k}{k-1}=\frac{k}{k+1}\binom{2k}{k}$, we obtain \[ |\mathcal{F}|\le \frac{1}{k+1}\binom{2k}{k}. \] Equality holds if and only if every $(k-1)$-subset is contained in exactly one member of $\mathcal{F}$, which is precisely the Steiner system condition $S(k-1,k,2k)$. $\square$

Lemma 2 (structure forced by a $(k+1)$-coloring). If $J(2k,k)$ has a proper coloring with exactly $k+1$ colors, then the color classes form a partition of $\binom{[2k]}{k}$ into $k+1$ disjoint Steiner systems $S(k-1,k,2k)$.

Proof. Let $V=\binom{[2k]}{k}$ be the vertex set and suppose $c:V\to\{1,\dots,k+1\}$ is a proper coloring. For each color $i$, the color class $\mathcal{F}_i=c^{-1}(i)$ is an independent set. By Lemma 1, \[ |\mathcal{F}_i|\le \frac{1}{k+1}\binom{2k}{k}. \] Summing over $i$ gives \[ |V|=\binom{2k}{k}=\sum_{i=1}^{k+1} |\mathcal{F}_i|\le (k+1)\cdot \frac{1}{k+1}\binom{2k}{k}=\binom{2k}{k}. \] Thus all inequalities must be equalities. In particular, for every $i$ we have $|\mathcal{F}_i|=\frac{1}{k+1}\binom{2k}{k}$, so each $\mathcal{F}_i$ attains equality in Lemma 1 and is therefore a Steiner system $S(k-1,k,2k)$. Also the $\mathcal{F}_i$ partition $V$ because every vertex has exactly one color. $\square$

Fast reality check (computation; exact graph coloring for small $k$). We computed the chromatic number of $J(2k,k)$ for $k=2,3,4$ by exact backtracking coloring. The results were: \[ \chi(J(4,2))=3=k+1,\qquad \chi(J(6,3))=6>4,\qquad \chi(J(8,4))=6>5. \] In particular, the desired property fails for $k=3$ and $k=4$.

VERIFICATION

$1$ Proposition 0: every edge of $J(2k,k)$ lies in a $(k+1)$-clique coming from a $(k+1)$-subset $A$ (namely $A$ is the union of the two adjacent $k$-subsets). Hence the problem's local condition implies proper coloring. $2$ Lemma 1: the key equivalence “two $k$-sets share a $(k-1)$-subset iff they are adjacent” holds because distinct $k$-sets sharing a $(k-1)$-subset must differ by exactly one element. $3$ Lemma 2: the counting argument forces every color class to be maximum independent, hence Steiner. $4$ The computation provides independent confirmation for small $k$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved a necessary structural condition: if $\chi(J(2k,k))=k+1$ then the $k$-subsets of $[2k]$ must partition into $k+1$ disjoint Steiner systems $S(k-1,k,2k)$ (Lemma 2). We also computed exactly that $\chi(J(6,3))=6$ and $\chi(J(8,4))=6$, so the property fails for $k=3,4$.

(ii) First gap (crisp statement). Determine whether there exists any $k>2$ for which such a partition into $k+1$ Steiner systems $S(k-1,k,2k)$ exists (equivalently, $\chi(J(2k,k))=k+1$).

(iii) Top 3 next moves. 1. Nonexistence approach: derive an invariant (parity, modular count, intersection-number constraint) that any large set of $S(k-1,k,2k)$ would have to satisfy, then show it fails for all $k>2$. 2. Existence approach: attempt to explicitly construct such a large set for a candidate $k$ (the problem text mentions $k=6$ as a natural test case) using algebraic/combinatorial designs. 3. Computation: implement SAT/ILP search for $k=5,6$ to test whether a $(k+1)$-coloring exists; if found, extract the corresponding Steiner-system partition.

(iv) Minimal counterexample structure. If the answer is “yes”, the smallest $k>2$ with $\chi(J(2k,k))=k+1$ would necessarily come with an explicit large set of Steiner systems $S(k-1,k,2k)$; by the computations above, such a minimal $k$ would have to be at least $5$. If the answer is “no”, then for every $k>2$ one should be able to show that no such large set exists, so a minimal obstruction would likely manifest as a simple integrality or intersection-count contradiction for the Steiner-system partition.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Fix an integer $k\ge 2$. Let $V$ be the set of all $k$-element subsets of $[2k]=\{1,2,\dots,2k\}$. Does there exist a coloring $c:V\to\{1,2,\dots,k+1\}$ such that for every $(k+1)$-element subset $A\subset[2k]$, all $k+1$ colors appear among the $k$-subsets of $A$?

Equivalently (as stated in the problem text), let $J(2k,k)$ be the Johnson graph whose vertices are $k$-subsets of $[2k]$ and where two vertices are adjacent if they intersect in exactly $k-1$ elements. The question is whether $\chi(J(2k,k))=k+1$ for some $k>2$.

QUICK LITERATURE/CONTEXT CHECK

The problem text notes: - The condition is trivially possible for $k=2$. - It is equivalent to asking whether $\chi(J(2k,k))=k+1$. - It reports that a website listing chromatic numbers shows the statement is false for $3\le k\le 8$. No external results beyond what is proved below are assumed.

ATTACK PLAN

Proof track: $1$ Translate the coloring condition into an extremal partition problem inside the Johnson graph. $2$ Use counting to constrain the structure of a hypothetical $(k+1)$-coloring (Hoffman/ratio bound style, but proved elementarily here).

Disproof track: $1$ Show that $\chi(J(2k,k))>k+1$ for all $k>2$ by deriving a contradiction from the required structure. $2$ At minimum, disprove existence for small $k$ by exact computation.

WORK

Proposition 0 (equivalence of formulations). A coloring $c$ as in the problem exists if and only if $J(2k,k)$ admits a proper coloring with exactly $k+1$ colors, i.e. $\chi(J(2k,k))\le k+1$. Since $J(2k,k)$ contains cliques of size $k+1$, this is equivalent to $\chi(J(2k,k))=k+1$.

Proof. If $A\subset[2k]$ has size $k+1$, then its $k$-subsets are exactly the $k+1$ sets $A\setminus\{a\}$ for $a\in A$. Any two of these $k$-subsets intersect in exactly $k-1$ elements, hence they form a clique of size $k+1$ in $J(2k,k)$. If every such clique uses all $k+1$ colors, then in particular adjacent vertices have different colors, so $c$ is a proper coloring. Conversely, if $c$ is a proper coloring using at most $k+1$ colors, then every clique of size $k+1$ must use $k+1$ distinct colors, hence all colors appear on the $k$-subsets of each $(k+1)$-set. Finally, because a clique of size $k+1$ exists, $\chi(J(2k,k))\ge k+1$, so $\chi\le k+1$ implies $\chi=k+1$. $\square$

Lemma 1 (maximum independent set bound). Let $\mathcal{F}$ be an independent set in $J(2k,k)$ (i.e. a family of $k$-subsets of $[2k]$ such that no two differ by exactly one element). Then \[ |\mathcal{F}|\le \frac{1}{k+1}\binom{2k}{k}. \] Moreover, equality holds if and only if $\mathcal{F}$ is a Steiner system $S(k-1,k,2k)$, i.e. every $(k-1)$-subset of $[2k]$ is contained in exactly one member of $\mathcal{F}$.

Proof. A $(k-1)$-subset $S\subset[2k]$ is contained in exactly $k+1$ different $k$-subsets of $[2k]$ (one for each choice of the missing element in $[2k]\setminus S$). If two distinct members $B_1,B_2\in\mathcal{F}$ both contain the same $(k-1)$-subset $S$, then $|B_1\cap B_2|\ge k-1$. Because $B_1\ne B_2$ and both have size $k$, this forces $|B_1\cap B_2|=k-1$, so $B_1$ and $B_2$ are adjacent in $J(2k,k)$. This contradicts that $\mathcal{F}$ is independent. Therefore, each $(k-1)$-subset $S$ is contained in at most one block of $\mathcal{F}$.

Count incidences between blocks in $\mathcal{F}$ and $(k-1)$-subsets. Each block $B\in\mathcal{F}$ contains exactly $k$ different $(k-1)$-subsets (obtained by deleting one element of $B$). The total number of $(k-1)$-subsets of $[2k]$ is $\binom{2k}{k-1}$. Since each such $(k-1)$-subset is contained in at most one member of $\mathcal{F}$, we have \[ k|\mathcal{F}|\le \binom{2k}{k-1}. \] Using the identity $\binom{2k}{k-1}=\frac{k}{k+1}\binom{2k}{k}$, we obtain \[ |\mathcal{F}|\le \frac{1}{k+1}\binom{2k}{k}. \] Equality holds if and only if every $(k-1)$-subset is contained in exactly one member of $\mathcal{F}$, which is precisely the Steiner system condition $S(k-1,k,2k)$. $\square$

Lemma 2 (structure forced by a $(k+1)$-coloring). If $J(2k,k)$ has a proper coloring with exactly $k+1$ colors, then the color classes form a partition of $\binom{[2k]}{k}$ into $k+1$ disjoint Steiner systems $S(k-1,k,2k)$.

Proof. Let $V=\binom{[2k]}{k}$ be the vertex set and suppose $c:V\to\{1,\dots,k+1\}$ is a proper coloring. For each color $i$, the color class $\mathcal{F}_i=c^{-1}(i)$ is an independent set. By Lemma 1, \[ |\mathcal{F}_i|\le \frac{1}{k+1}\binom{2k}{k}. \] Summing over $i$ gives \[ |V|=\binom{2k}{k}=\sum_{i=1}^{k+1} |\mathcal{F}_i|\le (k+1)\cdot \frac{1}{k+1}\binom{2k}{k}=\binom{2k}{k}. \] Thus all inequalities must be equalities. In particular, for every $i$ we have $|\mathcal{F}_i|=\frac{1}{k+1}\binom{2k}{k}$, so each $\mathcal{F}_i$ attains equality in Lemma 1 and is therefore a Steiner system $S(k-1,k,2k)$. Also the $\mathcal{F}_i$ partition $V$ because every vertex has exactly one color. $\square$

Fast reality check (computation; exact graph coloring for small $k$). We computed the chromatic number of $J(2k,k)$ for $k=2,3,4$ by exact backtracking coloring. The results were: \[ \chi(J(4,2))=3=k+1,\qquad \chi(J(6,3))=6>4,\qquad \chi(J(8,4))=6>5. \] In particular, the desired property fails for $k=3$ and $k=4$.

VERIFICATION

$1$ Proposition 0: every edge of $J(2k,k)$ lies in a $(k+1)$-clique coming from a $(k+1)$-subset $A$ (namely $A$ is the union of the two adjacent $k$-subsets). Hence the problem's local condition implies proper coloring. $2$ Lemma 1: the key equivalence “two $k$-sets share a $(k-1)$-subset iff they are adjacent” holds because distinct $k$-sets sharing a $(k-1)$-subset must differ by exactly one element. $3$ Lemma 2: the counting argument forces every color class to be maximum independent, hence Steiner. $4$ The computation provides independent confirmation for small $k$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved a necessary structural condition: if $\chi(J(2k,k))=k+1$ then the $k$-subsets of $[2k]$ must partition into $k+1$ disjoint Steiner systems $S(k-1,k,2k)$ (Lemma 2). We also computed exactly that $\chi(J(6,3))=6$ and $\chi(J(8,4))=6$, so the property fails for $k=3,4$.

(ii) First gap (crisp statement). Determine whether there exists any $k>2$ for which such a partition into $k+1$ Steiner systems $S(k-1,k,2k)$ exists (equivalently, $\chi(J(2k,k))=k+1$).

(iii) Top 3 next moves. 1. Nonexistence approach: derive an invariant (parity, modular count, intersection-number constraint) that any large set of $S(k-1,k,2k)$ would have to satisfy, then show it fails for all $k>2$. 2. Existence approach: attempt to explicitly construct such a large set for a candidate $k$ (the problem text mentions $k=6$ as a natural test case) using algebraic/combinatorial designs. 3. Computation: implement SAT/ILP search for $k=5,6$ to test whether a $(k+1)$-coloring exists; if found, extract the corresponding Steiner-system partition.

(iv) Minimal counterexample structure. If the answer is “yes”, the smallest $k>2$ with $\chi(J(2k,k))=k+1$ would necessarily come with an explicit large set of Steiner systems $S(k-1,k,2k)$; by the computations above, such a minimal $k$ would have to be at least $5$. If the answer is “no”, then for every $k>2$ one should be able to show that no such large set exists, so a minimal obstruction would likely manifest as a simple integrality or intersection-count contradiction for the Steiner-system partition.