Erdős Problem a Daythe open tracker

Erdős Problem #624

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

The condition that an integer `m` ensures the existence of a function `f` covering `Fin n` for all large enough subsets `Y`. The property is invariant under bijection, so we use a representative `Fin n` for a finite set of size `n`.

Let \(H(n)\) be the minimum integer \(m\) such that there is a function \(f: \mathcal{P}(X) \to X\) where \(X\) is a finite set of size \(n\), such that for every subset \(Y \subseteq X\) with \(|Y| \ge m\), the set \(\{f(A) : A \subseteq Y\}\) covers \(X\).

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 \(\left\{ f(A) : A\subseteq Y\right\}=X\). Prove that \(H(n)-\log_2 n \to \infty\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/624.
Prizenone
Topicscombinatorics
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/624
WORKING REPORT BY THIS SITE · JUL 28, 2026

Read our working report →

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\l

PARTIAL