Around the Garsia-Stanley’s Partitioning Conjecture

 

Art Duval, Bennet Goeckner, Carly Klivans, and Jeremy Martin found a counter example to the Garsia-Stanley partitioning conjecture for Cohen-Macaulay complexes. (We mentioned the conjecture here.)  Congratulations Art, Bennet, Carly and Jeremy!  Art, Carly, and Jeremy also wrote an article on the the Partitionability Conjecture in the Notices of the AMS.  (Here is an article about it in the Brown Daily Herald.) Let me tell you about the conjecture and related questions. Here are the last few sentences of the paper.

Even though statements like the Partitionability Conjecture can seem too beautiful to be false, we should remember to keep our minds open about the mathematical unknown—the reality might be quite different, with its own unexpected beauty.

I. Symmetric chain decomposition for the Boolean lattice

I will start with an analogy.

Let P(n) be the family of all subsets of {1,2,…, n}. A family of subsets of {1,2,…, n} is an antichain if no set in the family contains another set in the family. Sperner’s theorem (see this post) asserts that for every antichain  of subsets of we have  .

So we have a combinatorial notion: an antichain, and we have a numerical consequence: Sperner’s theorem. Our aim is to give a structure theorem which implies the numerical consequence. A saturated symmetric chain is a chain of sets of sizes , for some .

Symmetric chain decomposition: P(n) can be partitioned into saturated symmetric chains

The partition of P(n) into saturated symmetric chain gives you a combinatorial structure that implies the “numerical” content of Sperner’s theorem. The Garsia-Stanley’s conjecture has a somewhat similar flavor.

Let me note that there are stronger numerical results about antichains such as the LYM inequality (see the same post) and  an interesting question (I think)  is:

Question: Are there decomposition theorems for P(n) that support stronger numerical results about antichains,  such as the LYM inequality?

II. The general framework

The general framework of our discussion is described in the following diagram:

We will consider classes of objects (usually simplicial complexes) described by algebraic or topological properties (TOP) and a smaller class defined by a combinatorial notion (RIGHT). The topological/algebraic properties has some interesting numerical consequences (LEFT). Our task is to find general decomposition theorems that are implied by the topological notions and suffice to imply the numerical consequences.

III. Acyclic complexes, collapsibility and  matching

The algebraic topological notion: acyclic simplicial complex.

The combinatorial notion: collapsible simplicial complexes.

Numerical relations: (1) Euler-poincare relation, (2) Morse inequalities, (3) a certain system of non linear inequalities.

The decomposition theorem was proved by Stanley.

 

Fixing a field of coefficients, a simplicial complex is acyclic if all its (reduced) homology groups vanish.  A simplicial complex is collapsible if you can reduce it to the void complex by repeated deletion of pairs of faces (F,G) where G is a facet (maximal face) F is contained in G and is not contained in any other facet and . Note that a collapsing of gives a perfect matching among the faces of (We discussed collapsible and acyclic complexes in this post, and gave Bing’s example for non-collapsible contractible complex is this follow up post.)

Let be the number of -faces of , and  let . The Euler-Poincare relation asserts that , Morse inequalities (a baby version) assert that all the s are nonnegative, and (I showed that) they also satisfy some non linear relations of Kruskal-Katona nature. In the paper A combinatorial decomposition of acyclic simplicial complexes, Stanley proved that if K is acyclic, there is a perfect matching in the set of faces of which resembles the matching obtained by collapsing, Namely (1) , , and (2) the ‘s form a simplicial complex. The existence of this perfect matching implies the numerical consequences for acyclic complexes. (But it does not imply that the complex is acyclic.)  Earlier, I proved that a perfect matching with the first property exists. This implies the linear (Morse) inequalities.

Diversion: Zeeman’s conjecture

