For $[n] := \{1,...,n\}$, let $G$ be the set of all $\lceil n/2\rceil$-subsets of $[n]$. For a permutation $\rho \in S_{n}$, and some $F \subset G$, define $\rho(F)$ in the natural way: apply $\rho$ to each element in every set in $F$ and let $\rho(F)$ be the set of these new subsets. For example, if $F = \{ \{1,2\}, \{3,4\} \}$, and $\rho = 3241$ (in one-line notation), then $\rho(F) = \{\{2,3\},\{1,4\}\}$. Obviously $|\rho(F)| = |F|$.
Fixing some integer $k$, is there anything we can say about $K(n,k) := \min_{F \subset G, |F| = k} \max_{\rho \in S_n} |F \cup \rho(F)|$?
By symmetry considerations, for a fixed $F$, every $\lceil n/2\rceil$-subsets of $[n]$ is contained in the same number of $\rho(F)$'s, so for an "average" $\rho$ we have $\frac{|F \cap \rho(F)|}{|F|} = \frac{|F|}{|G|}$. That is, we can always find a $\rho$ such that $|F \cap \rho(F)| \leq \frac{|F|^2}{|G|}$. Then, $K(n,k) \geq 2k - \frac{k^2}{n \choose \lceil n/2 \rceil}$.
The question is, can we always (ever?) do much better than this average?
