The origins of the linear algebra method in combinatorics

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 [1]).

How is this relevant for the problem stated above?

Well, a balanced incomplete block design (BIBD), which nowadays is known as a 2(v,k,\lambda) design is simply a collection of k-subsets, called blocks, of v points such that every pair of distinct points lie in exactly \lambda blocks. By simple counting it can be shown that in a BIBD there exist constants b and r where b is the total number of blocks and r the total number of blocks through a fixed point such that bk = rv and (v-1)\lambda = (k-1)r. Now, if you take n = b 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 \lambda elements. And the Fisher’s inequality states that the number of subsets v is at most the number of elements in the set, b.

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 [2]. 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 [3].

At around the same time Paul Erdős solved the following question in a joint paper with N. G. De Bruijn [4]: 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 \lambda > 1. The general problem, posed in the beginning of this post, was ultimately solved by Majumdar (1953 [5]) and Isbell (1959 [6]) independently. Here’s a short proof of this result due to Babai [3].

Theorem. Let S_1, S_2, \ldots, S_m be distinct subsets of [n] = \{1, 2, \ldots, n\} and \lambda a fixed integer satisfying 1 \leq \lambda < n.  If  for every i \neq j, |S_i \cap S_j| = \lambda then m \leq n.

Proof. First we take care of some boundary cases. Say there exists an i such that |S_i| < \lambda, then clearly m = 1 < n. Now without loss of generality, say |S_1| = \lambda  then S_i \cap S_j = S_1 for all distinct i, j and hence S_i \setminus S_1, i > 0 are disjoint sets. Therefore, m - 1 + \lambda \leq n.
So, now we can assume that |S_i| > \lambda for all i. Define k_i = |S_i| - \lambda. Then all k_i‘s are positive. Let M be the incidence matrix, i.e., n \times m matrix with M_{ij} = 1 if i \in S_j and 0 otherwise. Consider the elements of M to be coming from the field \mathbb{R} of real numbers. Let A \in \mathcal{M}_m(\mathbb{R}) be the intersection matrix with A_{ij} = |S_i \cap S_j|. Then the intersection conditions can be stated as A = M^TM = \lambda J + D, where J is the all-one matrix  of order m \times m and  D the diagonal matrix [k_1 - \lambda, \ldots, k_m - \lambda].
From basic linear algebra it follows that rank(A) = rank(M^TM) \leq rank(M) \leq n. We can check that the matrix \lambda J is positive semidefinite and the matrix \lambda D is positive definite. Therefore, their sum must be positive definite. This proves that A has full rank and hence m \leq n.

To show that the matrix A 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 [2]. Alternately one can directly show that the m incidence vectors corresponding to the subsets are linearly independent [8].

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/

[1] http://onlinelibrary.wiley.com/doi/10.1111/j.1469-1809.1940.tb02237.x/abstract
[2] http://projecteuclid.org/euclid.aoms/1177729958
[3] Linear Algebra Methods in Combinatorics by Laszlo Babai and Peter Frankl.
[4] De Bruijn–Erdős theorem
[5] http://projecteuclid.org/euclid.aoms/1177728978
[6] http://www.jstor.org/stable/2033580?seq=1
[7] http://www.sciencedirect.com/science/article/pii/0012365X87901063
[8] http://math.mit.edu/~fox/MAT307-lecture15.pdf
[9] http://www.math.uwaterloo.ca/~cgodsil/pdfs/tools.pdf
[
10] http://mathoverflow.net/questions/230865/list-of-counting-proofs-instead-of-linear-algebra-method-in-combinatorics

Advertisements

About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics and tagged , . Bookmark the permalink.

One Response to The origins of the linear algebra method in combinatorics

  1. “The affiliation listed on Bose’s paper is the Institute of Statistics, University of North Carolina. Before taking up residence in the U.S. in 1948, Bose worked at the Indian Statistical Institute in Calcutta. One of the most influential combinatorialists of the decades to come, Bose was forced to become a statistician by the lack of employment chances in mathematics in his native country. A pure mathematician hardly in disguise, he reared generations of combinatorialists. His students at Chapel Hill included D. K. Ray-Chaudhuri, a name that together with his student R. M. Wilson (so, may be a grandson of Bose?) will appear several dozen times on these pages for their far reaching extension of Bose’s method.” – pg. 77, Linear Algebra Methods in Combinatorics by Babai and Frankl.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s