5
$\begingroup$

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$?

$\endgroup$

4 Answers 4

7
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks @Bill . Your construction shows that $O(\log n)$ sets are enough. $\endgroup$
    – Masood
    Nov 5, 2015 at 14:29
6
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Boy this is a lot better than my answer. Why do we need $\Theta(\log n)$ subsets? It seems like your construction would extend to $n = 2 \bmod 4$ with 9 sets or so. $\endgroup$ Nov 5, 2015 at 15:23
  • $\begingroup$ Right, to cover every pair, $O(1)$ subsets suffice. To separate every pair, there need to be $\Theta(n)$, and I think that's what your construction was trying to do. $\endgroup$ Nov 5, 2015 at 15:27
  • $\begingroup$ Ah, I see. For completeness, I added the "not divisible by 4" case. $\endgroup$ Nov 5, 2015 at 15:43
  • $\begingroup$ Oops, in my previous comment, I meant $\Theta(\log n)$ not $\Theta(n)$.. $\endgroup$ Nov 5, 2015 at 16:01
  • 1
    $\begingroup$ There are a lot of resources available. For some parameters, the La Jolla Covering Repository is a great resource: ccrwest.org/cover.html. That doesn't have much theory, though. There are some basic inequalities which might be mentioned at the starts of most papers on covering designs. $\endgroup$ Nov 5, 2015 at 17:02
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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