Existence of a function on some sets Let $A$ be a set of size $k^2$, and let $B$ be another set. Assume that there exists a function $f : A \times B \to \{1,2\}$ such that the following holds:
For every subset $A' \subseteq A$ of size $k$ and every function $g:A' \to \{1,2\}$, there exists $x \in B$ such that $f(y,x) = g(y)$ for every $y \in A'$.
Clearly, we must have $|B| =\Omega(2^k)$. What is the best asymptotic lower bound on $|B|$ in terms of $k$? e.g. is it possible that $|B| = O(2^k)$ or we must have something like $|B| = \Omega(2^{k\log{k}})$?
 A: Not an answer, but instead a construction for $|B| = {k^2 \choose k}$, which (after some manipulation via Sterling's approximation) is $ \Theta(2^{k\log k})$ if I'm not mistaken.
Each $b \in B$ represents a different size-$k$ subset $S_b$ of elements of $A$, i.e., $|S_b| = k$.  There are obviously $|B| = {k^2 \choose k}$ such subsets.
$\forall a \in A, b\in B,$ define $f(a,b) = 1$ if $a \in S_b$, and $= 2$ if $a \notin S_b$.
Now consider any size-$k$ $A' \subset A$.  Any function $g: A' \to \{1,2\}$ partitions $A'$ into $C_g = \{a' \in A' | g(a') = 1\}$ and $D_g = \{a' \in A' | g(a') = 2\}$.  So, simply find $S_b$ s.t. $C_g \subset S_b$ and $D_g \cap S_b = \emptyset$.  I.e., $S_b = C_g \cup E$ where $|E| = k-|C_g|$ and $E \subset A - A'$.  Such an $E$ can always be found because  $|A - A'| = k^2 - k \ge |E| = k - |C_g|$ for $k \ge 2$.  Finally, we have:


*

*$g(a') = 1 \implies a' \in C_g \subset S_b \implies f(a',b) = 1$, and,

*$g(a') = 2 \implies a' \in D_g \implies a' \notin S_b \implies f(a',b) = 2$, as required.
This answer can be slightly improved by $B$ having $1+ {k^2 \choose k-1}$ elements: corresponding to every $(k-1)$-subset of $A$, plus one extra element $b^*$ where $f(a,b^*)=1$ for all $a$.  But this does not really move the asymptotics appreciably closer to $O(2^k)$.
