# How to keep subsets disjoint?

Given positive integers $n$ and $k\le 2^n$, how to choose a subset $C\subset\{0,1\}^n$ of size $|C|=k$ to maximize the number of pairs $(c_1,c_2)\in C\times C$ with the supports of $c_1$ and $c_2$ disjoint (in other words, with $c_1$ and $c_2$ orthogonal)? If $k=1+n+...+\binom ns$, should one choose $C$ to be the set of all vectors with at most $s$ coordinates equal to $1$?

Some equivalent restatements:

• How to choose a family of $k$ subsets of a fixed $n$-element set to maximize the number of pairs of disjoint subsets?

• How to choose a binary code of length $n$ and size $k$ to maximize the number of pairs of codewords with disjoint supports?

• How to choose a simplicial complex on $n$ vertices with $k$ faces to maximize the number of pairs of disjoint faces?

(For the last restatement observe that the optimal set $C$ is monotonic, aka "downset".)

UPDATE As indicated by Sergey Norin (see his answer below), this problem originates from a question of Erdos, and is considered in a 1985 paper by Alon and Frankl. However, establishing a rather strong result for $k$ "small", their paper does not give any information in the case where $k=2^{\gamma n}$ with $\gamma>1/2$.

DISCUSSION There is interesting phenomenon here which seems to be unexplored as yet. For (roughly) $k<2^{n/2+\epsilon}$, a construction from Alon-Frankl shows that the number of pairs can be $\Omega(k^2)$ for a suitable choice of $C$. However, for $k>2^{\gamma n}$ with $\gamma>1/2$, this construction does not work. Indeed, it is not difficult to show that for $k$ "large" the situation breaks in the sense that $\Omega(k^2)$ cannot give the right order of magnitude any longer. It is quite possible that in this case, the set of all vectors with small support is optimal, exhibiting a kind of threshold behavior.

-
For the last point, presumably you mean that there is an optimal C that is monotonic, since if C is not monotonic, you can replace any element of C by a subset without making anything worse. – Dylan Thurston Apr 11 '11 at 12:24
@Dylan: correct. If C contains a vector $c$, and does not contain a vector $c_0$ lying below $c$, then replacing $c$ with $c_0$ in $C$ can only increase the number of pairs of vectors with disjoint supports. – Seva Apr 11 '11 at 14:15

Briefly outlining some of its conclusions, let me mention that for a wide range of values of $k$ keeping the sets in $C$ supported on disjoint subsets of $[n]=\{1,2,\ldots,n\}$ works much better than keeping them individually small. For example, for even $n$ and $k=2^{n/2 +1}-1$, if we choose $C$ to consist of sets of smallest possible size than typical set in $C$ will have size $\Omega(n/\log{n})$ and two such sets almost surely intersect. On the other hand, if we choose $A$ to be the set of all subsets of $\{1,\ldots,n/2\}$, $B$ to be the set of all subsets $\{n/2+1, \ldots, n\}$ and $C =A \cup B$, then at least half of the pairs of sets in $C$ are disjoint. Solving a problem of Erdős, Alon and Frankl show that this example is essentially the best possible.
I am excited to learn that the problem dates back to Erdos, and that it was studied in a 25+ year old paper by Alon and Frankl! On the other hand, upon looking at their paper, it seems to give a strong conclusion for $k$ "small", but does not address the case where $k$ is about $2^{\gamma n}$ with $\gamma>1/2$. – Seva Apr 11 '11 at 20:14
@Seva: In Alon & Frankl's paper it is shown that for families of subsets of size $m=2^{(1/2+\delta)n}$ the number of pairs is at most $m^{2 - \delta^2/2}$. This is not exact, but does provide some information. It would be interesting to improve on this bound and a quick internet search provided no indication that anybody did. – Sergey Norin Apr 11 '11 at 21:14