Sometimes you have to make things more complicated in order to make them simpler.
My old friend Aiden Bruen visited this week, and told me about a paper by him and his son Trevor which has just appeared in the Mathematical Intelligencer on the subject of bases.
Given a spanning set of n vectors in an r-dimensional vector space, we know that the set contains at least one basis. One of the main questions they tackled was: can one put a sensible lower bound on the number of bases contained in the set? Two big theorems in the paper assert that, if all the vectors are non-zero, there are at least n−r+1 bases, the extremal case being when n−r+1 of the vectors lie in a 1-dimensional subspace; and, if no vector in the set is a scalar multiple of any other, then the number is at least (n−r+2 choose 2), the extremal case being when n−r+2 of the vectors lie in a 2-dimensional subspace. (The hypothesis in this case is that the vectors represent distinct points in the projective space; so, in the case when r = 3, for example, we are maximising the number of triangles formed by n points in the projective plane.)
The proofs of the two theorems were moderately complicated and completely independent. But there is an obvious generalisation: introduce a new parameter s, and require that any s of the vectors are linearly independent. The Bruens’ cases were s = 1 and s = 2.
Introducing the parameter s greatly simplifies the argument, since it is available for induction along with the other two parameters. The general statement, whose proof takes only a page, is that a spanning set of n vectors in an r-dimensional vector space, any s of which are linearly independent, contain at least (n−r+s choose s) bases; equality implies that n−r+s of the vectors are contained in an s-dimensional subspace.
The other simplification is more conceptual than technical. The result holds for arbitrary matrods, not just for representable ones as suggested here. It states that an n-element matroid with rank r, in which any s-element set is independent, has at least (n−r+s choose s) bases; equality holds if and only if the matroid is the direct sum of a uniform matroid Un−r+s,s and a free matroid on r−s elements.
The advantage of proving it in the case of matroids is that the main tool, deletion and contraction, is readily to hand; contraction in a vector space involves taking a quotient space which is less easy to think about.
The other advantage of the matroid formulation is that in the vector space case we have to wonder about whether, for example, there exist m points in an s-dimensional space, any s of which form a basis. This important question, closely related to the existence of maximum-distance-separable codes and a problem of Segre (with which Aiden’s is one of the names most closely associated), is from our point of view quite separate from the main theorem.
The matroid formulation suggests other questions. The bound holds for any matroid; but, for example, it cannot be met for graphic matroids except in very special cases. (From one point of view, this is because graphic matroids are representable over any field whereas sets of vectors of the type just discussed only exist over sufficiently large fields.) However, the question has a natural translation into graph-theoretic terms. What is the smallest number of spanning trees in a connected graph with t vertices and n edges (with t = r+1 in terms of the parameters given above) whose girth is greater than s?