Let F be a field or the ring of integers. We are interested in the following problem:
Under what conditions on a pure and vertex-transitive simplicial complex Σ is it always true that Σ is Cohen-Macaulay over F whenever Σ has no homology over F below the dimension of Σ?
(A complex Σ is vertex-transitive if, for each pair of vertices v and w in Σ, there is an automorphism φ on Σ such that φ(v) = w.) So far, I have not found a single counter-example, but it would be surprising if there were no counter-examples, wouldn't it?
Given a family of graphs on a fixed vertex set V, we may identify the graphs in the family with their edge sets. If the family is closed under deletion of edges, this identification makes it possible to interpret the family as a simplicial complex. Such a complex is a monotone graph property if the complex is invariant under permutations of the underlying vertex set V.
Under what conditions on a pure monotone graph property Σ is it always true that Σ is Cohen-Macaulay over F whenever Σ has no homology over F below the dimension of Σ?
Some examples:
The complex of disconnected graphs on a fixed vertex set of size n has a vertex-decomposable (n-3)-skeleton and is homotopy equivalent to a wedge of spheres of dimension n-3.
John Shareshian and Michelle Wachs demonstrated that a certain skeleton of the matching complex Mn is shellable. They also proved that Mn has nonvanishing homology in the dimension of the examined skeleton. Moreover, it is not hard to prove that a bigger skeleton is Cohen-Macaulay over Q. The dimension of this skeleton is exactly the smallest dimension with nonvanishing rational homology; this dimension is easy to compute by the work of Bouc.
By results of John Shareshian, the (2n-5)-skeleton of the complex of not 2-connected graphs on n vertices is Cohen-Macaulay. This complex is known to be homotopy equivalent to a wedge of spheres of dimension 2n-5 (see Shareshian's paper for references).
It is easy to prove that the (n-2)-skeleton of the complex of bipartite graphs on n vertices is Cohen-Macaulay over Z. By results of Manoj Chari and of Svante Linusson and John Shareshian, this complex is homotopy equivalent to a wedge of spheres of dimension n-2. More generally, for each integer p < n/2, one may consider the complex of bipartite graphs that are subgraphs of some copy of Kr, n-r for some r ≤ p. This complex is homotopy equivalent to a wedge of spheres of dimension 2p-1 and has a Cohen-Macaulay (2p-1)-skeleton.
Let us say that a simplicial complex Δ is nearly nonevasive if the deletion of Δ with respect to some vertex is nonevasive. Clearly, any nonevasive complex, the 0-simplex excluded, is also nearly nonevasive. For vertex-transitive complexes, a particular deletion is nonevasive if and only if all deletions are nonevasive; the choice of vertex is immaterial. In particular, nonevasive monotone graph properties have this property. A complete solution to the following problem would mean significant progress on Karp's evasiveness conjecture, maybe even a complete solution:
Characterize the family of nearly nonevasive monotone graph properties.
The family is easily seen to be nonempty. Namely, the monotone graph property of not being the complete graph on n vertices is nearly nonevasive as the deletion with respect to any element is the full simplex. Yet another example of a nearly nonevasive graph property is the property of not containing a perfect matching on four vertices. Namely, the deletion with respect to (say) the edge 12 is a cone with cone point 34. In fact, this graph property is isomorphic to the octahedron. It is not hard to demonstrate that these are the only monotone graph properties such that the deletion is a cone.
However, there are more nearly nonevasive monotone graph properties. Namely, in the paper ``Optimal Decision Trees on Simplicial Complexes'', I provide a decision tree on the complex of not 2-connected graphs on n vertices such that all evasive faces contain the edge 1n. This implies that the complex is nearly nonevasive for each n. By the work of Babson-Björner-Linusson-Shareshian-Welker and Turchin, we know that the complex is homotopy equivalent to a nonempty wedge of spheres, which implies that the complex is not evasive.
In this context, I cannot resist mentioning the intriguing observation that each sphere in the wedge corresponds, in a very natural manner, to a copy of the associahedron; this observation is due to John Shareshian and Michelle Wachs; Shareshian describes it at the end of one of his papers.
It would be very interesting to know whether there are further examples of nearly nonevasive monotone graph properties. My hope is that this is indeed the case. Namely, any example is likely to have a rich and beautiful structure. A related problem is whether nearly nonevasive monotone graph properties have a ``nice'' homotopy type in general. The examples we have found are all wedges of spheres.
Of course, the following more general problem is also of great importance:
Characterize the family of nearly nonevasive vertex-transitive simplicial complexes.
For example, vertex-decomposable boundary complexes of simplicial polytopes (e.g., the dodecahedron and the icosahedron) are nearly nonevasive.
Let Δ be a simplicial complex of graphs on the vertex set [k], where k is a positive integer. For n ≥ k, define Δn as the simplicial complex on the vertex set [n] defined as follows: If G belongs to Δ and r1, ... , rk are integers such that
1 ≤ r1 < ... < rk ≤ n,
then G' belongs to Δn, where G' is the graph obtained from G by replacing the edge ab with the edge rarb for each edge ab in G.
One readily verifies that the number of cells of dimension d in Δn is given by a polynomial in n of degree at most k for each d. Our question is as follows:
Fix a field F and an integer d. Is there a polynomial f and an integer N such that the dimension of the d-th homology group over F of Δn is equal to f(n) whenever n ≥ N?
In general, we cannot pick N=k. For example, if Δ is the matching complex on four vertices, then Δn is shellable and hence has no homology in dimension 0 if n ≥ 5. However, Δ itself consists of three connected components and thus has homology in dimension 0. There is no nonzero polynomial with infinitely many zeros, which implies that we must pick N>4.
Let Mn be the matching complex on the vertex set {1, 2, 3, ..., n} and let e be the 0-cell corresponding to the edge between n-1 and n. I am interested in knowing whether the following sequence of reduced homology groups is exact and splits for every d:
0 ----> Hd(Mn - e; Z) ----> Hd(Mn; Z) ----> Hd-1(Mn-2; Z) ----> 0.
Here, Mn - e is the subcomplex obtained from Mn by removing the 0-cell e. I have verified this to be true for n ≤ 11. By the long exact sequence for the pair (Mn, Mn - e), the above sequence being exact is equivalent to every cycle in Hd-1(Mn-2) being zero in Hd-1(Mn - e) for every d.
If the above conjecture were true, then we would obtain that Hd(Mn; Z) is nonzero whenever Hd-1(Mn-2; Z) is nonzero. Now, by the work of Bouc, Hk-1(M3k+1; Z) is isomorphic to Z3 for k ≥ 2 and infinite for k = 0, 1. As a consequence, our sequence being exact would imply that Hd(Mn; Z) is nonzero whenever (n-4)/3 ≤ d ≤ (n-3)/2. Moreover, the sequence splitting would imply that Hd(Mn; Z) contains nonvanishing 3-torsion whenever (n-4)/3 ≤ d ≤ (n-5)/2. By the work of Shareshian and Wachs, the latter property is known to be true for d equal to the ceiling of (n-4)/3.
If you want to get in touch with me, send an email to jakob_jonsson at yahoo.se.
The information on this page is provided as is, and no warranty is given or implied that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability.
All trademarks are property of their respective owners.
© Copyright 2003-2006 by Jakob Jonsson. All rights reserved.