Lovasz’s Two Families Theorem

Posted on December 25, 2008 by Gil Kalai

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”.

7 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.

Reply
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 ?

Reply
Gil Kalai says:

December 31, 2008 at 10:31 pm

Dear Bruno,
you are absolutely right. thanks you!

Reply
Pingback: Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more
Pingback: My Mathematical Dialogue with Jürgen Eckhoff | Combinatorics and more
Pingback: Touching Simplices and Polytopes: Perles’ argument | Combinatorics and more
perringu says:

February 11, 2018 at 9:28 am

here we see sure some as say prof dr mircea orasanu and prof horia orasanu as followed
KRONECKER CAPELLI THEOREM AND APPLICATIONS
Author Mircea Orasanu
ABSTRACT
In this lecture we recall the definitions of autonomous and non autonomous Dynamical Systems as well as their different concepts of attractors. After that we introduce the different notions of robustness of attractors under perturbation (Upper semicontinuity, Lower semicontinuity, Topological structural stability and Structural stability) and give conditions on the dynamical systems so that robustness is attained. We show that enforcing the appropriately defined virtual holonomic constraints for the configuration variables implies that the robot converges to and follows a desired geometric path. Numerical simulations and experimental rMethods
1 INTRODUCTION
This is definitely more of a mess that we’ve seen to this point when it comes to separating variables. In this case simply dividing by the product solution, while still necessary, will not be sufficient to separate the variables. We are also going to have to multiply by to completely separate variables. So, doing all that, moving each term to one side of the equal sign and introduction a separation constant gives,Joint angles tracking the reference joint angles in simulations in the presence of measurement noise. The joints of the robot track the sinusoidal motions in the presence of measurement noise (above). The joint tracking errors converge exponentially …Aceasta ecuatie spune un lucru foarte interesant, anume ca orbita este simetrica fata de punctele de intoarcere. Imaginati-va ca particula a trasat portiunea de orbita dintre cele doua puncte, si fixati un plan perpendiular pe planul orbitei ce contine punctele de intoarcere. Atunci, daca orbita este simetrica, pentru a obtine portiunea ce inca nu a fost parcursa ar fi suficient sa “reflectez” orbita fata de acel plan, ca intr-o oglinda. Daca alegem sistemul de coordonate in asa fel incat punctul de intoarcere sa corespunda chiar unghiului , atunci operatia de reflexie se poate efectua prin substitutia , ce ar corespunde unei rotatii in sens invers fata de acel punct, ori ecuatia pe care am gasit-o mai sus este clar invarianta la aceasta transformare, deoarece variabila apare numai in derivata de ordinul doi, si schimbarea dubla de semn nu schimba nimic. De fapt, aceasta reflexie poate fi facuta in pasi si mai marunti. Oricat de mica ar fi distanta parcursa dincolo de un punct de intoarcere, pot intotdeauna s-o reflectez in sens opus.
THESIS

Reply

	5 nuances d’Au… on Aubrey de Grey: The chromatic…
	Gil Kalai on Coloring Problems for Arrangem…
	Stan Wagon on Coloring Problems for Arrangem…
	Stan Wagon on Coloring Problems for Arrangem…
	Gil Kalai on Coloring Problems for Arrangem…
	Jineon Baek on Test Your Intuition (34): Tili…
	Stan Wagon on Coloring Problems for Arrangem…
	Gil Kalai on Test Your Intuition (34): Tili…
	Sándor Kolumbán on Test Your Intuition (34): Tili…
	Coloring Problems fo… on Around Borsuk’s Conjecture 3:…
	Coloring Problems fo… on Serge Vlăduţ : Lattices with e…
	Coloring Problems fo… on Proof By Lice!