# Lovasz’s Two Families Theorem

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