**Laci and Kati**

This is the first of a few posts which are spin-offs of the extremal combinatorics series, especially of part III. Here we talk about Lovasz’s geometric two families theorem.

## 1. Lovasz’s two families theorem

Here is a very beautiful generalization of the two families theorem due to Lovasz. (You can find it in his 1977 paper Flats in Matroids and Geometric Graphs.)

**Lovasz’s Theorem:** Let and be two families of linear spaces having the following properties:

1) for every , , and .

2) For every , ,

3) for every , .

Then .

This theorem is interesting even if all vector spaces are subspaces of an -dimensional space.

Recall Bollobas’s two families theorem:

**Theorem:** Let and be two families of sets having the following properties:

1) for every , , and .

2) For every , ,

3) for every , .

Then .

Why is Lovasz’s algebraic version a generalization of Bollobas’ two families theorem? Suppose that the union of all the s and s is the set . We can consider the standard basis in , and then associate to every subset of a vector space .

## 2. Over the Quaternions?

Before hinting how the proof of Lovasz’s theorem goes, let me mention an open problem: We do not know if the theorem extends to vector spaces over division rings; e.g. over the quaternions. The simplest open case is the case when and all vector spaces are subspaces of a 4-dimensional space. We can formulate this question as a question regarding non-Pappusian projective spaces (projective spaces over non-commutative division rings).

**Problem:** Is it possible to find 7 pairs of lines , , … , in a three dimensional projective space over the quaternions such that:

a) for every , .

b) for every , ?

in a three dimensional projective space over the quaternions such that:

a) for every , .

b) for every , .

## 3. Exterior algebras and a taste of the proof.

Let me describe the proof for the special case that all the spaces are subspaces of an -dimensional space and . If the vector spaces are (say) over the field of real numbers, we can reduce the general case to the special case as follows: if , then project the entire two families onto a linear hyperplane. If this hyperplane is generic the conditions will not be violated. If you are not working not over the reals but rather over a small field you can still enlarge the field and apply the same argument.

Now consider the exterior algebra over . This is a -dimensional graded vector space endowed with a product operation called “wedge”. So is the direct sum of the th exterior powers of denoted by , for . The dimension of is .

For every -dimensional subspace we associate a non-zero vector in . We can take to be the wedge of the elements in a basis of . (This determined the value of up to a scalar multiple.)

The crucial property we need is:

if and only if .

Now let and . The crucial property implies

if and only if .

Now we are ready for the proof of Lovasz’s two families theorem in the special case . All we need to show is that the exterior vectors that are associated to the subspaces are linearly independent. If and , take the exterior product of this sum with . The only term that survives is . This term is not zero, and this is a contradiction.

## 4. The skew two families theorem.

**Theorem:** Let and be two families of sets having the following properties:

1) for every , , and .

2) For every , ,

3) for every , .

Then .

How is this theorem proved? You just noticed that in the algebraic proof of Lovasz’s theorem, you can replace the condition ” for every , ” with the condition “for every , “.

If we just assume that if , and for every , the proof still works. The skew version of the two families theorem was proved by Peter Frankl (this way) and by myself (I gave a somewhat different proof also using an exterior algebra) around 1980.

## 5. Shellability again

We said that a -dimensional pure polyhedral complex is shellable if its maximal faces (facets) can be ordered by a sequence such that for every , , the intersection of with the union of is homeomorphic to a -dimensional ball or sphere. This condition implies that the entire complex is homeomorphic to a sphere or a ball. (We mentioned shellability here and here.)

For simplicial complexes, shellability is especially simple and becomes a purely combinatorial condition. The intersection of with the previous facets should be a (nonempty) union of some (or all) of its own facets. In a shelling sequence of facets, adding to the simplicial complex generated by has a very simple form. We add to a subset and all sets that contain which are contained in . If we say that adding is a shelling step of type .

For a shellable simplicial complex and a shelling order let be the number of shelling steps of type . (It turns out that does not depend on the shelling order.)

**Theorem (Stanley)**:

**Proof:** Write and . We have altogether pairs of sets. Since we have that . Since for we conclude that for . (This proof is by Noga Alon and me and it gives simple proofs to the “upper bound theorem” for convex polytopes (we will come back to it) and to the Katchalski-Perles conjecture (that we already discussed).)

## 6. Rediscoveries and overlooks.

Bollobas’s Two Families theorem was stated originally in a different way. The above formulation was offered (later) as a conjecture by A. Ehrenfeucht and J. Mycielski and it was proved by Katona who gave the beautiful proof that we brought in part 3 of the extremal combinatorics posts. In this story, several simple combinatorial connections were overlooked and, in a sense, this was good as it led to different proofs, new proof techniques, and new points of view. The skew version of the two families theorem is equivalent to a conjecture of Bollobas on “weakly saturated graphs and hypergraphs”. The statement about shellability is also equivalent to the skew version of the two families theorem, and it has a different (earlier) algebraic proof by Kind and Kleinschmidt. Kind and Kleinschmidt gave a simple proof for the case of shellable complexes to Stanley’s 1975 theorem which applies for a larger class of simplicial complexes called “Cohen-Macaulay complexes”.

Any relation to Sergey Yekhanin’s construction of 3-query locally decodable codes? A part of his constructions looks somewhat similar.

Thank you for entertaining us with good math ! Still, I’m puzzled by your (re-)formulation of the quaternion version of the k=l=2 two-families subspace problem. Why aren’t p_i also *lines* (seven of them) instead of *points* in three-dimensional quaternionic projective space ?

Dear Bruno,

you are absolutely right. thanks you!

Pingback: Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more