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 and
be two families of linear spaces having the following properties:
1) for every ,
, and
.
2) For every ,
,
3) for every ,
.
Then .
This theorem is interesting even if all vector spaces are subspaces of an -dimensional space.
Recall Bollobas’s two families theorem:
Theorem: Let and
be two families of sets having the following properties:
1) for every ,
, and
.
2) For every ,
,
3) for every ,
.
Then .
Why is Lovasz’s algebraic version a generalization of Bollobas’ two families theorem? Suppose that the union of all the s and
s is the set
. We can consider the standard basis
in
, and then associate to every subset
of
a vector space
.
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 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 ,
, … ,
in a three dimensional projective space over the quaternions such that:
a) for every ,
.
b) for every ,
?
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 then
.
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 -dimensional space
and
. 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
, 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 over
. This is a
-dimensional graded vector space endowed with a product operation
called “wedge”. So
is the direct sum of the
th exterior powers of
denoted by
, for
. The dimension of
is
.
For every -dimensional subspace
we associate a non-zero vector
in
. We can take
to be the wedge of the elements in a basis of
. (This determined the value of
up to a scalar multiple.)
The crucial property we need is:
if and only if
.
Now let and
. The crucial property implies
if and only if
.
Now we are ready for the proof of Lovasz’s two families theorem in the special case . All we need to show is that the exterior vectors
that are associated to the
subspaces
are linearly independent. If
and
, take the exterior product of this sum with
. The only term that survives is
. This term is not zero, and this is a contradiction.
4. The skew two families theorem.
Theorem: Let and
be two families of sets having the following properties:
1) for every ,
, and
.
2) For every ,
,
3) for every ,
.
Then .
How is this theorem proved? You just noticed that in the algebraic proof of Lovasz’s theorem, you can replace the condition ” for every ,
” with the condition “for every
,
“.
If we just assume that if
, and
for every
, 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 -dimensional pure polyhedral complex is shellable if its maximal faces (facets) can be ordered by a sequence
such that for every
,
, the intersection of
with the union of
is homeomorphic to a
-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 with the previous facets should be a (nonempty) union of some (or all) of its own facets. In a shelling sequence of facets, adding
to the simplicial complex
generated by
has a very simple form. We add to
a subset
and all sets that contain
which are contained in
. If
we say that adding
is a shelling step of type
.
For a shellable simplicial complex and a shelling order
let
be the number of shelling steps of type
. (It turns out that
does not depend on the shelling order.)
Theorem (Stanley):
Proof: Write and
. We have altogether
pairs of sets. Since
we have that
. Since
for
we conclude that
for
. (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”.
Any relation to Sergey Yekhanin’s construction of 3-query locally decodable codes? A part of his constructions looks somewhat similar.
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 ?
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
Pingback: Touching Simplices and Polytopes: Perles’ argument | Combinatorics and more
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