Seperating $2n$ elements with subsets of size $n$

Suppose I have a set $X$ with $2n$ elements ($n$ nonzero natural number). I now want to find a collection of subsets $X_1, \ldots, X_k$ of $X$ such that

• Every $X_i$ contains $n$ elements.
• For every $x, y \in X$, there exists an $X_i$ such that $x \in X_i$ and $y \not\in X_i$ or $x \not\in X_i$ and $y \in X_i$ (the $X_i$ "seperate" the elements of $X$, in that the topology on $X$ generated by the $X_i$ is Kolmogorov)
• $k$ is minimal with respect to the above to properties.

An algorithm to find $X_1, \ldots, X_k$ would be great, but I am mostly looking for a way to calculate $k$. My intuition tells me that $k$ should be at least $\log_2(2n)$, more specifically I feel like $$\max_{x \in X} \# \lbrace y \in X \mid \not\exists i \in \lbrace 1, \ldots, j \rbrace : x \in X_i \enspace \& \enspace y \not\in X_i \rbrace \geq \log_2(\frac{2n}{j})$$ should hold for all $j \in \lbrace 1, \ldots, k \rbrace$, but I don't know how to prove this.

• Consider sets with $2^l$ elements first – Scipio Jun 4 '17 at 12:09
• I did; even if $n=4$ I don't see how to proceed. (i.e. I know that $k = 2$ is possible, but do not see how to show that $k = 1$ is impossible) – Bib-lost Jun 4 '17 at 12:11
• $X_1$ contains two elements $a,b$; clearly the second requirement doesn't hold for these two elements if you only have a single set. – Scipio Jun 4 '17 at 12:18
• By $n=4$ I meant the case where $X$ has $2*4 = 8$ elements. The case with $4$ elements is indeed clear. :) And surely, also the case with $8$ elements can be computed by hand in a reasonably short time; what I meant is that I do not see an argument which could somehow be generalised. – Bib-lost Jun 4 '17 at 12:44
• Could you add the cases $n=2,3,4$ into your question & give us the lists $X_1, X_2 , \cdots , X_k$ ? – Donald Splutterwit Jun 4 '17 at 12:50

Suppose $X$ contains $2^l$ elements. Let $(A_i^m)$ be the family of subsets of $X$ of non-separated elements after introducing $X_1, \cdots, X_m$, i.e. sets of elements for which the second requirement does not hold (check that these sets are well defined and uniquely partition $X$). Ultimately, we want that all the subsets $A_i$ contain just a single element (i.e. every element is separated from all other elements).

With each $X_i$ we want to separate as many elements as possible. Now, at first $A_1 = X$ containing $2^l$ elements and we take $X_1$ just an arbitrary set of $n$ elements. After this, we have sets $A_1$, $A_2$, both containing $2^{l-1}$ elements. Now, with $X_2$ we can again split both in half, resulting in four 'remaining sets' with $2^{l-2}$ elements. Continue recursively to see that $k=l$. Moreover, it is clear that after introducing $m$ sets, $\max_i \# A_i^m \geq 2^{l-m}$, so that our result is indeed optimal.

For example, start with $X = A_1^0 = \{1,2,3,4,5,6,7,8\}$. Introduce $X_1 = \{1,2,3,4\}$ to get $A_1^1 = \{1,2,3,4\}, A_2^1 = \{5,6,7,8\}$. Introduce $X_2 = \{1,2,5,6\}$ and $X_3 = \{1,3,5,7\}$ to finish the job. (Make sure to check the corresponding sets $(A_i^m)$.)

Now, for any other number of elements $2n$, your 'splits' wil not be optimal. You can check that $\max_i \# A_i^m \geq 2n\cdot2^{-m}$ still holds.

• So probably we have that, in general, $k$ is the unique integer satisfying $2^{k-1} < 2n \leq 2^{k}$? – Bib-lost Jun 4 '17 at 13:57
• yes exactly :) This hinges on the very last statement in my answer, so make sure to check that carefully. – Scipio Jun 4 '17 at 14:01

There should be $k=\lceil log_2(2n) \rceil$ partitions, $2k$ sets.

We have the conditions: $$\mathcal{P}_1:\forall X_i, \text{num}\{X_i\}=n$$ $$\mathcal{P}_2:\forall x_i,x_j \exists X_i, x_i \in X_i, x_j \not\in X_i$$

It is clear for sets of $2n=2^k$ elements, the partitions are binary, hence optimal. Under this case, the condition $\mathcal{P}_2$ implies the stronger: $$\mathcal{P}_{2b}:\forall x_i,x_j \exists X_i,X_j, x_i \in X_i, x_j \in X_j$$ because each partition requires its complement. If there is not complement, the property is not met. $$\forall X_i \exists Y_i=X -X_i$$

If the set contains $2n=2^k+2m$ elements, $2m<2^k$, each $2m$ remaining elements shall be included into different disjoint partitions. Again in this case the partition complement must exist and the condition $\mathcal{P}_{2}$ will not introduce any benefit against $\mathcal{P}_{2b}$.

• Don't you mean $k = \lceil \log_2(2n) \rceil$? Surely if $n=3$ you need at least $2 = \lceil log_2(6) \rceil$ partitions? – Bib-lost Jun 4 '17 at 14:14