Approximating a partition

Question

Let $X = \{1,\ldots,2 \cdot n\}$ be a set of numbers. For this question, an equal partition $Y_1,Y_2$ of $X$ is a partition of $X$ to two equal sizes. Let $\varepsilon \in (0,1)$ be an error parameter. Define an $\varepsilon$-cover of $X$ of size $k$ as equal partitions $(Y^i_1,Y^i_2)_{i \in \{1,\ldots,k\}}$ such that the following holds: For any equal partition $Z_1, Z_2$ of $X$, there is $i \in \{1,\ldots,k\}$ such that $|Z_1 \cap Y^i_1| \geq (1-\varepsilon) \cdot n$. That is, an $\varepsilon$-cover contains a good approximation for any equal partition.

My question is what is the smallest size of an $\varepsilon$-cover? Can it be of size independent of $n$? can it be polynomial in $1/\varepsilon$?

This seems like a fundamental combinatorial question and I assume variants of this problem have been studied. However, I am unfamiliar with the right keywords to find such results. Any form of help would be very appreciated.

Answer 1

Right keyword is "covering codes". If instead of a partition you consider two $\{0,1\}$-vectors consisting of $n$ 1's and $n$ 0's (and summing up to the all-1 vector), you want to cover the set of all such vectors by $2k$ Hamming balls of radius $2\varepsilon n$. The standard entropy bound shows that the volume of every ball grows as $2^{H(2\varepsilon) n}$, where $H(t)=-t\log_2t-(1-t)\log_2(1-t)$, that gives $2^{(1-H(2\varepsilon))n}$ lower bound for $2k$.