Partitions that separate all subsets

Question

Let $A=\{1,2,\dots,n\}$ and let $\mathcal{A}_1,\dots,\mathcal{A}_k$ be partitions of $A$ into two sets. Suppose that for each subset $B\subseteq A$ of even size, there exists a partition $\mathcal{A}_i$ such that half the elements of $B$ is in one part of the partition and the other half is in the other part. What is the minimum possible $k$ for which this is possible?

An asymptotic bound for $k$ would already be good enough. For example, can we use just $k=O(n)$ partitions? Or even some polynomial in $n$ partitions?

If we only consider subsets $B$ of size two, then we can do it with $\log n$ partitions by writing each element of $A$ in base two and have $\mathcal{A}_i$ be the partition according to whether the $i$th digit is $0$ or $1$. However this does not work when $B$ is of arbitrary size: For example among the four numbers $001,010,011,111$, none of the digits has $0$ and $1$ appearing twice each.

Answer 1

$\def\FF{\mathbb{F}}$ The construction of lasen H is optimal.

Suppose that we have $k$ partitions with the desired property. We encode these partitions as vectors $\vec{v}_1$, $\vec{v}_2$, ..., $\vec{v}_k \in \FF_2^n$ where we put a $1$ in the $j$-th coordinate of $\vec{v}_i$ if $j$ is in the first part of the $i$-th partition. We also set $\vec{v}_0 = (1,1,\ldots, 1)$.

Define the subspace $W$ of $\FF_2^n$ by $$W = \{ \vec{w} : \vec{v}_0 \cdot \vec{w} = 0 \ \mbox{and} \ \vec{v}_1 \cdot \vec{w} = \vec{v}_2 \cdot \vec{w} = \cdots = \vec{v}_k \cdot \vec{w} \}.$$ Since $W$ is defined by $k$ linear equations, $\dim W \geq n-k$. Define the quadratic form $Q$ on $\FF_2^n$ by $Q(x_1, x_2, \ldots, x_n) = \sum_{i<j} x_i x_j$.

Now, let $\vec{w} \in W$ and let $B = \{ j : \vec{w}_j =1 \}$. Since $\vec{v}_0 \cdot \vec{w} = 0$, the size of $B$ is even, say $B = 2m$. There is supposed to be some partition $(X_i, Y_i)$ where $|X_i \cap B| = |Y_i \cap B|$. For this $i$, we have $\vec{v}_i \cdot \vec{w} = m$. By the defining equations of $W$, we also have $\vec{v}_1 \cdot \vec{w} = m$.

We also have $Q(\vec{w}) = \binom{2m}{2} \equiv m \bmod 2$. So $Q(\vec{w}) = \vec{v}_1 \cdot \vec{w}$ for all $\vec{w} \in W$.

We therefore deduce, for $\vec{x}$ and $\vec{y}$ in $W$, that $Q(\vec{x}+\vec{y}) = Q(\vec{x}) + Q(\vec{y})$. Writing $\vec{x} = (x_1, \ldots, x_n)$ and $\vec{y} = (y_1, \ldots, y_n)$, we have $$0 = \sum_{i<j} {\Big (} (x_i+x_j)(y_i+y_j) - x_i x_j - y_i y_j {\Big )} = \sum_{i<j} (x_i y_j + x_j y_i) = \sum_{i \neq j} x_i y_j$$ $$= \left( \sum_i x_i \right) \left( \sum_j y_j \right) - \sum_r x_r y_r = (\vec{v}_0 \cdot \vec{x}) (\vec{v}_0 \cdot \vec{y}) - \vec{x} \cdot \vec{y}$$ for all $\vec{x}$, $\vec{y} \in W$. But, for $\vec{x} \in W$ we have $\vec{x} \cdot \vec{v}_0 =0$. So we deduce that $\vec{x} \cdot \vec{y} =0$ for $\vec{x}$ and $\vec{y} \in W$.

In other words, $W \subseteq W^{\perp}$, so $\dim W \leq n - \dim W$. Combined with $\dim W \geq n-k$, we have $n-k \leq n-(n-k)$ so $n/2 \leq k$. Since $k$ is an integer, we can improve this to $\lceil n/2 \rceil \leq k$, which is lasen H's bound.

