Selecting subsets with size $\frac{n}{2}$ covering every pair of the elements

Question

Given a set $S$ of $n$ elements. Let $T$ be the set of all subsets of $S$, with size $\frac{n}{2}$ ($n$ is even). We want to select a subset $T'$ of $T$, with the property that for any pair of the elements $x,y \in S$, there exists a subset $Q \in T'$, such that $x \in Q$ and $y \in Q$. What is the minimum size of $T'$? In particular, is $|T'| < n$?

Answer 1

The answer is $6$ for $n \ge 4$. This is problem 1.3 on IMC 2013:

http://www.imc-math.org.uk/imc2013/IMC2013-day1-solutions.pdf

---

It takes $6$ subsets.

Lower bound: For any element $a$, to cover all $n-1 \gt 2(n/2 -1)$ pairs of elements including $a$, there must be at least $3$ subsets containing $a$. This is true for all elements so there must be at least $3n$ pairs $(e,Q), e\in Q$. Each subset contributes $n/2$ pairs $(e,Q), e \in Q$ so there must be at least $6$.

Construction: Write $n/2$ as $2s+3t$ with $s,t$ nonnegative integers. Break the elements into sets $A,B,C,D$ of size $s$ and $X',X'',Y',Y'',Z',Z''$ of size $t$, with $X= X' \cup X'', Y=Y'\cup Y'',Z = Z' \cup Z''$. Then consider the unions of $\{A,B,X,Y'\},$ $\{C,D,X,Y''\},$ $\{A,C,Y,Z'\},$ $\{B,D,Y,Z''\},$ $\{A,D,Z,X'\},$ and $\{B,C,Z,X''\}.$

Answer 2

If $n$ is a power of two (i.e. if $n=2^m$), you can do quite a bit better-- you can take $|T'|=O(\log(n))$.

Interpret the elements of $S$ as $m$-bit binary strings. Let $U_i^0$ be the set of elements for which the $i$-th bit is zero, and $U_i^1$ be the set of elements for which the $i$-th bit is one. This separates $S$ in half, so $|U_i|=n/2$. Let $\overline{x}$ be the bitwise complement of $x$ (i.e. we switch all the zeroes to ones and ones to zeroes in the binary string).

If $y\neq \overline{x}$, then there exists some $i$ such that the $i$-th bit of $x$ and $y$ are equal. Suppose the $i$-th bit is $b$. In that case, $x,y\in U_i^b$.

So, we just need to deal with the case where $x=\overline{y}$. Take all the (disjoint) $n/2$ pairs of the form $(x,\overline{x})$. Choose half (i.e. $n/4$) of these pairs, take the union, and call that set $V^0$; call the complement $V^1$. Then if $y=\overline{x}$, either $(x,y)$ is in $V^0$ or $V^1$.

This achieves your condition with $2m+2=O(\log(n))$ sets.

Answer 3

It takes at least $5$ and at most $7$ subsets of size $n/2$ to cover every pair, for $n \ge 4$.

Since ${n/2 \choose 2} \lt {n \choose 2}/4$ for $n \ge 4$, at least $5$ are necessary.

If $n$ is divisible by $4$, you can do this with $6$ subsets. Divide the set into subsets of equal sizes, $S_1, S_2, S_3, S_4$. Then take $\lbrace S_i \cup S_j \rbrace$ with $i \ne j$. This is the best possible for $n=4$, and I think it is the best possible for larger $n$ divisible by $4$.

If $n$ is not divisible by $4$, you can cover all pairs with $7$ subsets. Divide the set into disjoint subsets $S_1,S_2,S_3,S_4$ of size $|S_i|=(n-2)/4$. There will be two "extra" elements; let us call them $a$ and $b$. Then take $S_1 \cup S_2 \cup \{a\}$, $S_3 \cup S_4 \cup \{a\}$, $S_1 \cup S_3 \cup \{b\}$, $S_2 \cup S_4 \cup \{b\}$. Then augment $S_1 \cup S_4$ and $S_2 \cup S_3$ by any one element each, and augment $\{a,b\}$ by any $n/2 - 2$ elements.

Usually, when people look at covering designs, the sizes of the blocks are much smaller than $n/2$.

In case you want to separate every pair of elements, then you need $\Theta(\log n)$ subsets.

Answer 4

This is a long comment:

Consider a bipartite graphs, with the subsets of size $n/2$ as vertices on the left, and pairs of elements on the right. An edge goes from a subset $S_i$ to a pair, if that pair is a subset of $S_i$.

Add axillary vertices $A$, connected to all subsets, and $Z$, connected to all pair vertices. Set weight $1$ on all edges from the pairs to $Z$, and weight $\infty$ on all other verices. Something that satisfies your condition is a maximal flow from $A$ to $Z$.

Perhaps it is possible to encode minimality on the number of subsets into this formulation...