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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Dylan Thurston Apr 11 '11 at 12:24
  • $\begingroup$ @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. $\endgroup$ – Seva Apr 11 '11 at 14:15

As far as I know, a paper of Alon and Frankl "The Maximum Number of Disjoint Pairs in a Family of Subsets" (available here) contains state of the art knowledge on the problem.

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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Seva Apr 11 '11 at 20:14
  • 1
    $\begingroup$ @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. $\endgroup$ – Sergey Norin Apr 11 '11 at 21:14

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.