ERDŐS/DAILY ▸

← back to the ledger

ERDőS #629 · PARTIAL

Erdős problem 629 — wave 6h report

Date: 2026-07-27 UTC

Claim grades

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:

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}<n(k)<k^2 2^{k+2}. \]

  1. 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). \]

  1. The Radhakrishnan–Srinivasan lower bound gives

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

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

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

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

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\):

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:

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:

engineprimal optimumcertified lower boundresult
OR-Tools CP-SAT4040OPTIMAL
SciPy/HiGHS MILP4040gap = 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:

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

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