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:

Theorem: Let $A_1,A_2,\dots A_t$ and $B_1,B_2,\dots , B_t$ be two families of sets having the following properties:

1) for every $i$ , $|A_i| \le k$ , and $|B_i| \le \ell$ .

2) For every $i$ , $A_i \cap B_i = \emptyset$ ,

3) for every $i \ne j$ , $A_i \cap B_j \ne \emptyset$ .

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

Why is Lovasz’s algebraic version a generalization of Bollobas’ two families theorem? Suppose that the union of all the $A_i$ s and $B_i$ s is the set $X=\{1,2,\dots,n\}$ . We can consider the standard basis $e_1,e_2\dots,e_n$ in $R^n$ , and then associate to every subset $S$ of $X$ a vector space $span \{e_i:i \in S\}$ .

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 $k=\ell=2$ 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 $\ell_1,\ell'_1$ , $\ell_2,\ell_2'$ , … , $\ell_7, \ell'_7$ in a three dimensional projective space over the quaternions such that:

a) for every $i=1,2,\dots,7$ , $\ell_i \cap \ell'_i = \emptyset$ .

b) for every $i \ne j$ , $\ell_i \cap \ell'_j \ne \emptyset$ ?

Update (April 2014): Benjy Weiss brought to my attention a paper by S.A. Amitsur Rational identities and applications to algebra and geometry. In the paper it is shown that, for Desarguian geometries, intersection theorems are equivalent to rational identities in the coordinate ring and that any nontrivial intersection theorem, together with the order axioms, implies Pappus’ theorem. This may be relevant for showing that (at least in some cases) if you cannot find m pairs $m>6$ then $m=\infty$ .

Update: Here is a related question I asked over MathOverflow.

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 $n$ -dimensional space $U$ and $n = k + \ell$ . 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 $n>k+\ell$ , 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 $\bigwedge U$ over $U$ . This is a $2^n$ -dimensional graded vector space endowed with a product operation $\wedge$ called “wedge”. So $\bigwedge U$ is the direct sum of the $k$ th exterior powers of $U$ denoted by $\bigwedge^k(V)$ , for $k=0,1,2,\dots, n$ . The dimension of $\bigwedge ^k(V)$ is ${{n} \choose {k}}$ .

For every $k$ -dimensional subspace $V \subset W$ we associate a non-zero vector $\psi (V)$ in $\bigwedge^k(V)$ . We can take $\psi (v)$ to be the wedge of the elements in a basis of $V$ . (This determined the value of $\psi (V)$ up to a scalar multiple.)

The crucial property we need is:

$\psi(V) \wedge \psi (W) =0$ if and only if $V \cap W \ne \{0\}$ .

Now let $v_i = \psi (V_i)$ and $w_i = \psi (W_i)$ . The crucial property implies

$v_i \wedge w_j=0$ if and only if $i \ne j$ .

Now we are ready for the proof of Lovasz’s two families theorem in the special case $n = k + \ell$ . All we need to show is that the exterior vectors $v_i$ that are associated to the $t$ subspaces $V_i$ are linearly independent. If $\sum \lambda_iv_i = 0$ and $\lambda_k \ne 0$ , take the exterior product of this sum with $w_k$ . The only term that survives is $\lambda_k v_k \wedge w_k$ . This term is not zero, and this is a contradiction.

4. The skew two families theorem.

Theorem: Let $A_1,A_2,\dots A_t$ and $B_1,B_2,\dots , B_t$ be two families of sets having the following properties:

1) for every $i$ , $|A_i| \le k$ , and $|B_i| \le \ell$ .

2) For every $i$ , $A_i \cap B_i = \emptyset$ ,

3) for every $i<j$ , $A_i \cap B_j \ne \emptyset$ .

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

How is this theorem proved? You just noticed that in the algebraic proof of Lovasz’s theorem, you can replace the condition ” for every $i \ne j$ , $V_i \cap W_j \ne \{0\}$ ” with the condition “for every $i<j$ , $V_i \cap W_j \ne \{0\}$ “.

If we just assume that $v_i \wedge w_j=0$ if $i<j$ , and $v_i \wedge w_i \ne 0$ for every $i$ , 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 $d$ -dimensional pure polyhedral complex is shellable if its maximal faces (facets) can be ordered by a sequence $F_1,F_t,\dots ,F_t$ such that for every $k$ , $1 < k \le t$ , the intersection of $F_k$ with the union of $F_1,\dots,F_{k-1}$ is homeomorphic to a $(d-1)$ -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 $F_k$ with the previous facets should be a (nonempty) union of some (or all) of its own facets. In a shelling sequence of facets, adding $F_k$ to the simplicial complex $K_k$ generated by $\{F_1,F_2,\dots,F_{k-1} \}$ has a very simple form. We add to $K_k$ a subset $S_k \subset F_k$ and all sets that contain $S_k$ which are contained in $F_k$ . If $|S_k| =m$ we say that adding $F_k$ is a shelling step of type $m$ .

For a shellable simplicial complex $K$ and a shelling order $F_1,F_2,\dots,F_t$ let $h_m(K)$ be the number of shelling steps of type $m$ . (It turns out that $h_m(K)$ does not depend on the shelling order.)

Theorem (Stanley): $h_m(K) \le {{n-d+m} \choose {m}}.$

Proof: Write $A_i = \{1,2,\dots, n\} \backslash F_i$ and $B_i = S_i$ . We have altogether $h_m$ pairs of sets. Since $S_i \subset F_i$ we have that $S_i \cap A_i =\emptyset$ . Since $S_i \not \subset F_j$ for $j<i$ we conclude that $B_i \cap A_j \ne \emptyset$ for $j<i$ . (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”.

About these ads

5 Responses to Lovasz’s Two Families Theorem

elad says:

December 25, 2008 at 4:01 pm

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

bruno says:

December 31, 2008 at 8:59 pm

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 ?

Gil Kalai says:

December 31, 2008 at 10:31 pm

Dear Bruno,
you are absolutely right. thanks you!

Pingback: Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more
Pingback: My Mathematical Dialogue with Jürgen Eckhoff | Combinatorics and more

	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Jon Awbrey on Influence, Threshold, and…