The maximal size of intersection of two sets

Question

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

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

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

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

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

Answer 1

Here is an answer to the first point and shows how you can also do the third point.

Let $\displaystyle \bigcup_{i=1}^{n+1} S_i=\{b_{1},b_{2},\ldots, b_{m}\}$. We consider the following table with rows indexed by the sets $S_1,S_2,\ldots, S_{n+1}$ and columns indexed by the elements $b_1,b_2,\ldots, b_m$. We put a $1$ in the cell $(i,j)$ with $1\leq i\leq k$ and $1\leq j\leq m$ if $b_j$ is an element of the set $S_i$. Let $x_i$ the number of $1$'s in the column $i$, or equivalently it is the number of sets in which the element $b_i$ appears with $1\leq i\leq m$.

Now we have that $S=\displaystyle \sum_{i=1}^{m} x_i$ is equal to the sum of the numbers in the whole table, and doing the sum by rows we obtain that $\displaystyle \sum_{i=1}^{m} x_i=\sum_{i=1}^{n+1} |S_i|=n(n+1)$.

Let us look further at $\displaystyle \sum_{1\leq i<j\leq n+1} |S_i\cap S_j|$. This is equal to the number of pairs of $1$'s who are in the same column. But this is equivalent in our notation to the fact $\displaystyle \sum_{1\leq i<j\leq n+1} |S_i\cap S_j|=\sum_{i=1}^{m} \dbinom{x_i}{2}$.

Now just use the convexity of the function $\binom{x}{2}$ to get that $$\sum_{i=1}^{m} \dbinom{x_i}{2}\geq m \dbinom{\frac{n(n+1)}{m}}{2}=\cfrac{(n(n+1)-m)n(n+1)}{2m}$$.

Since there are $\dbinom{n+1}{2}$ intersection the maximum size of the intersection is at least $\cfrac{n(n+1)-m}{m}$. Finally $m\leq 2n$ and you get the desired size almost namely $\cfrac{n-1}{2}$.

Answer 2

An answer to your fourth question:

The Welch lower bound (applicable to arbitrary complex vectors, as opposed to the Sidelnikov lower bounds applicable only to vectors with entries in the complex roots of unity, which are somewhat tighter) states that for any integer $f\geq 1,$ we have

$$ \max_{1\leq i<j\leq m} |\langle x_i,x_j\rangle|^2 \geq \frac{1}{m(m-1)} \left[\frac{\sum_{i=1}^m \langle a_i,a_i\rangle^f }{\binom{n+f-1}{f}}-\left( \sum_{i=1}^m \langle a_i,a_i \rangle^{2f} \right)\right]. $$

This can be optimized over $f$ and generally gives the best lower bound (for roughly equal norm vectors) when $m\approx n^{f}.$ For your specific case $$ \max_{1\leq i<j\leq m} |\langle x_i,x_j\rangle|^2 \geq \frac{1}{m(m-1)} \left[\frac{m k^f }{\binom{n+f-1}{f}}-\left(m k^{2f} \right)\right]. $$