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

Erdős problem #624 — wave w003

Access date: 2026-07-28 UTC.

Claim labels used below:

(a) elementary-rigorous: proved directly here.
(b) rigorous-modulo-named-theorem: the exact named input is stated.
(c) plausible/structural-unverified: not used as a theorem.
(d) computational-only: a finite calculation with reproducible code.

0. Mandatory live-page gate

I fetched the rendered live page, its /latex/624 view, both bibliography popups, and its discussion thread through the Bright Data browser path before doing any mathematics.

Live badge: OPEN.
Claimed proofs: 0.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
All other visible reaction/working markers are None.
The page was last edited 27 October 2025.

The only discussion consists of [Post deleted] (Unknown, 17:28 on 24 August 2025) and Thomas Bloom's “Corrected, thanks.” (18:33 on the same date). It contains no mathematical claim. Thus neither stop condition (claimed solution/falsification or current worker) was present.

Verbatim current statement

Copied from the live /latex/624 view:

Let $X$ be a finite set of size $n$ and $H(n)$ be such that there is a function $f:\{A : A\subseteq X\}\to X$ so that for every $Y\subseteq X$ with $\lvert Y\rvert \geq H(n)$ we have\[\{ f(A) : A\subseteq Y\}=X.\]Prove that\[H(n)-\log_2 n \to \infty.\]

As is forced by the listed bounds, $H(n)$ is understood to mean the least such threshold.

Results listed on the live page

The page attributes to Erdős and Hajnal [ErHa68]

\log _2 n\leq H(n) <\log _2n+(3+o(1))\log _2\log _2n. \tag{1}

It then records:

Alon's pigeonhole argument for $H(2^k)\geq k+1$.
An Erdős--Gyárfás strengthening, proved by Alon by personal

communication: for an absolute $c>0$ and sufficiently large $k$, every $f:\mathcal P(X)\to X$, $|X|=2^k$, has a $k$-set $Y$ with \[ |\{f(A):A\subseteq Y\}|<(1-c)2^k. \]

Alon's converse construction (again personal communication): for large

$k$, some $f$ has more than $2^k/4$ images on every $k$-set.

These page-reported personal communications are not used in the new finite calculation below.

1. Primary-source literature audit

1.1 The two cited records exist

(b) P. Erdős and A. Hajnal,

Egy kombinatorikus problémáról / On a combinatorial problem, Matematikai Lapok 19 (1968), 345--348, MR39 #5378, is available from the Rényi Institute archive. I downloaded and read all four pages. Its English summary states (1) and the conjectured divergent difference.

P. Erdős, A selection of problems and results in combinatorics,

Combinatorics, Probability and Computing 8 (1999), 1--6, MR1684620, DOI 10.1017/S0963548398003496, exists with exactly that metadata. The publisher exposes the abstract and metadata but not the full article in this environment, so I make no claim about wording inside it beyond the live page's citation.

1.2 Important statement discrepancy

The 1968 source requires

f(A)\in X\setminus A, \tag{2}

whereas the authoritative live statement only requires $f:\mathcal P(X)\to X$. The live problem is therefore at least as strong as the original set-mapping formulation. The upper bound in (1) still transfers, because a construction satisfying (2) is also allowed by the live statement; the lower conjecture does not transfer in the other direction automatically. Everything computed below concerns exactly the unrestricted live statement.

This is not cosmetic: none of the explicit witnesses below was assumed to satisfy (2).

1.3 Search outcome

I searched exact fragments of the formula, both cited titles, “set mapping,” $H(2^k)$, and the Erdős--Gyárfás/Alon wording. I found:

the original 1968 source;
the 1999 bibliographic record;
a 2013 Gyárfás presentation repeating the historical set-mapping problem;
P. Erdős and J. Spencer,

On a problem of Erdős and Hajnal, which concerns the different independent-set parameter $h(n)$, not a solution of this $H(n)$ conjecture;

the general terminology paper B. Bollobás, D. Pritchard, T. Rothvoß and

A. Scott, Cover-Decomposition and Polychromatic Numbers, arXiv:1009.6144.

