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.
PERTURBATION LEMMA: Consider two linear maps
of two real vector spaces and . Assume that
Then a generic linear combination of and has kernel
Cool, no? Proof, then: Find a subspace of such that
so that in particular is injective on . Then, for small enough, the image of
But if we norm in any way, then approximates as tends to zero, which is linearly independent from by assumption. WALLA
Now, how is this used.
Let me set up some of the basic objects.
If is an abstract simplicial complex on ground-set , let denote the nonface ideal in , where .
Let denote the face ring of . A collection of linear forms in the polynomial ring is a partial linear system of parameters if
for the Krull dimension. If , then is simply a linear system of parameters, and the corresponding quotient is called an Artinian reduction of .
(HL) For every sphere of even dimension , there is an Artinian reduction and a degree one element such that the map
is an isomorphism.
This is quite a reasonable demand. Indeed, Graebe proved that and that the resulting pairing
is perfect, so and 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 -conjecture (and other conjectures, such as the Grünbaum conjecture), and proving the hard Lefschetz theorem in full generality is not much harder.
Lets recall a cool notion due to Provan and Billera: A pure simplicial -complex is vertex decomposable if it is a simplex, or there exists a vertex whose link is vertex decomposable of dimension and its deletion is vertex decomposable of dimension .
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 being clear.
Lets label the vertices of in order of their vertex decomposition, from to . Now, will be a linear combination of indeterminates, so lets assume we have constructed an element that uses just the first of them, and such that itself is as close to a Lefschetz element as possible for its kind, that is, the kernel of
is the intersection of kernels of the maps
where ranges from to .
We want to construct a map with this property (which I call the transversal prime property}. To this effect, we want to apply the perturbation lemma to the maps , , and with respect to the spaces and . Let us denote by the ball given as the union of neighborhoods of the first vertices.
For this, we have to find out the kernel of . But this is the the ideal in generated by the monomials of faces which are not in the neighborhood of any of the first vertices. Lets call it . Lets also look at the image of , which by Graebe’s theorem is exactly the span of the images of the maps the maps
where ranges from to .
But then, is in degree if and only if is in degree . Why is that? Because with respect to the Poincaré pairing, (in degree ) and (in degree ) are dual.
The ring is obtained by taking , seen as a quotient of and modding out by the ideal generated by the linear system . But that is of length , even though is only of dimension . We can remove the vertex for the price of removing one of the linear forms, but then we have the same issue, having a -sphere and a system of length . Still, one too many! Taking a subsystem of length , we obtain an Artinian reduction for via a linear system , but what happens to the additional linear form of not in ? It has to act as a Lefschetz element on if we want
to be trivial in degree . But we may assume so by induction! Hence, we can choose as the generic sum of and by the perturbation lemma.
So, ultimately, we can construct a map with the transversal prime property. But then its kernel is the intersection of the kernels of
where ranges from to . But that is . SABABA.
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 -skeleton of above, and there is no need to be vertex decomposable. It is enough to find another nicely decomposable -manifold that contains it the -skeleton of , and then use some technical topological tricks to connect the local picture to global homological properties.