Skip to main content
added 634 characters in body; deleted 10 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

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.

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

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.

Rollback to Revision 9
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

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.

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.

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

added 593 characters in body; added 31 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

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.

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

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.

added 1 characters in body; deleted 1 characters in body; Post Made Community Wiki
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
added 11 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
added 481 characters in body; deleted 3 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
edited body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
deleted 1 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
deleted 3 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
added 1 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
added 23 characters in body; added 1 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading