Erdős Problem #629

Problem 629 (Round 2)

1) ROUND-2 OBJECTIVE

Path C: isolate the exact combinatorial obstruction by replacing the original graph-theoretic minimization problem with an equivalent signed set-system parameter.

Round 1 already proved the coarse but important estimate \[ m(k)\le n(k)\le 2m(k). \] The exact gap that remains is therefore: what additional flexibility is gained by allowing different list-families on the two sides of the bipartition? The most promising Round-2 move is to identify a parameter that measures precisely this asymmetry.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

• The inequalities \[ m(k)\le n(k)\le 2m(k), \] where $m(k)$ is the minimum size of a family of $k$-sets without property B.
• The exponential-scale consequence $n(k)=2^{k+o(k)}$.

3) NEW INSIGHT / TOOL (ROUND 2)

The new insight is that $n(k)$ is exactly the minimum size of an unsplittable signed pair of $k$-uniform set-families.

More precisely, one must consider two multisets of $k$-sets, \[ \mathcal A=(A_1,\dots,A_a),\qquad \mathcal B=(B_1,\dots,B_b), \] and ask for a subset $S$ of the ground set that simultaneously

• meets every $A_i$, and
• contains none of the $B_j$.

If no such $S$ exists, then $(\mathcal A,\mathcal B)$ is an exact witness for non-$k$-choosability of a complete bipartite graph, and conversely every non-$k$-choosable bipartite graph produces such a witness.

4) ATTACK PLAN (ROUND 2)

The exact gap after Round 1 is that the parameter $m(k)$ only captures the symmetric obstruction $\mathcal A=\mathcal B$. To understand whether $n(k)$ is closer to $m(k)$ or to $2m(k)$, one must understand how much a genuinely asymmetric pair $(\mathcal A,\mathcal B)$ can save.

So the plan is:

1. prove that in defining $n(k)$, it suffices to consider complete bipartite graphs;
2. encode list assignments on $K_{a,b}$ as pairs of multisets of $k$-sets;
3. prove the exact signed-family reformulation $n(k)=\sigma(k)$;
4. recover the Round-1 bounds as immediate corollaries, thereby identifying the exact missing parameter.

5) WORK (ROUND 2)

Claim 629.1 (complete bipartite reduction).

In the definition of $n(k)$, it is enough to minimize over complete bipartite graphs. Equivalently, \[ n(k)=\min\{a+b: K_{a,b}\ \text{is not $k$-choosable}\}. \]

Proof. Let $G$ be a bipartite graph with bipartition $X\cup Y$, and suppose $G$ is not $k$-choosable. Then there exists a $k$-list assignment $L$ on $G$ that admits no proper $L$-coloring. Now consider the complete bipartite graph $K_{|X|,|Y|}$ on the same bipartition, with the same list assignment $L$. If $K_{|X|,|Y|}$ had a proper $L$-coloring, then that coloring would also be proper for the subgraph $G$, contradiction. So $K_{|X|,|Y|}$ is not $k$-choosable. Therefore the minimum defining $n(k)$ can be attained among complete bipartite graphs. $\square$

Definition 629.2 (splitter and unsplittable pair).

Let $k\ge 1$. A signed $k$-pair is a pair \[ (\mathcal A,\mathcal B), \] where $\mathcal A=(A_1,\dots,A_a)$ and $\mathcal B=(B_1,\dots,B_b)$ are multisets of $k$-subsets of some finite ground set $U$.

A subset $S\subseteq U$ is called a splitter for $(\mathcal A,\mathcal B)$ if \[ S\cap A_i\neq \emptyset \quad\text{for all }i, \qquad B_j\nsubseteq S \quad\text{for all }j. \] Equivalently: $S$ meets every $A_i$ and contains none of the $B_j$.

A signed $k$-pair is unsplittable if it has no splitter.

Define \[ \sigma(k):=\min\{|\mathcal A|+|\mathcal B|:(\mathcal A,\mathcal B)\ \text{is an unsplittable signed $k$-pair}\}. \]

Claim 629.3 (exact reformulation).

For every $k\ge 1$, \[ n(k)=\sigma(k). \]

Proof. First prove $n(k)\le \sigma(k)$. Let $(\mathcal A,\mathcal B)$ be an unsplittable signed $k$-pair with $|\mathcal A|=a$ and $|\mathcal B|=b$. Construct the complete bipartite graph $K_{a,b}$ with left side \[ X=\{x_1,\dots,x_a\} \] and right side \[ Y=\{y_1,\dots,y_b\}. \] Assign lists \[ L(x_i):=A_i,\qquad L(y_j):=B_j. \]

