9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Could you explain how you get the equality? $\endgroup$ Sep 25, 2023 at 14:07
  • 2
    $\begingroup$ @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. $\endgroup$ Sep 25, 2023 at 14:15

1 Answer 1

7
$\begingroup$

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$. lines through a point

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

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 26, 2023 at 1:18
  • 2
    $\begingroup$ @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 ! $\endgroup$
    – orangeskid
    Sep 26, 2023 at 1:45
  • 1
    $\begingroup$ 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. ... $\endgroup$
    – Mike
    Sep 27, 2023 at 19:03
  • 1
    $\begingroup$ Also, it should be observed by the reader that $\sum {{f_i} \choose 2}$ indeed is the number of pairs of lines that intersect. $\endgroup$
    – Mike
    Sep 27, 2023 at 19:08
  • 1
    $\begingroup$ 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 $\endgroup$
    – Mike
    Sep 27, 2023 at 19:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .