Karim Adiprasito: The g-Conjecture for Vertex Decomposible Spheres

J Scott Provan (site)

The following post was kindly contributed by Karim Adiprasito. (Here is the link to Karim’s paper.) Update: See Karim’s comment on the needed ideas for extend the proof to the general case. See also  in the comment section references to papers by Balin and Fleming and by Jensen and Yu.

So, Gil asked me to say a little bit about my proof of the g-conjecture (and some other conjectures in discrete geometry) on his blog, and since he bought me many  coffees to explain it to him (or if he is to be believed, the department paid), I am happy to oblige.

So, I want to explain a special, but critical case to the proof. It contains the some shadow of the core ideas necessary, but needs some more tricks I will remark on afterwards.

Also, I wanted to take this opportunity to mention something marvelous that I learned from Leonid Gurvits recently that increased my own understanding of one of the key tricks used indefinitely. That trick is the following cool lemma.

Leonid Gurvits

Perturbation lemma

PERTURBATION LEMMA: Consider two linear maps

\alpha, \beta: X\ \longrightarrow\ Y

of two real vector spaces X and Y. Assume that

\beta (\ker \alpha ) \cap \rm{im}~ \alpha =\{0\} \subset Y.

Then a generic linear combination \alpha ``+"\beta of \alpha and \beta  has kernel
\ker (\alpha  ``+" \beta )= \ker \alpha \cap \ker \beta.

Cool, no? Proof, then: Find a subspace A of X such that

\alpha A\ =\ \alpha X\quad \text{and}\ \quad X\ \cong\ A \oplus \ker\alpha

so that in particular \alpha is injective on A. Then, for \epsilon \ge 0 small enough, the image of

\alpha\ +\ \epsilon \beta{:}\ X\ \longrightarrow\ Y


(\alpha\ +\ \epsilon \beta)(A)\ +\ \beta\ker\alpha\ \subset\ Y.

But if we norm Y in any way, then (\alpha+\epsilon \beta)(A) approximates \alpha A as \epsilon tends to zero, which is linearly independent from \beta\, \ker\alpha by assumption. WALLA

Now, how is this used.

Face rings

Let me set up some of the basic objects.

If \Delta is an abstract simplicial complex on ground-set [n]:= \{1,\cdots,n\}, let I_\Delta := \langle \textbf{x}^{\textbf{a}}: supp (\textbf{a})\notin\Delta\rangle denote the nonface ideal in \mathbb{R}[\mathbf{x}], where \mathbb{R}[\mathbf{x}]=\mathbb{R}[x_1,\cdots,x_n].

Let \mathbb{R}^\ast[\Delta]:= \mathbb{R}[\mathbf{x}]/I_\Delta denote the face ring of \Delta. A collection of linear forms \Theta=(\theta_1,\cdots,\theta_l) in the polynomial ring \mathbb{R}[\textbf{x}] is a partial linear system of parameters if

\dim_{\rm{Krull}} {\mathbb{R}^\ast[\Delta]} {\Theta \mathbb{R}^\ast[\Delta]} =\dim_{\rm{Krull}} \mathbb{R}^\ast[\Delta]-l,

for \dim_{\rm{Krull}} the Krull dimension. If l=\dim_{\rm{Krull}} \mathbb{R}^\ast[\Delta] = \dim \Delta +1, then \Theta is simply a linear system of parameters, and the corresponding quotient A(\Delta)={\mathbb{R}^\ast[\Delta]}/{\Theta \mathbb{R}^\ast[\Delta]} is called an Artinian reduction of \mathbb{R}^\ast[\Delta].

The g-conjecture

The g-conjecture (as described earlier  in Gil’s blog) is implied by the following property:

(HL) For every sphere S of even dimension d-1=2k, there is an Artinian reduction A(S) and a degree one element \ell such that the map

A^k(S) \ \xrightarrow{\ \cdot \ell\ }\ A^{k+1}(S)

is an isomorphism.

This is quite a reasonable demand. Indeed, Graebe proved that A^d(S) \cong \mathbb{R} and that the resulting pairing

A^k(S) \times A^{k+1}(S)\rightarrow \mathbb{R}

is perfect, so A^k(S) and A^{k+1}(S) are isomorphic as vector spaces. We shall call this property (PD), because it is a special case of Poincaré pairing.

(HL) is a special case of the Hard Lefschetz Theorem I prove in my paper, and we will prove it for a subset of all triangulated spheres here. Proving it for all spheres implies the g-conjecture (and other conjectures, such as the Grünbaum conjecture), and proving the hard Lefschetz theorem in full generality is not much harder.

Lou Billera

Vertex-decomposable spheres

Lets recall a cool notion due to Provan and Billera: A pure simplicial d-complex is vertex decomposable if it is a simplex, or there exists a vertex whose link is vertex decomposable of dimension d-1 and its deletion is vertex decomposable of dimension d.

We restrict our attention to vertex decomposable spheres and disks and assume the boundary of the link is vertex decomposable as well in every step.

THEOREM: Vertex decomposable spheres satisfy (HL).

We prove this theorem by induction on dimension, the base case of zero-dimensional spheres (k=0) being clear.

Lets label the vertices of S in order of their vertex decomposition, from 1 to n. Now, \ell will be a linear combination of indeterminates, so lets assume we have constructed an element \ell_i that uses just the first i of them, and such that \ell_i itself is as close to a Lefschetz element as possible for its kind, that is, the kernel of

A^k(S) \ \xrightarrow{\ \cdot \ell_i\ }\ A^{k+1}(S)

is the intersection of kernels of the maps

A^k(S) \ \xrightarrow{\ \cdot x_j\ }\ A^{k+1}(S)

where j ranges from 1 to i.

We want to construct a map \ell_{i+1} with this property (which I call the transversal prime property}. To this effect, we want to apply the perturbation lemma to the maps \beta x_{i+1}, \alpha=\ell_i, and with respect to the spaces X=A^k(S) and Y=A^{k+1}(S). Let us denote by D the ball given as the union of neighborhoods of the first i vertices.

For this, we have to find out the kernel of \ell_i. But this is the the ideal in A(S) generated by the monomials of faces which are not in the neighborhood of any of the first i vertices. Lets call it K. Lets also look at the image I of \ell_i, which by Graebe’s theorem is exactly the span of the images of the maps the maps

A^k(S) \ \xrightarrow{\ \cdot x_j\ }\ A^{k+1}(S)

where j ranges from 1 to i.

But then, x_{i+1}K \cap I is 0 in degree k+1 if and only if A(st_{i+1} \partial D) is 0 in degree k. Why is that? Because with respect to the Poincaré pairing, x_{i+1}K \cap I (in degree k+1) and A(st_{i+1} \partial D) (in degree k) are dual.
The ring A(st_{i+1} \partial D) is obtained by taking \mathbb{R}[st_{i+1} \partial D], seen as a quotient of \mathbb{R}[S] and modding out by the ideal generated by the linear system \Theta. But that is of length d, even though st_{i+1} \partial D is only of dimension d-2. We can remove the vertex i+1 for the price of removing one of the linear forms, but then we have the same issue, having a (d-3)-sphere st_{i+1} \partial D and a system \Theta' of length d-1. Still, one too many! Taking a subsystem of length d-2, we obtain an Artinian reduction for \mathbb{R}[lk_{i+1} \partial D] via a linear system \Theta'', but what happens to the additional linear form of \Theta' not in \Theta''? It has to act as a Lefschetz element on \mathbb{R}[lk_{i+1} \partial D]/\Theta''\mathbb{R}[lk_{i+1} \partial D] if we want

A(st_{i+1} \partial D)\ \cong\ \mathbb{R}[lk_{i+1} \partial D]/\Theta'\mathbb{R}[lk_{i+1} \partial D]

to be trivial in degree k. But we may assume so by induction! Hence, we can choose \ell_{i+1} as the generic sum of \ell_i and x_{i+1} by the perturbation lemma.

So, ultimately, we can construct a map \ell_n with the transversal prime property. But then its kernel is the intersection of the kernels of

A^k(S) \ \xrightarrow{\ \cdot x_j\ }\ A^{k+1}(S) ,

where j ranges from 1 to n. But that is 0SABABA.

And beyond?

Now, we have the Lefschetz theorem for a special class, but that is less than what we want in the end, since vertex decomposable spheres are few and in between (do you see a reason why? there are many). So, what do we do? For a long time, I tried to extend the perturbation lemma to combine more than two maps.
Recently (depending on when Gil puts this post on the blog), I met Leonid Gurvits for the first time on a marvelous little conference at the Simons Institute. I knew that the problem is related to Hall’s Marriage Theorem for operators (I explain this connection a bit further in my paper), but Leonid enlightened this further by pointing me towards several nice papers, starting with his work on Quantum Matching Theory. Indeed, finding a good extension to three and more maps would essentially mean that we could also find Hall Marriage Type Theorems for 3-regular hypergraphs, which we know for complexity reasons to be unlikely.

So what can we do instead? Well, it turns out that I only really needed to look at the k-skeleton of S above, and there is no need to be vertex decomposable. It is enough to find another nicely decomposable d-1-manifold that contains it the k-skeleton of S, and then use some technical topological tricks to connect the local picture to global homological properties.




This entry was posted in Combinatorics, Convex polytopes, Geometry, Guest blogger and tagged , , , , . Bookmark the permalink.

9 Responses to Karim Adiprasito: The g-Conjecture for Vertex Decomposible Spheres

  1. dsp says:

    While I try to understand this argument, can I just ask if there’s any chance of a detailed blog post on McMullen’s proof of the g-theorem for polytopes in the near future?

  2. both objects (minkowski weights + McMullen product and conewise polynomials + natural multiplication) are isomorphic, you can write me an email if you like.

    • Gil Kalai says:

      Let me add that vertex-decomposable d-1-dimensional spheres with n vertices satisfy the Hirsch bound and the stronger property that one can move between every facet F to every facet G by a path of adjacent facets (“non-revisiting path) with the property that once you leave a vertex you never return to it. (Since every time you move from a facet to an adjacent facet you leave a vertex it implies that the length of the path is at most n-d.)

      It is very nice that this notion introduced for the study of Hirsch’s conjecture was useful in the study of the g-conjecture.

  3. Gil Kalai says:

    Karim, can you give an overview of the ideas and tricks needed to go beyond the vertex-decomposable case?

    • Sure, let me give it a try. This is essentially expanding on the last part of my post, so you are welcome to move it there, Gil.

      So, in my proof I said that
      x_{i+1}K \cap I has to be 0. Well, it turns out that K and I are orthogonal complements, so what I am asking is equivalent to saying that the Poincaré pairing is non-degenerate on one of them (or equivalently, on both) in the restriction to the ideal of x_{i+1}.

      So, how does that help? Well, on the other hand, I observed that this property of x_{i+1}K \cap I = 0 is equivalent to a Lefschetz property, and in fact the Lefschetz property we want.

      So, say you want to prove the hard Lefschetz theorem for a sphere S of dimension d-1. What you do is embed your sphere in a d-sphere S' as a hypersphere (neologism of hypersurface+sphere). Now, the essential observations are:
      (A) Lefschetz for S is equivalent to non-degeneracy of the Poincaré pairing in A(S') at the non-face ideal of S. This is what I call biased Poincaré duality in the paper.
      (B) The latter property about the pairing is, by the decomposition theorem (or rather, a variant thereof), independent of how S' is triangulated outside of S, and in particular is invariant under any refinements you make to S' outside of the hypersphere.

      So, how does that help, if S is not vertex decomposable. Well, if we adopt the parameters of my proof ( 2k=d-1), then we need to prove this pairing property in S'. But for this we would need the Lefschetz theorem for S, no? Well, not quite. I only need the k -skeleton of S (because that is the degree where the pairing ultimately interests us).

      Cool but folklore observation: If you have a k -dimensional complex in a (2k+1)-dimensional manifold, then that complex embeds into all kinds of nice hypersurfaces of the manifold. In our situation, that means that the k -skeleton of S embeds into different hypersurfaces (i.e. not only S) in S', in particular ones that are very close to vertex-decomposable (to realize these hypersurfaces combinatorially, I sometimes need to use observation (B)). For such a hypersurface X, I then can prove a version of the hard Lefschetz theorem, which then is equivalent to stating that for the nonface ideal of X in A(S'), biased Poincaré duality is true. Now, there is an easy observation that you can cleverly choose X so that within A(S') and in the relevant degree (in this case k+1), the nonface ideals of X and S are isomorphic.

      But then you have not only proven biased Poincaré duality for the nonface ideal of X, but also for the non-face ideal of S (as they are isomorphic in the relevant degree. Using (A) again you obtain the Lefschetz theorem for S.

  4. Pingback: Dan Romik Studies the Riemann’s Zeta Function, and Other Zeta News. | 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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s