Suppose, for contradiction, that there is a proper $L$-coloring $c$. Let \[ S:=\{c(x_i):1\le i\le a\} \] be the set of colors used on the left side. Since $c(x_i)\in A_i$, the set $S$ meets every $A_i$. Also every $y_j$ is adjacent to every $x_i$, so $c(y_j)\notin S$. As $c(y_j)\in B_j$, it follows that $B_j\nsubseteq S$ for every $j$. Hence $S$ is a splitter for $(\mathcal A,\mathcal B)$, contradicting unsplittability. Therefore $K_{a,b}$ is not $k$-choosable, so $n(k)\le a+b=\sigma(k)$.

Now prove $\sigma(k)\le n(k)$. Let $G$ be a bipartite graph on $n(k)$ vertices that is not $k$-choosable, and by Claim 629.1 assume $G=K_{a,b}$ with bipartition $X\cup Y$, where $a+b=n(k)$. Take a bad $k$-list assignment $L$ on $G$. Write \[ X=\{x_1,\dots,x_a\},\qquad Y=\{y_1,\dots,y_b\}, \] and form the signed $k$-pair \[ \mathcal A:=(L(x_1),\dots,L(x_a)),\qquad \mathcal B:=(L(y_1),\dots,L(y_b)). \] If $(\mathcal A,\mathcal B)$ had a splitter $S\subseteq U$, then we could color every $x_i$ by any color in $L(x_i)\cap S$, and every $y_j$ by any color in $L(y_j)\setminus S$. This would be a proper $L$-coloring of $K_{a,b}$, because colors on the left lie in $S$ and colors on the right lie outside $S$. This contradicts the choice of $L$. Hence $(\mathcal A,\mathcal B)$ is unsplittable, and \[ \sigma(k)\le |\mathcal A|+|\mathcal B|=a+b=n(k). \]

Combining the two inequalities gives $n(k)=\sigma(k)$. $\square$

Corollary 629.4 (Round-1 bounds recovered and conceptually sharpened).

For every $k\ge 1$, \[ m(k)\le n(k)\le 2m(k). \]

Proof. Let $(\mathcal A,\mathcal B)$ be an unsplittable signed $k$-pair. Let $\mathcal F$ be the family of distinct sets appearing in $\mathcal A\cup\mathcal B$, with labels forgotten. If $\mathcal F$ had property B, there would exist $S\subseteq U$ meeting every member of $\mathcal F$ and containing none of them. In particular, $S$ would meet every $A_i$ and contain no $B_j$, making $S$ a splitter for $(\mathcal A,\mathcal B)$, contradiction. So $\mathcal F$ has no property B, and therefore \[ |\mathcal A|+|\mathcal B|\ge |\mathcal F|\ge m(k). \] Taking the minimum over unsplittable pairs and using Claim 629.3 gives $n(k)\ge m(k)$.

For the upper bound, choose a family $\mathcal F$ of $m(k)$ distinct $k$-sets with no property B. Take the signed pair $(\mathcal F,\mathcal F)$. If $S$ met every member of $\mathcal F$ and contained none of them, then $\mathcal F$ would have property B, impossible. Thus $(\mathcal F,\mathcal F)$ is unsplittable. Hence \[ n(k)=\sigma(k)\le |\mathcal F|+|\mathcal F|=2m(k). \] $\square$

Corollary 629.5 (the exact obstruction left open).

Determining $n(k)$ is equivalent to determining the minimum size of an unsplittable signed $k$-pair. Equivalently, the remaining open question is:

How much smaller can the best asymmetric signed obstruction $(\mathcal A,\mathcal B)$ be than the symmetric property-B obstruction $(\mathcal F,\mathcal F)$?

In particular, any proof that $n(k)<2m(k)$ must exploit a genuinely asymmetric pair.

6) ADVERSARIAL VERIFICATION

I checked the new reformulation against the main possible gaps.

• Do duplicate lists matter? Yes, they can matter for the vertex count, so $\mathcal A$ and $\mathcal B$ were defined as multisets (or ordered lists), not just ordinary families.

• Is completion to $K_{a,b}$ legitimate? Yes. A proper coloring of $K_{a,b}$ would automatically be a proper coloring of any spanning bipartite subgraph with the same bipartition, so non-choosability is preserved when we add cross-edges.

