Logo
All Random Solved Random Open
OPEN
Let $X$ be a finite set of size $n$ and $H(n)$ be such that there is a function $f:P(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.\]
A problem of Erdős and Hajnal [ErHa68] who proved that \[\log_2 n \leq H(n) < \log_2n +(3+o(1))\log_2\log n.\] Even the weaker statement that for $n=2^k$ we have $H(n)\geq k+1$ is open.

For this weaker statement, Erdős and Gyárfás conjecture the stronger form that if $\lvert X\rvert=2^k$ then, for any $f:P(X)\to X$, there must exist some $Y\subset X$ of size $k$ such that \[\#\{ f(A) : A\subseteq Y\}< 2^k-k^C\] for every $C$ (with $k$ sufficiently large depending on $C$).