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

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

• Could you explain how you get the equality? Sep 25, 2023 at 14:07
• @FabiusWiesner Build a bipartite graph with the n subsets on left, and $n$ choose 2 subsets of size 2 on the right. Connect $A_i$ to $\{a,b\}$ if it is the unique subset containing it. There are $n$ choose 2 edges as each 2-subset belongs in a unique set. Alternatively, each set $A_i$ contributes $| A_i |$ choose 2 edges for each of its 2-subsets. Sep 25, 2023 at 14:15

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

• Wow, thank you. Do you mind sharing the intuition of how you thought of $p_i \leq f_i$. In retrospect, it’s clear now, but I don’t get how to think of that. Sep 26, 2023 at 1:18
• @AspiringMat: I added a picture, it is helpful to think in terms of points and lines, since we are used to them. There is a result that even if the number of lines is $m$, we must have $m\ge n$, and I think it could be proved in a similar way. One can think about the projective (your case) or affine ( $m > n$) over a finite field. A great question, all your questions are in fact ! Sep 26, 2023 at 1:45
• Very nice, but I do think the part about Hall's Marriage Thm should be clarified. Let $G$ be the bipartite graph where point $p_i$ is adjacent to $L_j$ iff $p_i$ is not on $L_j$. Then for any subset $S$ of points, the line $L_j$ is not in $N_G(S)$ only if every point in $S$ is in $L$. Now, if $|S|=1$, then letting $S =\{p_i\}$ there must be at least one line not containing $p_i$ lest all the lines intersect. For $|S| \ge 2$ observe that there can be at most one line containing every point in $S$, by the assumption that every pair of points is contained by at most one line. ...
– Mike
Sep 27, 2023 at 19:03
• Also, it should be observed by the reader that $\sum {{f_i} \choose 2}$ indeed is the number of pairs of lines that intersect.
– Mike
Sep 27, 2023 at 19:08
• It should be noted that the only place we use the fact that every line has at least $2$ points, is to establish that no line contains all the points, so we can use Hall's Thm. Finally, on that note, for the more general $m \le n$, care needs to be taken in the sense that $m=1$ and one line containing all the points, works. +1
– Mike
Sep 27, 2023 at 19:42