Answer 2

This is sub-optimal, but gives a first bound.

Let $k_n$ be the solution for $n$. Notice that $k_2=1$, given by the single partition $\{\{1\},\{2\}\}$, and $k_3=2$ by e.g. $\{\{1,2\},\{3\}\}$ and $\{\{1\},\{2,3\}\}$. Suppose we have $k_{n'}$ for all $n'\le n+1$, and that we want to find $k_{n+2}$. Let $B\subseteq[n+2]$, we try to construct a set of partitions solving the problem.

• If $B\subseteq[n]\subset[n+2]$, then we can simply consider the partitions solving the problem for $[n]$ and add to them $n+1$ and $n+2$ in any way we like.
• If $B$ contains both $n+1$ and $n+2$, then we can take the partition $X\sqcup Y=[n]$ of the solution of the problem for $n$, and consider $X':=X\cup\{n+1\}$ and $Y':=Y\cup\{n+2\}$.

Therefore, these possibilities are covered by considering $k_n$ partitions. Further, if $B$ contains $n+1$ but not $n+2$ (or vice versa), then let $m$ be the biggest element of $B\cap[n]$. Let $X\sqcup Y=[m-1]$ be the solution for the problem for $m-1$ and $B\cap[m-1]$ and consider $X':=X\cup\{m,...,n\}$ and $Y':=Y\cup\{n+1,n+2\}$. Then $X'\cup Y'=[n+2]$ solves the problem. This proves that $$k_{n+2}\le\sum_{i=0}^nk_n\ ,$$ which is pretty obviously bounded by the sequence of Fibonacci with $F_0=F_1=1$, $$k_n\le F_{n-1},\qquad n\ge2\ .$$ So we have for example $$k_4\le3,\qquad k_5\le5,\qquad k_6\le8\ ,$$ and so on.

---

Notice that in fact we have $k_4=2$ by taking $$\{\{1,3,\},\{2,4\}\},\{\{1,2\},\{3,4\}\}\ ,$$ already proving that the bound given above is not optimal.

Answer 3

I brute forced with $n$ going from 2 to 8. The minimum $k$ for those $n$ were $1,2,2,3,3,4,4$. I looked at the minimal set of partitions, and noticed that they could be constructed like this:

1. Let the 1st set of the 1st partition be
   $\{\lfloor n/2\rfloor ,...,1\}$
2. To get the 1st set of the 2nd partition change the 1st value to the smallest unused value $\{\lfloor n/2\rfloor+1 ,\lfloor n/2\rfloor-1,...,1\}$
3. To get the 1st set of the 3rd partition change the 2nd value to the smallest unused value
   $\{\lfloor n/2\rfloor+1 ,\lfloor n/2\rfloor+2,\lfloor n/2\rfloor-2,...,1\}$

and continue until you have the first set of $\lfloor (n+1)/2\rfloor$ partitions. The other sets must be complements to the first ones.

Using this construction I continued for $n=9,...,22$, and found that $5,5,6,6,7,7,8,8,9,9,10,10,11,11$ partitions suffice. However for these $n$ I didn't brute force to confirm minimality. I know this is no answer until I have a proof for the sufficiency of $\lfloor (n+1)/2\rfloor$

Answer 4

We can prove a lower bound of order $\sqrt{n}$. Let $\mathcal{A}_i$ be the pair $(X_i, Y_i)$ and set $|X_i| = x_i$ so $|Y_i| = n - x_i$.

Lemma There are precisely $\binom{n}{x_i}$ subsets $B$ of $[n]$ such that $|B \cap X_i| = |B \cap Y_i|$.

Proof We biject these sets $B$ with the subsets $C$ of $[n]$ of cardinality $x_i$. Specifically, $B \mapsto (X_i \setminus B) \cup (Y_i \cap B)$. $\square$

You want each of the $2^{n-1}$ even subsets of $[n]$ to occur as such a $B$ for at least one index $i$. Therefore, $$2^{n-1} \leq \sum_i \binom{n}{x_i}.$$ We have $\binom{n}{x_i} \leq 2^n/\sqrt{\pi n/2}$ (see here for a similar bound) so there must be at least $\sqrt{\pi n/8}$ terms in the sum.