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

Erdős problem 629 — wave 6h report

Date: 2026-07-27 UTC

Claim grades

(a) elementary-rigorous: proved below without an external theorem.
(b) rigorous modulo named theorem: the exact theorem and primary source are named.
(c) plausible/structural-unverified: useful interpretation, not promoted to a theorem.
(d) computational-only: a finite claim certified by the standalone program, with the solver and scope stated exactly.

Step 0: live-page gate

I fetched the rendered live page, its LaTeX view, and its discussion thread through the Bright Data browser path:

The direct rendered mathematics was ambiguous about superscripts, so the LaTeX view was used to disambiguate it. The following is the verbatim current statement:

> The list chromatic number $\chi_L(G)$ is defined to be the minimal $k$ such that for any assignment of a list of $k$ colours to each vertex of $G$ (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct colours.

> Determine the minimal number of vertices $n(k)$ of a bipartite graph $G$ such that $\chi_L(G)>k$.

Gate data read from the live page:

status: OPEN;
page last edited: 28 October 2025;
claimed proofs: 0;
“Currently working on this problem”: None;
“Interested in collaborating”: None;
four comments were present.

Thus the requested stop condition did not apply.

Results listed on the live page

These are recorded as page ground truth, not rederived:

1. Erdős–Rubin–Taylor proved

\[ 2^{k-1}

2. If $m(k)$ is the least size of a family of $k$-sets without property B, then

\[ m(k)\le n(k)\le m(k+1). \]

3. The Radhakrishnan–Srinivasan lower bound gives

\[ 2^k\left(\frac{k}{\log k}\right)^{1/2}\ll n(k). \]

4. $n(2)=6$, $n(3)=14$, and

\[ n(k)\le k\,n(k-2)+2^k. \]

All four live comments

Comments are explicitly unverified by the website; none was a claimed proof.

1. sp4cerat, 22 June 2026. “Some computational notes on $n(4)$ (separator-free / property-B encoding).” The comment says a record attack found no total-$\le39$ construction in its tested searches and links the code textually at GitHub. Its notes say the unresolved $q=11$, $|P|=10,|N|=29$ split was extrapolated at about 18 single-core hours. The comment is historical work, but the page’s current-worker marker is still None.

2. Alfaiz, 4 April 2026. Claimed the asymptotic upper bound

\[ n(k)\le\left(\frac{e\ln 2}{2}+o(1)\right)k^2 2^k \]

and linked a Google Drive note.

3. Nat Sothanaphan, 4 April 2026. Replied that the preceding bound was not new: combine Erdős’s 1964 bound

\[ m(k)\le\left(\frac{e\log 2}{4}+o(1)\right)k^2 2^k \]

with $n(k)\le2m(k)$.

4. Quanyu Tang, 25 October 2025. Pointed out the sharper lower bound inherited from $m(k)$, citing Radhakrishnan–Srinivasan and Grill–Linzmayer. The comment says the site was updated to incorporate it.

Literature check

I searched the exact problem wording, n(k) not k-choosable bipartite, n(4) choosability, the cited titles, and forward references. The following primary records were verified to exist and to make the stated claims:

Erdős, Rubin, Taylor (1980), _Choosability in graphs_, Congressus Numerantium XXVI, 125–157. The bibliographic record exists; I did not obtain a reliable full-text copy. Consequently, claims attributed to it here are taken only from the authoritative live page and from the later HMT paper.
Hanson, MacGillivray, Toft (1996), _Choosability of bipartite graphs_, Ars Combinatoria 44, 183–192. The publisher page and PDF explicitly state $n(3)=14$, $n(k)\le k n(k-2)+2^k$, and hence $n(4)\le40$. (b)
Östergård (2014), _On the minimum size of 4-uniform hypergraphs without property B_, Discrete Applied Mathematics 163, 199–204, DOI 10.1016/j.dam.2011.11.035. Its abstract states that an exhaustive search proves $m(4)=23$. (b)
Seymour (1974), _A note on a combinatorial problem of Erdős and Hajnal_, Journal of the London Mathematical Society s2-8, 681–682, DOI 10.1112/jlms/s2-8.4.681. This is the primary source for the 23-edge upper construction. The explicit edge list used below was located in Raigorodskii–Cherkashin’s 2020 survey and then checked from scratch, rather than trusted.
Radhakrishnan–Srinivasan (2000), _Improved bounds and algorithms for hypergraph 2-coloring_, Random Structures & Algorithms 16, 4–32, publisher record.
Grill–Linzmayer (2024), _Improved Lower Bounds for Property B_, arXiv:2403.05674v3. Its abstract identifies $\Omega(2^k\sqrt{k/\log k})$ as the current asymptotic lower bound for $m(k)$ and studies finite-$k$ refinements.

I found no primary paper in these searches claiming a value of $n(4)$, an improvement of the HMT value $n(4)\le40$, or a solution of the general problem. That is a search report, not an assertion that no such paper exists. (c)

1. Exact signed-set-cover reduction

Let a bad $k$-list assignment live on a bipartite graph with parts $P$ and $N$.

First add every missing edge between the two parts. Adding edges cannot create a list coloring, so a minimum obstruction may be taken to be a complete bipartite graph. Repeated lists within one part are redundant: after deleting one duplicate, any coloring extends to it by copying the same-side twin’s color. Thus the vertices can be represented by two families of distinct $k$-sets. (a)

Let the color palette be $[q]$. For a subset $S\subseteq[q]$, color every vertex on the $P$-side from $S$ and every vertex on the $N$-side from its complement. This is possible exactly when

\[ S\cap T\ne\varnothing\quad(T\in P),\qquad T\nsubseteq S\quad(T\in N). \]

Consequently, $(P,N)$ is an obstruction exactly when every $S\subseteq[q]$ is killed by at least one signed clause:

\[ \exists T\in P:\ T\cap S=\varnothing \quad\text{or}\quad \exists T\in N:\ T\subseteq S. \tag{1} \]

The objective $|P|+|N|$ is exactly the bipartite vertex count. This is a plain set-cover formulation over the $2^q$ possible separators. (a)

2. A finite uniform reduction for any attempted $n(4)\le39$

Lower end: $q\ge11$

For a fixed signed 4-set and the layer of $r$-subsets $S$:

a positive clause kills $\binom{q-4}{r}$ members of the layer;
a negative clause kills $\binom{q-4}{r-4}$ members.

Binomial coefficients outside their natural range are zero.

For $q\le6$, a subset $S$ exists with both $|S|<4$ and $|[q]\setminus S|<4$, so no signed clause can kill it.

For $q=7$, the 35 three-subsets force all 35 positive complements and the 35 four-subsets force all 35 negative sets. Hence at least 70 clauses are needed.

For $q=8$, every signed clause kills only one four-subset, so the 70 four-subsets require at least 70 clauses.

For $q=9$, writing $p=|P|$, $n=|N|$, the layers of sizes 4 and 5 give

\[ 5p+n\ge126,\qquad p+5n\ge126. \]

Adding yields $p+n\ge42$.

For $q=10$, every signed clause kills six of the $\binom{10}{5}=252$ five-subsets, giving $p+n\ge42$.

Therefore no obstruction with at most 39 vertices uses $q\le10$. (a)

Upper end: $q\le22$

Among witnesses with a fixed number of lists, choose one with the smallest palette. If two colors $x,y$ never occur together in a list, relabel $y$ as $x$. List sizes remain four. Any coloring of the relabeled instance lifts to a coloring of the original instance: an apparent $x$-$x$ conflict that came from different original symbols lifts to $x$-$y$, while all genuine same-symbol conflicts remain conflicts. Hence noncolorability is preserved, contradicting palette minimality.

Thus every pair of colors occurs together in at least one list. With at most 39 lists,

\[ \binom q2\le39\binom42=234. \]

Since $\binom{22}{2}=231$ and $\binom{23}{2}=253$, $q\le22$. (a)

Combining the two ends gives the concrete finite target

\[ \boxed{11\le q\le22} \]

in the following precise sense: if any total-$\le39$ obstruction exists, repeated color-merging produces one whose palette lies in this interval. A non-minimal presentation of an obstruction can use more than 22 colors. This is a uniformity step: it does not prove $n(4)=40$, but it specifies all palettes that an exact exclusion must cover. (a)

3. The Seymour–Toft core and why naive orientation cannot save edges

The following 23 distinct 4-sets on $[11]$ are the Seymour–Toft core:

\[ \begin{aligned} &129\,10,\ 349\,10,\ 569\,10,\ 789\,10,\\ &129\,11,\ 349\,11,\ 569\,11,\ 789\,11,\\ &12\,10\,11,\ 34\,10\,11,\ 56\,10\,11,\ 78\,10\,11,\\ &1358,\ 1367,\ 1457,\ 1467,\ 1468,\\ &2357,\ 2367,\ 2368,\ 2457,\ 2458,\ 2468. \end{aligned} \]

Here, for example, $129\,10$ means $\{1,2,9,10\}$.

The verifier exhausts all $2^{11}=2048$ colorings and confirms:

no coloring makes every one of these 23 edges bichromatic;
deleting any one edge makes the family 2-colorable.

These two properties of this explicit edge list are (d).

There is also a general elementary lemma.

Lemma. If a non-2-colorable $k$-uniform hypergraph $H$ is edge-minimal, then a separator-free signed family restricted to signed copies of edges of $H$ must use both signs of every edge. In particular, it has $2|H|$ signed clauses.

Proof. For each $e\in H$, choose a property-B coloring of $H-e$. The edge $e$ is monochromatic, since otherwise this would color all of $H$. Every other edge is bichromatic and therefore kills neither orientation of this separator. The sign of $e$ matching its monochromatic color is forced. Complementing the coloring forces the other sign. Repeat for every $e$. $\square$ (a)

For the explicit core, this proves that merely assigning signs to its 23 edges requires all 46 signed copies. Extra edges are essential to reach the HMT value 40.

4. Exact computation: arbitrary 11-color extensions containing the core

Define $M_{\rm core}(11)$ as the minimum $|P|+|N|$ over all signed 4-set obstructions on $[11]$, with arbitrary additional 4-sets allowed, subject only to the condition that the unoriented union $P\cup N$ contains every edge of the Seymour–Toft core.

For every 4-set $T\subseteq[11]$, introduce binary variables $p_T,n_T$. The model is

\[ \begin{aligned} \min\quad &\sum_T(p_T+n_T),\\ \text{s.t.}\quad &\sum_{T\cap S=\varnothing}p_T+\sum_{T\subseteq S}n_T\ge1 &&\text{for every }S\subseteq[11],\\ &p_T+n_T\ge1&&\text{for every core edge }T,\\ &p_T,n_T\in\{0,1\}. \end{aligned} \]

This has 660 binary variables, 2048 separator-cover constraints, and 23 core constraints.

Two independent optimization engines rebuilt this model from scratch:

|---|---:|---:|---|

| OR-Tools CP-SAT | 40 | 40 | OPTIMAL |

| SciPy/HiGHS MILP | 40 | 40 | gap = 0 |

Therefore

\[ \boxed{M_{\rm core}(11)=40}. \]

This is an exact but computational-only (d) result. It rules out every 39-clause obstruction on the 11-color palette whose unoriented list union contains this particular core. It does not rule out:

a core-free obstruction on 11 colors;
an obstruction on 12–22 colors;
an embedded Seymour–Toft core helped by lists using additional colors.

Explicit attaining certificate

Let

\[ X_1=\{1,2\},\ X_2=\{3,4\},\ X_3=\{5,6\},\ X_4=\{7,8\}, \qquad Y=\{9,10,11\}. \]

Put each of the 12 sets $X_i\cup Z$, where $i\in[4]$ and $Z\in\binom Y2$, in both $P$ and $N$. Of the 16 transversals choosing one point from every $X_i$, put a transversal in $P$ when it contains an odd number of the first elements $1,3,5,7$, and in $N$ otherwise.

Each side has $12+8=20$ lists. Exhaustion of all 2048 separators verifies (1), and the union contains the 23 core edges. This reproduces the known HMT upper construction; it is not claimed as new. (d), and (b) for its published provenance

5. Reverification

Standalone verifier:

python3 runs/erdos629_wave6h_verify.py

It performs, without importing the comment author’s code:

1. pure-Python exhaustion of all 2048 colorings of the 23-edge core;

2. edge-criticality checks for all 23 one-edge deletions;

3. pure-Python verification of the explicit HMT $20+20$ certificate;

4. recomputation of the $q\le10$ layer bounds and the $q\le22$ pair count;

5. reconstruction and exact solution of the forced-core integer program in CP-SAT;

6. independent reconstruction and exact solution in HiGHS.

The dependency-free portion can be run with --skip-optimization.

6. Exact remaining wall

To prove $n(4)=40$, one must still exclude every signed cover of total at most 39 for every palette

\[ q=11,12,\ldots,22. \]

The most useful missing structural lemma would force a small, classified non-2-colorable core inside the unoriented union and show that extra colors cannot make its signed extension cheaper. The result above handles one core on its original 11-color palette only.

The naive $q=22$ model has

$2\binom{22}{4}=14{,}630$ signed variables;
$2^{22}=4{,}194{,}304$ separator constraints;
$14{,}630\cdot2^{18}=3{,}835{,}166{,}720$ literal incidences.

The incidence count and 14.29-GiB raw-index figure are exact arithmetic. (a) A practical SAT/MILP representation would likely exceed 40 GiB before search state, and a naive complete palette sweep is plausibly at least hundreds of core-hours, with no credible finite upper runtime guarantee. These are resource estimates, not certified lower bounds. (c) It should not be run on this box. A stronger core theorem, orbit reduction, or certified cutting-plane argument is needed.

PARTIAL: Proved that any total-$\le39$ obstruction reduces to one on a palette $11\le q\le22$, and computationally certified with two independent solvers that every 11-color obstruction whose unoriented union contains the Seymour–Toft core needs exactly 40 lists; the unrestricted problem remains open.

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