Lovasz’s Two Families Theorem

Laci and Kati

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 V_1,V_2,\dots V_t and W_1, W_2, \dots , W_t be two families of linear spaces having the following properties:

1) for every i, \dim V_i \le k, and \dim W_i \le \ell.

2) For every i, V_i \cap W_i = \{0\},

3) for every i \ne j, V_i \cap W_j \ne \{0\}.

Then t \le {{k+\ell} \choose {k}}.

This theorem is interesting even if all vector spaces are subspaces of an (k+\ell)-dimensional space.

Recall Bollobas’s two families theorem: Continue reading