Zeeman conjectured that if a 2-dimensional space is contractible then is collapsible. ( is the unit interval. This innocent-looking conjecture  is widely believed to be false (perhaps even outrageous) because it implies both the Poincare conjecture (now theorem) and also the Andrews-Curtis conjecture.

IV. Complexes with prescribed Betti numbers. Duval’s theorem and discrete Morse Theory

The algebraic topological notion: simplicial complex with prescribed Betti-numbers.

The combinatorial notion: Discrete Morse theory. (This is an important notion developed by Robin Forman in the mid 90s.)

Numerical relations (Bjorner and me, late 80s): (1) Euler-poincare relation, (2) Morse inequalities, (3) a certain system of non linear inequalities.

The decomposition theorem was proved by Art Duval in the paper A Combinatorial Decomposition of Simplicial Complexes.

 

In this case  Duval proved that the set of faces in the complex admits a matching (leaving isolated faces that correspond to the Betti numbers) which implies the numerical consequences found by Bjorner and me. It resembles the structure of discrete Morse theory.

 

V. The Cohen-Macaylay property, shellability, and the Garsia-Stanley’s conjecture

The algebraic topological notion: Cohen-Macaulay simplicial complex.

The combinatorial notion: shellable simplicial complexes.

Numerical relations: (1) The h-numbers are non negative , (3) a certain non linear inequalities (The h-vector form an M-vector).

A decomposition conjecture: the the Garsia Stanley conjecture (now disproved). (A weaker form was proved by Duval and Zhang.)

 

Richard Stanley in 1979 and Adriano Garsia in 1980 conjectured that the faces of every -dimensional Cohen-Macaulay simplicial complex can partitioned into intervals  [] where is a facet (top dimensional) for every .  The paper by Duval, Geockner, Klivans, and Martin,  A non-partitionable Cohen-Macaulay simplicial complex, presents a counter example. A weaker form of the conjecture was proved by Duval and Zhang.

The Cohen Macaulay property for simplicial complexes and POSETS

We discussed face rings, and the Cohen-Macauly property in various previous posts like the one by Eran Nevo on on the commutative algebra connection to the g-conjecture, and the happy birthday post for Richard Stanley. A -dimensional simplicial complex is Cohen-Macaulay (with respect to a field of coefficients,) if when and for every face latex when . This property is equivalent (by a deep theorem of Riesner) to the Cohen-Macaulay property for the face ring of . The ring theoretic definition of Cohan-Macaulayness can be seen as an algebraic form (on the level of vector spaces) of the combinatorial decomposition conjectured by Garsia and Stanley.

The numerical consequences

The Cohen-Macauly property implies that a certain linear combinations of face numbers called the h-numbers are non-negative, and in addition satisfies certain nonlinear relations originated in the 1927 work of Macaulay. For complexes that admit the partitioning conjectured by Garsia and Stanley the h-numbers count the number of intervals in the partition according to the dimensions of the s. (This implies the nonnegativity of the h-numbers.)

Shellability and the decomposition conjecture

A pure -dimensional simplicial complex is shellable if it can partitioned into intervals  [] where is a facet (top dimensional) for every , and the union of the first intervals is a simplicial complex for every . A shellable simplicial complex is Cohen Macaulay (a direct proof of the ring-theoretic statement was was given by Kind and Kleinschmidt in 1979.) Shelling of a simplicial complex can be seen as a special form of decomposition.  It is a partitioned into intervals  [] where is a facet (top dimensional) for every with the additional property that the union of the first  intervals in the partition is a simplicial complex for every .

Cohen-Macauly complexes are not necessarily shellable, since shellability implies stronger homotopical properties. But even these stronger homotopical properties do not suffice, Marry Ellen Rudin found an example of non-shellable simplicial ball. (See also here.)

VI. The ultimate partitioning conjecture (to intervals) and Duval and Zhang (almost) ultimate partitioning theorem (to trees).

 

The algebraic topological notion: General simplicial complex. (With prescribed shifted complex, if you wish).

The combinatorial notion: non-pure shellability. (This notion introduced by Michelle Wachs is also sometimes called michellability.)

A decomposition conjecture (by me) decomposition of the shifted complex into intervals can be mimicked on the original complex. (More general than the Garsia-Stanley conjecture and thus false.) This decomposition implies the system of linear equaltions satisfied by simplicial complexes with prescribed algebraic shifting. (See, this paper on algebraic shifting, and this post on algebraic shifting.)

A decomposition theorem (by Duval and Zhang):  decomposition of the shifted complex into intervals can be mimicked by a decomposition of  the original complex into certain trees in the paper Iterated Homology and Decompositions of Simplicial Complexes.

 

Boolean trees

A few  remaining questions

1) Find a version of Duval-Zhang decomposition theorem for Cohen-Macauly complexes that supports also the non-linear inequalities for the -vector. (Like the decomposition theorems of Stanley and of Duval.) Extend to the general case of Duval-Zhang theorem!

2) Is there an analog for discrete Morse theory (using either Boolean trees or full Boolean intervals) for triangulated manifolds (and more generally Buchsbaum compexes) for the usual homology and for various classes of  iterated homology?

3) For the class of triangulated spheres is there a tree-decomposition a la Duval and Zhang that supports the non negativity of g-numbers or the full g-conjecture?

4) Can these partitioning theorems be extended to more general classes of regular CW complexes?

And let me end with two more sentences from the ending paragraph of the Notices paper.

The story of the Partitionability Conjecture has many facets. Shellability, partitionability, constructibility, and the Cohen-Macaulay property come from different but overlapping areas of mathematics: combinatorics, commutative algebra, topology, and discrete geometry. The hierarchy of these structural properties turned out to be more complicated than we had anticipated, just as Rudin’s and Ziegler’s examples demonstrate that even the simplest spaces can have intricate combinatorics.

 

Advertisements