• Could the lower bound $m(k)\le n(k)$ fail because labels are forgotten? No. If the unlabeled union family had property B, the same witness subset would split the signed pair. Forgetting labels only makes the obstruction weaker, so this step is safe.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advance over Round 1 is an exact structural reformulation: \[ n(k)=\sigma(k), \] where $\sigma(k)$ is the minimum size of an unsplittable signed $k$-pair. Thus the open problem is no longer merely "compare $n(k)$ with $m(k)$", but rather "quantify the savings available from asymmetric signed obstructions over the symmetric property-B construction".

8) COMPLETION ESTIMATE

COMPLETION: 62%

9) REFERENCES

• [Bloom629 ] T. F. Bloom, Erdős Problem #629, accessed 2026-03-08.

Problem 629: the exact obstruction when one side has only $k$ lists

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read all of 629.tex, including its equivalence between non-$k$-choosability and an unsplittable signed pair $(\mathcal A,\mathcal B)$ of $k$-sets. The global target is the minimum total number $n(k)$ of vertices of a non-$k$-choosable bipartite graph. I determine the entire boundary case $|\mathcal A|=k$ and obtain $n(2)$ directly. These are restricted-case deductions, not a solution of the general asymptotic problem.

2) WORK

If $|\mathcal A|<k$, choose one element from each member of $\mathcal A$ and let $S$ be their union. It meets all left lists and has size less than $k$, so it contains no right $k$-set. Thus it is a splitter, irrespective of $|\mathcal B|$.

Now suppose $|\mathcal A|=k$ and the pair is unsplittable. Its $k$ left lists must be pairwise disjoint. If two intersect, choose one common element for those two and one element for each remaining left list; the resulting hitting set has size at most $k-1$ and again is a splitter.

For $k$ disjoint left lists, each of size $k$, there are exactly $k^k$ transversals obtained by choosing one element of each list. Every such transversal $S$ must contain a right list $B$, or it would split the pair. Since both have size $k$, this requires $B=S$. Distinct transversals therefore require distinct right lists. Consequently \[ |\mathcal A|=k\quad\Longrightarrow\quad |\mathcal B|\ge k^k \] for any unsplittable pair. Conversely, taking all $k^k$ transversals as right lists gives an unsplittable pair: every hitting set contains one of these transversals. We have proved the exact threshold \[ K_{k,b}\text{ is }k\text{-choosable}\quad\Longleftrightarrow\quad b<k^k. \] Here the forward construction supplies a bad assignment for $b\ge k^k$, while the previous argument excludes every bad assignment when $b<k^k$.

For $k=2$, every bipartite graph on at most five vertices has a side of size at most two. A side of size one always admits a splitter, and $K_{2,3}$ is 2-choosable by the threshold. But $K_{2,4}$ fails with left lists $\{1,2\},\{3,4\}$ and right lists all four cross pairs. Hence \[ n(2)=6. \]

3) ADVERSARIAL VERIFICATION

This does not imply $n(k)=k+k^k$: allowing more than $k$ vertices on both sides can yield much smaller total obstructions. Duplicate lists within one side never help a minimum witness, because removing a duplicate leaves precisely the same splitter constraints; the source's multiset formalism is valid but duplicates are redundant for the minimization. The elementary threshold is not claimed to be new in the list-colouring literature.

4) FINAL

UNRESOLVED. The smallest-side regime is completely characterized and the $k=2$ value is verified. The optimal balance and size of general asymmetric signed families remain undetermined.

5) SOURCES CHECKED

The complete supplied 629.tex, read 2026-09-23. The threshold proof, construction, and $n(2)$ calculation are self-contained consequences of the explicitly reviewed signed-family reformulation.

6) COMPLETION ESTIMATE

Subjective progress toward the general minimum-order problem. COMPLETION: 15%

Problem 629

1) FORMAL RESTATEMENT

Let $G=(V,E)$ be a graph. A $k$-list assignment is a function $L:V\to \binom{\mathcal{C}}{k}$ assigning to each vertex a set $L(v)$ of $k$ "allowed colors" from some color universe $\mathcal{C}$. An $L$-coloring is a proper vertex-coloring $c:V\to\mathcal{C}$ such that $c(v)\in L(v)$ for all $v\in V$ and $c(u)\ne c(v)$ for every edge $uv\in E$. The list chromatic number (choice number) $\chi_L(G)$ is the least $k$ such that $G$ has an $L$-coloring for every $k$-list assignment $L$.

For $k\in\mathbb{N}$ define \[ n(k)\ :=\ \min\left\{|V(G)|:\ G\text{ is bipartite and }\chi_L(G)>k\right\}. \] ( $\chi_L(G)>k$ means $G$ is not $k$-choosable.)

Goal. Determine $n(k)$ (exactly or asymptotically) as a function of $k$.

2) QUICK LITERATURE/CONTEXT CHECK

Web browsing available: YES. Computation available: YES.

The Erdős Problems site lists this question as open. It records the classical bounds of Erdős--Rubin--Taylor: \[ 2^{k-1}\ <\ n(k)\ <\ k^2\,2^{k+2}, \] and also notes the connection to property B (2-colorability) of $k$-uniform hypergraphs via a function $m(k)$: the minimum size of a family of $k$-sets without property B. The site records the inequalities $m(k)\le n(k)\le m(k+1)$ and the improved lower bound \[ 2^k\left(\frac{k}{\log k}\right)^{1/2}\ \ll\ n(k) \] coming from Radhakrishnan--Srinivasan.

The original Erdős--Rubin--Taylor manuscript $1980$ gives a clean proof that $N(2,k)$, the minimum number of vertices of a graph that is $2$-colorable but not $k$-choosable, satisfies \[ m(k)\ \le\ N(2,k)\ \le\ 2m(k), \] and in particular $N(2,2)=6$, and $12\le N(2,3)\le 14$ (with later work proving $N(2,3)=14$). For complete bipartite graphs $K_{n,n}$, Erdős--Rubin--Taylor proved a threshold $M(k)=2^{k+o(k)}$ such that $K_{n,n}$ fails to be $k$-choosable when $n\ge M(k)$, i.e. $\chi_L(K_{n,n})\sim \log_2 n$.

3) ATTACK PLAN

The problem is to determine (or sharply estimate) the minimum order of a bipartite graph with list chromatic number exceeding $k$.

1. Reduce to set systems / property B. Use the Erdős--Rubin--Taylor correspondence between $k$-choosability of complete bipartite graphs and families of $k$-sets without property B. This suggests that determining $n(k)$ up to constants/polynomial factors is closely related to determining $m(k)$.
2. Prove clean inequalities between $n(k)$ and $m(k)$. Re-derive (with full details) inequalities of the form $m(k)\le n(k)\le 2m(k)$ by explicit constructions and a "witness set" (property B) coloring argument.
3. Use known bounds on $m(k)$ to deduce asymptotics for $n(k)$. Even if $m(k)$ is not known exactly, known bounds imply $n(k)=2^{k+o(k)}$.

4) WORK

No exact formula for $n(k)$ was found. I give a fully detailed reduction to property B and derive clean exponential-scale asymptotics.

4.1. Property B and a basic lower bound $m(k)\ge 2^{k-1}$

A family $\mathcal{F}$ of $k$-subsets of a finite ground set $U$ is said to have property B if there exists $B\subseteq U$ such that $B$ meets every $F\in\mathcal{F}$ but contains none of them. Equivalently, $\mathcal{F}$ is 2-colorable as a $k$-uniform hypergraph.

Let $m(k)$ be the minimum size of a family of $k$-sets without property B.

4.2. From $m(k)$ to non-$k$-choosable bipartite graphs

4.3. Exponential-scale asymptotics $n(k)=2^{k+o(k)}$

From Proposition Proposition, determining $n(k)$ is equivalent (up to a factor $2$) to determining $m(k)$.

Even without sharp knowledge of $m(k)$, the known bounds of the form \[ 2^{k-1}\ \le\ m(k)\ \le\ k^{O(1)}\,2^k \] imply \[ \log_2 m(k)\ =\ k + O(\log k)\ =\ k+o(k), \] and hence \[ n(k)\ =\ 2^{k+o(k)}. \] So the correct growth is exponential in $k$ with base $2$, but the polynomial factor (and exact values) remain the main difficulty.

5) VERIFICATION

Lemma Lemma is a standard first-moment/union-bound argument and was checked carefully. Proposition Proposition is constructive in both directions: the upper bound builds a concrete complete bipartite graph with a "hard" list assignment from a property-B counterexample; the lower bound turns a property-B witness set $B$ into a valid list-coloring for any bipartite graph with fewer than $m(k)$ vertices.

6) FINAL

UNRESOLVED.

1. The exact (or sharp asymptotic) determination of $n(k)$ is open.
2. I proved the clean reduction $m(k)\le n(k)\le 2m(k)$ to the extremal set-system quantity $m(k)$ (property B).
3. This yields an elementary exponential lower bound $n(k)\ge 2^{k-1}$ and shows $n(k)=2^{k+o(k)}$ given standard polynomial-factor upper bounds for $m(k)$.
4. A complete solution would require determining $m(k)$ (and hence $n(k)$) up to a sharp constant or sharp polynomial factor.

7) COMPLETION ESTIMATE

COMPLETION: 45%.