How many subsets of a set of cardinality n can pairwise share the same number of elements?
In 1940’s statistician R. A. Fisher, while working on the “design of experiments”, made an interesting discovery that in a balanced incomplete block design the number of blocks is never less than the number of points (see page 54 in ).
How is this relevant for the problem stated above?
Well, a balanced incomplete block design (BIBD), which nowadays is known as a – design is simply a collection of -subsets, called blocks, of points such that every pair of distinct points lie in exactly blocks. By simple counting it can be shown that in a BIBD there exist constants and where is the total number of blocks and the total number of blocks through a fixed point such that and . Now, if you take and consider the set of blocks through a fixed point as subsets then the condition of a BIBD translates into two such distinct subsets sharing elements. And the Fisher’s inequality states that the number of subsets is at most the number of elements in the set, .
R. C. Bose observed a few years later that the Fisher’s inequality holds for a more general case than originally proved by Fisher. He proved that , if every pair of sets in a uniform family has equal intersection size, then the number of sets does not exceed the number of points . Though the significance of this 2-page paper of Bose goes far beyond proving the Fisher’s inequality. The method he used is what is now known as the ”linear algebra bound” which has since been used to prove numerous important results .
At around the same time Paul Erdős solved the following question in a joint paper with N. G. De Bruijn : Maximally how many subsets of an n-set can have pairwise precisely one common element?
While the result of Bose assumes that each subset has the same size (uniform family) the de Bruijn-Erdős inequality makes no such assumption. But their method couldn’t be generalized for . The general problem, posed in the beginning of this post, was ultimately solved by Majumdar (1953 ) and Isbell (1959 ) independently. Here’s a short proof of this result due to Babai .
Theorem. Let , , , be distinct subsets of and a fixed integer satisfying . If for every , then .
Proof. First we take care of some boundary cases. Say there exists an such that , then clearly . Now without loss of generality, say then for all distinct and hence , are disjoint sets. Therefore, .
So, now we can assume that for all . Define . Then all ‘s are positive. Let be the incidence matrix, i.e., matrix with if and otherwise. Consider the elements of to be coming from the field of real numbers. Let be the intersection matrix with . Then the intersection conditions can be stated as , where is the all-one matrix of order and the diagonal matrix .
From basic linear algebra it follows that . We can check that the matrix is positive semidefinite and the matrix is positive definite. Therefore, their sum must be positive definite. This proves that has full rank and hence .
To show that the matrix has full rank we could have also computed its determinant (product of eigenvalues in this case as the matrix is symmetric). This is what Bose did in . Alternately one can directly show that the incidence vectors corresponding to the subsets are linearly independent .
This result shows the power of using linear algebra in combinatorics. It has been used extensively to solve several interesting combinatorial and geometrical problems, many of which could not be proved in any other way. Here is a nice mathoverflow question that discusses the use of linear algebra in combinatorics: http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics, and here is a blog post by Gowers discussing this kind of dimension argument in combinatorics: https://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/
 Linear Algebra Methods in Combinatorics by Laszlo Babai and Peter Frankl.
 De Bruijn–Erdős theorem