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_2n.\]Erdős said that even the weaker statement that for $n=2^k$ we have $H(n)\geq k+1$ is open, but Alon has provided the following simple proof: by the pigeonhole principle there are $\frac{n-1}{2}$ subsets $A_i$ of size $2$ such that $f(A_i)$ is the same. Any set $Y$ of size $k$ containing at least $k/2$ of them can have at most\[2^k-\lfloor k/2\rfloor+1< 2^k=n\]distinct elements in the union of the images of $f(A)$ for $A\subseteq Y$.

For this weaker statement, Erdős and Gyárfás conjectured the stronger form that if $\lvert X\rvert=2^k$ then, for any $f:\{A : A\subseteq 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$). This was proved by Alon (personal communication), who proved the stronger version that there exists some absolute constant $c>0$ such that, if $k$ is large enough, there must exist some $Y\subset X$ of size $k$ such that\[\#\{ f(A) : A\subseteq Y\}<(1-c)2^k.\]Alon also proved that, provided $k$ is large enough, if $\lvert X\rvert=2^k$ there exists some $f:\{A: A\subseteq X\}\to X$ such that, if $Y\subset X$ with $\lvert Y\rvert=k$, then\[\#\{ f(A) : A\subseteq Y\}>\tfrac{1}{4}2^k.\]

View the LaTeX source

This page was last edited 27 October 2025.