Revisions to The maximal size of intersection of two sets

added a top-level tag; https://meta.mathoverflow.net/questions/1457/why-are-mo-tags-formatted-as-they-are

Link

edited Nov 13, 2018 at 9:45

Martin Sleziak

4.7k
4
35
40

co.combinatorics linear-algebra

improved formatting

Source Link

edited Nov 10, 2018 at 1:42

kodlu

10.4k
2
36
55

Let $S=\{1,2,\cdots,2n\}$, and $S_i \subseteq S(i=1,2,\cdots,n+1)$ be $n+1$ subsets, each of which contains half of the $2n$ elements, namely $|S_i|=n$. Consider the following expression: $$M=\max_{1\le i<j \le n+1} |S_i \cap S_j|$$

When $n$ is even, it seems that $M\ge n/2$ for any choice of $S_i$. I think it is a really interesting phenomenon, but how does one give a proof of this?

Also by experiment, I find that$\{(i,j):1\le i<j \le n+1,|S_i \cap S_j|\ge n/2\}$ is $\Omega(n)$, not only one pair.

This question can be generalized to the following one: Let $S=\{1,2,\cdots,n\}$, and $S_i \subseteq S$ be $m$ subsets of $S$, each of which contains exactly $k$ elements. Can the maximal size of $|S_i \cap S_j|(1\le i<j \le m)$ be bounded from below?

This question can be changed to a real version. Consider $x_i \in [0,1]^n$ be $m$ vectors, each of which has a fixed norm: $\| {x_i}\|_2=k$. Can the maximal inner product of $x_i \cdot x_j(1\le i<j \le m)$ be bounded from below?

When $n$ is even, it seems that $M\ge n/2$ for any choice of $S_i$. I think it is a really interesting phenomenon, but how does one give a proof of this.

Also by experiment, I find that$\{(i,j):1\le i<j \le n+1,|S_i \cap S_j|\ge n/2\}$ is $\Omega(n)$, not only one pair.

This question can be generalized to the following one: Let $S=\{1,2,\cdots,n\}$, and $S_i \subseteq S$ be $m$ subsets of $S$, each of which contains exactly $k$ elements. Can the maximal size of $|S_i \cap S_j|(1\le i<j \le m)$ be bounded from below?

This question can be changed to a real version. Consider $x_i \in [0,1]^n$ be $m$ vectors, each of which has a fixed norm: $\| {x_i}\|_2=k$. Can the maximal inner product of $x_i \cdot x_j(1\le i<j \le m)$ be bounded from below?

Maybe the third and fourth question are hard, but if they can be solved, I think the results will be very useful. Also, the correctness of the first two questions have been checked for a few instances.

Let $S=\{1,2,\cdots,2n\}$, and $S_i \subseteq S(i=1,2,\cdots,n+1)$ be $n+1$ subsets, each of which contains half of the $2n$ elements, namely $|S_i|=n$. Consider the following expression: $$M=\max_{1\le i<j \le n+1} |S_i \cap S_j|$$

When $n$ is even, it seems that $M\ge n/2$ for any choice of $S_i$. I think it is a really interesting phenomenon, but how does one give a proof of this?

Also by experiment, I find that$\{(i,j):1\le i<j \le n+1,|S_i \cap S_j|\ge n/2\}$ is $\Omega(n)$, not only one pair.

This question can be generalized to the following one: Let $S=\{1,2,\cdots,n\}$, and $S_i \subseteq S$ be $m$ subsets of $S$, each of which contains exactly $k$ elements. Can the maximal size of $|S_i \cap S_j|(1\le i<j \le m)$ be bounded from below?

This question can be changed to a real version. Consider $x_i \in [0,1]^n$ be $m$ vectors, each of which has a fixed norm: $\| {x_i}\|_2=k$. Can the maximal inner product of $x_i \cdot x_j(1\le i<j \le m)$ be bounded from below?

Maybe the third and fourth question are hard, but if they can be solved, I think the results will be very useful. Also, the correctness of the first two questions have been checked for a few instances.

Let $S=\{1,2,\cdots,2n\}$, and $S_i \subseteq S(i=1,2,\cdots,n+1)$ be $n+1$ subsets, each of which contains half of the $2n$ elements, namely $|S_i|=n$. Consider the following expression: $$M=\max_{1\le i<j \le n+1} |S_i \cap S_j|$$

When $n$ is even, it seems that $M\ge n/2$ for any choice of $S_i$. I think it is a really interesting phenomenon, but how does one give a proof of this.

Also by experiment, I find that$\{(i,j):1\le i<j \le n+1,|S_i \cap S_j|\ge n/2\}$ is $\Omega(n)$, not only one pair.

This question can be generalized to the following one: Let $S=\{1,2,\cdots,n\}$, and $S_i \subseteq S$ be $m$ subsets of $S$, each of which contains exactly $k$ elements. Can the maximal size of $|S_i \cap S_j|(1\le i<j \le m)$ be bounded from below?

This question can be changed to a real version. Consider $x_i \in [0,1]^n$ be $m$ vectors, each of which has a fixed norm: $\| {x_i}\|_2=k$. Can the maximal inner product of $x_i \cdot x_j(1\le i<j \le m)$ be bounded from below?

Maybe the third and fourth question are hard, but if they can be solved, I think the results will be very useful. Also, the correctness of the first two questions have been checked for a few instances.

change R+ to [0,1]+; deleted 12 characters in body

Source Link

edited Nov 10, 2018 at 1:32

zbh2047

611
1
5
13

Let $S=\{1,2,\cdots,2n\}$, and $S_i \subseteq S(i=1,2,\cdots,n+1)$ be $n+1$ subsets, each of which contains half of the $2n$ elements, namely $|S_i|=n$. Consider the following expression: $$M=\max_{1\le i<j \le n+1} |S_i \cap S_j|$$

When $n$ is even, it seems that $M\ge n/2$ for any choice of $S_i$. I think it is a really interesting phenomenon, but how does one give a proof of this?
Also by experiment, I find that$\{(i,j):1\le i<j \le n+1,|S_i \cap S_j|\ge n/2\}$ is $\Omega(n)$, not only one pair.
This question can be generalized to the following one: Let $S=\{1,2,\cdots,n\}$, and $S_i \subseteq S$ be $m$ subsets of $S$, each of which contains exactly $k$ elements. Can the maximal size of $|S_i \cap S_j|(1\le i<j \le m)$ be bounded from below?
This question can be generalized furtherchanged to a real version. Consider $x_i \in \mathbb{R}_+^n$$x_i \in [0,1]^n$ be $m$ vectors, each of which has a fixed norm: $\| {x_i}\|_2=k$. Can the maximal inner product of $x_i \cdot x_j(1\le i<j \le m)$ be bounded from below?

Maybe the third and fourth question are hard, but if they can be solved, I think the results will be very useful. Also, the correctness of the first two questions have been checked for a few instances.

Let $S=\{1,2,\cdots,2n\}$, and $S_i \subseteq S(i=1,2,\cdots,n+1)$ be $n+1$ subsets, each of which contains half of the $2n$ elements, namely $|S_i|=n$. Consider the following expression: $$M=\max_{1\le i<j \le n+1} |S_i \cap S_j|$$

When $n$ is even, it seems that $M\ge n/2$ for any choice of $S_i$. I think it is a really interesting phenomenon, but how does one give a proof of this?
Also by experiment, I find that$\{(i,j):1\le i<j \le n+1,|S_i \cap S_j|\ge n/2\}$ is $\Omega(n)$, not only one pair.
This question can be generalized to the following one: Let $S=\{1,2,\cdots,n\}$, and $S_i \subseteq S$ be $m$ subsets of $S$, each of which contains exactly $k$ elements. Can the maximal size of $|S_i \cap S_j|(1\le i<j \le m)$ be bounded from below?
This question can be generalized further to a real version. Consider $x_i \in \mathbb{R}_+^n$ be $m$ vectors, each of which has a fixed norm: $\| {x_i}\|_2=k$. Can the maximal inner product of $x_i \cdot x_j(1\le i<j \le m)$ be bounded from below?

Maybe the third and fourth question are hard, but if they can be solved, I think the results will be very useful. Also, the correctness of the first two questions have been checked for a few instances.

Let $S=\{1,2,\cdots,2n\}$, and $S_i \subseteq S(i=1,2,\cdots,n+1)$ be $n+1$ subsets, each of which contains half of the $2n$ elements, namely $|S_i|=n$. Consider the following expression: $$M=\max_{1\le i<j \le n+1} |S_i \cap S_j|$$

When $n$ is even, it seems that $M\ge n/2$ for any choice of $S_i$. I think it is a really interesting phenomenon, but how does one give a proof of this?
Also by experiment, I find that$\{(i,j):1\le i<j \le n+1,|S_i \cap S_j|\ge n/2\}$ is $\Omega(n)$, not only one pair.
This question can be generalized to the following one: Let $S=\{1,2,\cdots,n\}$, and $S_i \subseteq S$ be $m$ subsets of $S$, each of which contains exactly $k$ elements. Can the maximal size of $|S_i \cap S_j|(1\le i<j \le m)$ be bounded from below?
This question can be changed to a real version. Consider $x_i \in [0,1]^n$ be $m$ vectors, each of which has a fixed norm: $\| {x_i}\|_2=k$. Can the maximal inner product of $x_i \cdot x_j(1\le i<j \le m)$ be bounded from below?

Maybe the third and fourth question are hard, but if they can be solved, I think the results will be very useful. Also, the correctness of the first two questions have been checked for a few instances.

Removed the deprecated (discrete-mathematics) tag - see the tag info: https://mathoverflow.net/tags/discrete-mathematics/info (if there are some other suitable tags, choose some of them instead)

Source Link