11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I have a draft proof that $k=\Omega(\sqrt{n})$, but lasen H’s answer suggests that this bound can be improved. $\endgroup$ – Alex Ravsky Aug 3 '17 at 5:20
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is kind of whiny of me, but I am confused as to why this didn't get more upvotes. Combined with lasen H's construction, this is a complete solution, which none of the other answers are. $\endgroup$ – David E Speyer Aug 11 '17 at 0:45
  • $\begingroup$ Based on math.meta.stackexchange.com/a/3006/197161, maybe consider marking your answer CW and incorporating lasen H's answer + Alex Ravsky's comment to make a complete answer? $\endgroup$ – stewbasic Aug 16 '17 at 3:25
  • 1
    $\begingroup$ @Andy Hmm, trying to remember. First of all, I had already seen arguments like this one: See gowers.wordpress.com/2008/07/31/… for easier examples. And I recognized Gower's heuristic "If you want to find the maximum of a combinatorial quantity, and if the maximum seems to be very far from uniquely attained, then try to relate the quantity to the dimension of a certain vector space" as relevant. $\endgroup$ – David E Speyer Feb 1 '18 at 3:42
  • 1
    $\begingroup$ Pairwise intersections --> dot product and a condition about evenness --> I should use $\mathbb{F}_2$. But how to get at "half the size of an even set"? Some experimentation suggested that simply asking for $A_i \cap B \equiv \tfrac{1}{2} |B| \bmod 2$ was enough, so I needed a formula which took a vector in $\mathbb{F}_2^n$ with $2m$ ones and returned $m$. I remembered that $\binom{k}{2} \bmod 2$ is periodic modulo $4$, so a quadratic form could work, and there are a lot of tools for analyzing quadratic forms. $\endgroup$ – David E Speyer Feb 1 '18 at 3:47
  • 1
    $\begingroup$ At that point, I was sure something would work. It then took a bunch of editing to make it this neat; the first draft was much hairier. $\endgroup$ – David E Speyer Feb 1 '18 at 3:47
7
+50
$\begingroup$

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$

$\endgroup$
  • 3
    $\begingroup$ Very good! The sufficiency follows from “discrete continuity” intermediate value property. Let $n^*=\lfloor (n+1)/2\rfloor$. Given a subset $B$ of $A$ of even size $2r$, for each $1\le i\le n^*$ let $a_i$ be the size of the intersection of $B$ with the 1st set of the $i$-th partition. By the constructions of the partition sets, $|a_i-a_{i+1}|\le 1$ for each $1\le i\le n^*-1$ and $2r-1\le a_1+a_{n^*}\le 2r+1$. The latter implies that if $a_1<r$ then $a_{n_*}\ge r$ and if $a_1>r$ then $a_{n_*}\le r$. Hence there exists $1\le i\le n^*$ such that $a_i=r$, so the $i$-th partition is the required. $\endgroup$ – Alex Ravsky Aug 3 '17 at 5:14
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1, but shouldn't it be $\sqrt{n \pi/ 8}$? $\endgroup$ – lasen H Aug 4 '17 at 17:13
  • $\begingroup$ @lasenH Thanks for the correction! $\endgroup$ – David E Speyer Aug 4 '17 at 17:40
1
$\begingroup$

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.

$\endgroup$

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.