5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Consider sets with $2^l$ elements first $\endgroup$ – Scipio Jun 4 '17 at 12:09
  • $\begingroup$ 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) $\endgroup$ – Bib-lost Jun 4 '17 at 12:11
  • $\begingroup$ $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. $\endgroup$ – Scipio Jun 4 '17 at 12:18
  • $\begingroup$ 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. $\endgroup$ – Bib-lost Jun 4 '17 at 12:44
  • $\begingroup$ Could you add the cases $n=2,3,4$ into your question & give us the lists $X_1, X_2 , \cdots , X_k$ ? $\endgroup$ – Donald Splutterwit Jun 4 '17 at 12:50
2
$\begingroup$

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.

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

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}$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Bib-lost Jun 4 '17 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.