Partitions that separate all subsets
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.
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:
- Let the 1st set of the 1st partition be
$\{\lfloor n/2\rfloor ,...,1\}$ - 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\}$
- 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$
$\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.