Proving $n$ subsets $A_1, ..., A_n$ of size $\geq 2$ must pairwise intersect.

Question

Let $A_1, ..., A_n \subseteq [n]$ be $n$ subsets of $[n]$ with $|A_i|\geq 2$. Suppose further that for every $B \subseteq [n], |B|=2$, that there exists a unique $i$ with $B\subseteq A_i$. Prove that $A_i \cap A_j \neq \emptyset $ for all $i,j$.

Attempt: I can get the equality:

$$\sum_{i=1}^n {|A_i| \choose 2} = {n \choose 2}$$

Using a double counting argument, but not sure how to use that to prove $A_i, A_j$ intersect for all $i,j$.

Answer 1

Say $\mathcal{P}$ is our base set, $\mathcal{P}=n$, and we have a family of subsets $\mathcal{L}=\{L_1, \ldots, L_n\}$, $|L_j|\ge 2$ for all $1\le j\le n$. Also assume that for every $p\ne p' \in \mathcal{P}$ there exists a unique $L \in \mathcal{L}$ such that $L\ni p, p'$.

We'll call the elements of $\mathcal{P}$ points, and the elements of $\mathcal{L}$ lines.

Some notations:

1. for all $j$, let $\ell_j$ be the cardinality of $L_j$.

2. for every $i$, let $f_i = \# \{ j \ | L_j \ni p_i \}$ ( the cardinality of the fan of $p_i$).

Now, since every pair of points is contained in exactly one line, we have ( formula indicated in the posting)

$$\binom{n}{2} = \sum_{j=1}^n \binom{\ell_j}{2}$$

Let's also note that a priori every two lines intersect in at most one point. Therefore, we have

$$\binom{n}{2} \ge \sum_{i=1}^n \binom{f_i}{2}$$

Now note that if the point $p_i$ (red) is not contained in the line $L_j$ ( green), then $f_i \ge \ell_j$.

Indeed: there are at least as many lines through the red point as there are points on the green line

Now, let us show that there exists a bijection $i \mapsto j = j(i)$ such that the line $L_j$ does not contain $p_i$. This can be done using Hall's marriage theorem ( some details to fill in). Under this correspondence $i\mapsto j$, we'll have $f_i \ge \ell_j$ ( from the above).

Therefore we have

$$\sum_{i=1}^n \binom{f_i}{2} \ge \sum_{j=1}^n \binom{\ell_j}{2}$$

Now, we have two inequalities, so

$$\sum_{i=1}^{n}\binom{f_i}{2} = \binom{n}{2}$$ and this implies that every two lines intersect in a point.

$\bf{Added:}$ Let's assume that we have $m$ lines, instead of $n$, and also $1<m\le n$. Now with Hall's lemma, we can get an injective map from lines $\mathcal{L}$ to points $\mathcal{P}$, $L_j \mapsto p_i$, such that $p_i \not \in L_j$ ( we are using $m \le n$). We get

$$\binom{n}{2} = \sum_{j=1}^m \binom{\ell_j}{2} \le \sum_{i=1}^n \binom{f_i}{2} \le \binom{m}{2}$$

We conclude that we must have $m=n$, And every two lines intersect.

So, we proved our statement, and the fact that in general $m\ge n$.

$\bf{Added:}$ @Mike corrected second Added, we also need $1< m$ ( or else all the points will be on a line), with the feedback a rewrite seems needed.

The inequality $m\ge n$ is called the Fisher inequality and is valid more generally for designs. Our original question is about finite projective planes, an active area with big unsolved problems ( so I was told).