Set mappings on subsets of an $n$-set: prove $H(n)-\log_2 n\to\infty$ (Erdős #624)
Statement
Let $X$ be a finite set of size $n$, and let $H(n)$ be the minimal integer such that there exists a function $f:\{A : A\subseteq X\}\to X$ (assigning to every subset of $X$ an element of $X$) with the property that for every $Y\subseteq X$ with $\lvert Y\rvert \geq H(n)$ the images of the subsets of $Y$ cover all of $X$: $$\{ f(A) : A\subseteq Y\}=X.$$ Prove that $$H(n)-\log_2 n \to \infty.$$ (Since $Y$ has only $2^{\lvert Y\rvert}$ subsets, trivially $H(n)\geq \log_2 n$; the conjecture says the truth exceeds this trivial bound by an unbounded amount.)
Acceptance. FULLY RESOLVES: a complete proof that $H(n)-\log_2 n\to\infty$ — machine-checkable (Lean, e.g. against the formal-conjectures statement) preferred, else a full written proof; OR a disproof: an explicit construction of functions $f$ (for an infinite sequence of $n$) witnessing $H(n)\leq \log_2 n + O(1)$, with proof of the covering property. A finite computation alone cannot close this. ADVANCES: exact values of $H(n)$ for small $n$, each certified by (a) an explicit $f$ achieving threshold $H(n)$ and (b) an exhaustiveness certificate (SAT/ILP or search transcript a program can re-check) that no $f$ achieves a smaller threshold; a proof that $H(n)\geq \log_2 n + c$ for a constant $c$ strictly larger than the additive gap established by Alon's argument stated in the background; an improvement of the Erdős–Hajnal upper bound below the $(3+o(1))\log_2\log_2 n$ error term stated in the background; or a quantitative strengthening of Alon's $(1-c)2^k$ theorem with an explicit constant. Deliver the proof file, or the search code plus per-$n$ certificates and the table of exact values.
Background
A problem of Erdős and Hajnal [ErHa68], repeated by Erdős in [Er99]; listed as open on erdosproblems.com/624 (fetched 2026-07-13, status 'open'). Erdős and Hajnal proved the two-sided bound $\log_2 n \leq H(n) < \log_2 n + (3+o(1))\log_2\log_2 n$, so the conjecture lives entirely inside an additive $O(\log\log n)$ window. Erdős remarked that even the weak statement $H(2^k)\geq k+1$ was open, but Alon supplied a short pigeonhole proof (recorded on the problem page): among the 2-element subsets of $X$ some $(n-1)/2$ share the same image, and a $k$-set $Y$ containing enough of them cannot have all of $X$ in its image set. Erdős and Gyárfás conjectured a stronger failure at size $k=\log_2 n$: for $\lvert X\rvert = 2^k$ and any $f$, some $Y$ of size $k$ has $\#\{f(A):A\subseteq Y\} < 2^k - k^C$ for every constant $C$ (for $k$ large in terms of $C$). Alon proved this in the stronger form that some $Y$ of size $k$ has $\#\{f(A):A\subseteq Y\} < (1-c)2^k$ for an absolute constant $c>0$; in the other direction Alon constructed, for large $k$, an $f$ such that every $Y$ of size $k$ satisfies $\#\{f(A):A\subseteq Y\} > \tfrac{1}{4}2^k$. So the coverage at the trivial threshold is now well understood, while the actual conjecture $H(n)-\log_2 n\to\infty$ remains open. A formal Lean statement exists in the google-deepmind/formal-conjectures repository (ErdosProblems/624.lean). The attacker's tool: SAT/ILP determination of exact values of $H(n)$ for small $n$ (none appear in the literature or OEIS — a fresh checkable data frontier), plus probabilistic and entropy arguments to widen the additive gap asymptotically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #624 (T. F. Bloom) | website |
| REF-02 | Formal Lean statement of Erdős #624 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.