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:

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_is and B_is 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 kth 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
This entry was posted in Combinatorics, Convexity, Open problems and tagged , , . Bookmark the permalink.

5 Responses to Lovasz’s Two Families Theorem

  1. elad says:

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

  2. bruno says:

    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 ?

  3. Gil Kalai says:

    Dear Bruno,
    you are absolutely right. thanks you!

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

  5. Pingback: My Mathematical Dialogue with Jürgen Eckhoff | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s