8 Extremal Set theory 8.2 Intersecting and non-intersecting sets 8.4 Exercises

8.3 Fisher’s inequality

Let us prove an inequality for intersecting sets satisfying a strong constraint on intersection. This is known as Fisher’s inequality, an important result in design theory (see Chapter 9) motivated by statistics. More important for us is the proof of a generalized version by R. C. Bose in 1949 using the so-called ‘linear algebra method’ . This is seemingly the first application of linear algebra method to a combinatorial problem. We state a general version due to K. N. Mazumdar with further proof simplifications by Babai and Frankl [Babai 2020].

Theorem 8.12.

Let $A_{i},1\leq i\leq m$ be distinct subsets of $[n]$ such that $|A_{i}\cap A_{j}|=k$ for all $i\neq j$ and for $1\leq k\leq n$ . Then $m\leq n$ .

Note that the exactness of the intersection puts a stronger constraint and hence the bound is much smaller than in Erdős-Ko-Rado theorem or its variants. An elementary usage of linear algebra method is as follows: Identify the elements to count with linearly independent elements of a ’low-dimensional’ vector space and thus the number of elements is at most the dimension.

Proof.

Define the incidence vector for $A$ , $x_{A}\in\{0,1\}^{n}$ as $x_{A}(i)=1[i\in A]$ . Abbreviate the incidence vectors to $A_{1},\ldots,A_{m}$ as $x_{1},\ldots,x_{m}$ . Note that dimension of $\{0,1\}^{n}$ is $n$ and hence we need to only show that $x_{1},\ldots,x_{m}$ are linearly independent.

Observe that $x_{i}.x_{j}=|A_{i}\cap A_{j}|$ and so $x_{i}.x_{j}=k$ if $i\neq j$ and $x_{i}.x_{i}=|A_{i}|$ . Further $|A_{i}|\geq k$ for all $i$ and at most one $i$ (say $i=1$ WLOG) can satisfy equality as two distinct $k$ - sets cannot have intersection cardinality $k$ . Suppose $\sum_{i}a_{i}x_{i}=0$ for some real numbers $a_{i}$ . Then using the above facts and linearity,

	$\displaystyle 0$	$\displaystyle=(\sum_{i}a_{i}x_{i}).(\sum_{i}a_{i}x_{i})=\sum_{i}a_{i}^{2}x_{i}% .x_{i}+\sum_{i\neq j}a_{i}a_{j}x_{i}.x_{j}$
		$\displaystyle=\sum_{i}a_{i}^{2}(\|A_{i}\|-k)+k(\sum_{i}a_{i})^{2}$

If $A_{1}$ is not a $k$ -set, the above equality implies that $\sum_{i}a_{i}^{2}=0$ and so $x_{i}$ ’s are linearly independent. If $A_{1}$ is a $k$ -set, then we have that $\sum_{i=2}^{m}a_{i}^{2}=0$ and $\sum_{i}a_{i}=0$ which together again imply that $a_{i}$ ’s are all $0$ . Thus $x_{i}$ ’s are linearly independent in this case as well. ∎