The last paper defines the exact hypergraph language used below, but its general bounded-edge/VC-dimension results do not supply the family-specific upper bound needed here. No primary paper or arXiv record containing Alon's personal-communication result, or a later solution of the stated limit, was found. This is an honest search miss, not a proof that no unindexed result exists.

2. Exact reformulations

2.1 Boolean-interval hypergraph

Fix $n,h$. Let

\mathcal B_{n,h}=\left( \{A\subseteq[n]:|A|\leq h\}, \{E_Y:Y\in {[n]\choose h}\} \right),\qquad E_Y=\{A:A\subseteq Y\}. \tag{3}

Every edge has size $2^h$. A function in the problem is exactly an $n$-colouring of the vertices of (3) in which every edge contains every colour, i.e. an $n$-polychromatic colouring. Sets above rank $h$ can be coloured arbitrarily.

It is enough to check $h$-sets: if $Z\subseteq Y$, $|Z|=h$, then $\mathcal P(Z)\subseteq\mathcal P(Y)$. This reformulation is (a).

2.2 Eliminate the private top rank

Lemma (a). An $n$-polychromatic colouring of $\mathcal B_{n,h}$ exists if and only if the sets of size $<h$ can be $n$-coloured so that the proper subsets of every $h$-set miss at most one colour.

Proof. In a full colouring, the sole extra member of $E_Y$ beyond the proper subsets of $Y$ is $Y$ itself, so it can repair at most one missing colour. Conversely, if at most one colour is missing, give $Y$ that colour (or an arbitrary colour if none is missing). Distinct $h$-sets have distinct private top vertices, so all these choices are independent. $\square$

This removes the top-rank variables in the second SAT encoding below.

2.3 Monotonicity in the ground-set size

Lemma (a). If $(n,h)$ has a colouring and $h\leq m\leq n$, then $(m,h)$ has a colouring.

Proof. Restrict the domain to $\mathcal P(M)$ for an $m$-subset $M\subseteq[n]$, and compose the $n$ colours with any surjection $[n]\to[m]$. Every $h$-set in $M$ originally saw all $n$ colours, so after merging it sees all $m$ colours. $\square$

Consequently define the finite threshold

p(h)=\max\{n:H(n)\leq h\}. \tag{4}

The cardinality of an edge gives $p(h)\leq2^h$, and the lemma says the admissible $n$'s form an initial interval.

There is also an exact asymptotic reduction:

\boxed{\quad H(n)-\log _2n\longrightarrow\infty \quad\Longleftrightarrow\quad \frac{p(h)}{2^h}\longrightarrow0.\quad} \tag{5}

Indeed, if the left side holds, then

h-\log _2p(h)\geq H(p(h))-\log _2p(h)\to\infty.

Conversely, with $h=H(n)$, monotonicity gives $n\leq p(h)$, hence

H(n)-\log _2n\geq h-\log _2p(h)\to\infty.

This is (a) and isolates the precise missing uniform statement.

3. Verified exact small cases

3.1 Result

Under the convention that a threshold may be $0$,

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | $H(n)$ | 0 | 1 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 |

Equivalently,

p(0)=1,\qquad p(1)=2,\qquad p(2)=3,\qquad p(3)=6, \tag{6}

and

11\leq p(4)\leq15. \tag{7}

The values through $n=6$, apart from direct finite witness checking, have elementary lower bounds. The assertion $p(3)=6$, and therefore the sharp lower bounds at $n=7,8$, is (d) because its negative side is SAT-based. The witness side through $n=11$ is a direct finite certificate.

3.2 Explicit witnesses

The standalone verifier is erdos624_wavew003_verify.py. It encodes a subset by its integer bitmask. For the $(6,3)$ witness, on the masks of size $<3$, in increasing integer order, the colours are

0,4,5,1,1,3,4,4,2,2,3,2,1,1,4,5,3,1,1,2,5,5

For every triple, these proper subsets contain at least five of the six colours; the triple itself is assigned the unique missing colour (or $0$ if none is missing). This proves $p(3)\geq6$.

The analogous $(11,4)$ certificate contains 232 base colours, embedded verbatim in the verifier. Every 4-set's proper subsets contain at least ten of the eleven colours, and its private top set fills the possible missing colour. Its reconstructed full-colouring SHA-256 is

9fa1c20ec81706b7290af337642339998f1b78fc2e97f466fc6d651ce835dfc9

The $(6,3)$ full-colouring SHA-256 is

3b8e57b1b4e9a8fa1669f142a0469f9ee666ba512c3f5f72669e4de611a61c8c

The checker reconstructs both functions and directly enumerates every $Y$ of every size $\geq h$; it does not ask a solver to validate either witness. It then restricts and merges the $n=6$ witness for $4\leq n\leq6$ and the $n=11$ witness for $7\leq n\leq11$.

For $n=2,3,4$, the rank colouring $f(A)=|A|$ at $h=n-1$ gives the needed upper bounds.

3.3 Lower bounds in the table

If $2^h<n$, one edge has too few vertices to contain all $n$ colours.

This gives all cardinality lower bounds.

For $(n,h)=(4,2)$, every pair $Y=\{i,j\}$ has exactly four subsets,

so those four colours would have to be distinct. Hence the four singleton sets would be pairwise differently coloured and all different from $f(\varnothing)$, requiring five colours. Thus $H(4)=3$. This is (a).

The $(7,3)$ obstruction is the exhaustive computation in the next

section. Monotonicity also excludes $(8,3)$.

For $(16,4)$, every 4-edge has 16 vertices and would have to be rainbow.

Among the $\binom{16}{2}>16$ two-sets, two have the same colour. Their union has size at most four, so both lie in a common 4-edge, a contradiction. Together with the $n=11$ witness and monotonicity this proves (7). This is (a).

4. Reproducible $(7,3)$ obstruction

4.1 Direct CNF

For every $A\in {[7]\choose\leq3}$ and colour $c\in[7]$, introduce $x_{A,c}$. Add exactly-one clauses and

\bigvee_{A\subseteq Y}x_{A,c} \qquad(Y\in {[7]\choose3},\ c\in[7]). \tag{8}

This has 448 variables and 1653 base clauses.

On $Y_0=\{0,1,2\}$, eight subsets must use all seven colours, so exactly one unordered pair receives the duplicate colour. There are $\binom82=28$ cases. In each case colour names are canonically fixed by order of first occurrence; every possible solution is colour-isomorphic to one of them.

4.2 Independently generated reduced CNF

Using the top-rank lemma, retain only the 29 sets of size $<3$. For every triple $Y$ and pair of colours $c<d$, add

\left(\bigvee_{A\subsetneq Y}x_{A,c}\right) \ \vee\ \left(\bigvee_{A\subsetneq Y}x_{A,d}\right). \tag{9}

Clause (9) says that $c,d$ cannot both be missing, exactly the “at most one missing colour” condition. This encoding has 203 variables and 1373 base clauses.

The seven proper subsets of $Y_0$ use either seven colours or six colours with one duplicate. This gives $1+\binom72=22$ exhaustive canonical cases.

4.3 Cross-check

Both encodings were solved independently by CaDiCaL 1.9.5 and Glucose 4.2:

| encoding | solver | UNSAT cases | variables | base clauses | base-CNF SHA-256 | |---|---|---:|---:|---:|---| | full | CaDiCaL | 28/28 | 448 | 1653 | 9bf9976767976bf295b217c3038fdb2c63e9f2c6a588cf403caba5e79426c3cd | | full | Glucose | 28/28 | 448 | 1653 | same | | reduced | CaDiCaL | 22/22 | 203 | 1373 | 4f798d5af9c2d99d88bcb8f31591a5bf60405de28a312749f656794d7c0273bc | | reduced | Glucose | 22/22 | 203 | 1373 | same |

No DRAT/LRAT certificate is claimed. Thus this is deliberately labelled (d), not a solver-independent theorem. The two encodings, exhaustive symmetry proof, and two solver implementations make the computation reproducible and resistant to a single modelling/solver error.

The relevant generator is compactly:

# Full coverage clauses.
for Y in h_sets:
    for c in range(n):
        clauses.append([x[A, c] for A in submasks(Y)])

# Equivalent top-rank-eliminated clauses.
for Y in h_sets:
    for c in range(n):
        for d in range(c):
            clauses.append(
                [x[A, c] for A in proper_submasks(Y)]
                + [x[A, d] for A in proper_submasks(Y)]
            )

The complete executable implementation, including exactly-one clauses, canonical cases, both certificates, hashes, and direct checks, is in the standalone file.

Reproduction

python3 runs/erdos624_wavew003_verify.py

Observed output on this VM:

explicit witness checks: PASS
  n6_h3 full-colouring sha256=3b8e57b1b4e9a8fa1669f142a0469f9ee666ba512c3f5f72669e4de611a61c8c
  n11_h4 full-colouring sha256=9fa1c20ec81706b7290af337642339998f1b78fc2e97f466fc6d651ce835dfc9
full/cadical195: UNSAT 28/28; vars=448, base_clauses=1653
full/glucose42: UNSAT 28/28; vars=448, base_clauses=1653
reduced/cadical195: UNSAT 22/22; vars=203, base_clauses=1373
reduced/glucose42: UNSAT 22/22; vars=203, base_clauses=1373
exhaustive (n,h)=(7,3) obstruction: PASS (computational-only)
H(n), n=1..11: 1:0 2:1 3:2 4:3 5:3 6:3 7:4 8:4 9:4 10:4 11:4
p(0),p(1),p(2),p(3) = 1,2,3,6; 11 <= p(4) <= 15
ALL CHECKS PASSED

The full run takes about 3.4 seconds. A solver-free direct certificate check is also available:

python3 runs/erdos624_wavew003_verify.py --certificates-only

5. The next finite boundary and measured compute wall

The next exact question is $(n,h)=(12,4)$. It alone decides whether $p(4)=11$; if satisfiable, one continues only through $n=15$.

Three one-core attempts were capped:

direct encoding: 9528 variables, 59139 clauses, unresolved after about

150 seconds;

top-rank-eliminated encoding: 3588 variables, 52704 clauses, unresolved

after 180 seconds;

the reduced encoding plus canonical first-occurrence colour symmetry:

3588 variables, 55993 clauses, unresolved after 150 seconds.

No status is inferred from a timeout. Resolving this boundary responsibly would require a cube-and-conquer or partition-pattern split and proof logging. A realistic next pilot is 10--100 core-hours, roughly \$1--\$10 at \$0.10/core-hour, followed by an independent DRAT/LRAT check if UNSAT. The censored runs do not support a more confident runtime estimate.

6. Why the standard relaxation stalls asymptotically

The natural integer program has variables $x_{A,c}$ and constraints

\sum_c x_{A,c}=1,\qquad \sum_{A\subseteq Y}x_{A,c}\geq1. \tag{10}

Its symmetric fractional relaxation has

x_{A,c}=\frac1n.

For every $h$-edge and colour, the second left side is $2^h/n$, so this fractional point is feasible for the entire trivial range $n\leq2^h$. Therefore first-moment incidence counting and the basic set-cover LP cannot improve $p(h)\leq2^h$ at all.

By (5), the exact missing lemma is a genuinely integral, Boolean-interval-specific estimate

\mathsf p(\mathcal B_{n,h})<n \quad\text{whenever}\quad n\geq\varepsilon_h2^h,\qquad \varepsilon_h\to0, \tag{11}

or equivalently $p(h)=o(2^h)$. General cover-decomposition machinery gives useful lower bounds or approximation results for broad hypergraph classes; it does not provide the required upper bound (11). A proof must exploit the overlap/integrality structure of the lower Boolean intervals beyond (10). That is the precise asymptotic wall; the finite work above does not close it.

PARTIAL: For the unrestricted live statement, proved the threshold reduction $p(h)/2^h\to0$, supplied directly checked witnesses, and computationally established $H(n)=0,1,2,3,3,3,4,4,4,4,4$ for $1\le n\le11$; the asymptotic integrality lemma remains open.

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