Tag Archives: Shifting

(Eran Nevo) The g-Conjecture III: Algebraic Shifting

This is the third in a series of posts by Eran Nevo on the g-conjecture. Eran’s first post was devoted to the combinatorics of the g-conjecture and was followed by a further post by me on the origin of the g-conjecture. Eran’s second post was about the commutative-algebra content of the conjecture. It described the Cohen-Macaulay property (which is largely understood and known to hold for simplicial spheres) and the Lefshetz property which is known for simplicial polytopes and is wide open for simplicial spheres.

The g-conjecture and algebraic shifting

Squeezed spheres

Back to the question from last time, Steinitz showed that

any simplicial 2-sphere is the boundary of a convex 3-polytope.

However, in higher dimension

there are many more simplicial spheres than simplicial polytopes,

on a fixed large number of vertices. Continue reading

Extremal Combinatorics IV: Shifting

 

Compression

 

We describe now a nice proof technique called “shifting” or “compression” and mention a few more problems.

 

The Sauer-Shelah Lemma:

Let N=\{1,2,\dots,n\}. Recall that a family {\cal F} \subset 2^N shatters a set S \subset N if for every R \subset S there is T \in {\cal F}  such that S \cap T=R.

Theorem (Sauer-Shelah): If |{\cal F}| > {n \choose 0} + {n \choose 1} + \dots + {n \choose k} then there exists a set S, |S|=k+1, such that \cal F shatters S.

Proof by Shifting

I will describe now a proof of the Sauer-Shelah theorem which is not the easiest but still is quite easy and demonstrates an important technique called “shifting” or “compression” (for an application to additive number theory look at this post by Terry Tao).

The idea of shifting is to reduce an extremal problem for a family of sets \cal F to the case of families of a special type. In the case of the Sauer-Shelah Theorem we first make a reduction to families which are closed under taking subsets (such families are called “ideals,” “down-sets,” and “simplicial complexes”).  Then we prove the theorem for such families. Continue reading