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 split exact 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. However, the crucial property is split exactness, i.e., the existence of a monomorphism from Hd-1(Mn-2; Z) to Hd(Mn; Z).
If the above conjecture were true, then we would obtain that Hd(Mn; Z) contains p-torsion whenever Hd-1(Mn-2; Z) contains p-torsion. 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 split exact 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, this is indeed true for d equal to the ceiling of (n-4)/3. In fact, I have been able to extend this result to (n-4)/3 ≤ d ≤ (n-7)/2; see §11.2.3 in my thesis. In recent work (soon to be posted on this page), I also settle the case d = (n-6)/2.
Recently, I discovered 5-torsion in H4(M14; Z). In itself, this observation is a mere curiosity. Yet, combining this with the above conjecture, we would obtain that H4+k(M14+2k; Z) contains 5-torsion for all nonnegative integers k. This would be a highly significant result.
Let G be a simple graph. Let us define a transfer matrix T(G) indexed by all independent vertex sets of G; a vertex set is independent if no two vertices in the set are joined by an edge. The value of T(G) on position (σ,τ) is (-1)|σ| if σ ∩ τ is empty and 0 otherwise. If we know the characteristic polynomial of T(G), then we can compute the Euler characteristic of the independence complex of G × Cn for all n, where Cn is the cycle graph on n vertices. See this paper for more information about the special case G = Cm.
In the paper just referenced, we prove that all eigenvalues of T(Cm) are roots of unity. Another class with the same property is the class of complete bipartite graphs. Experiments suggest that the property holds also for Pm, the path graph on m vertices.
The big problem is to characterize all graphs with this "roots of unity" property.
Not all graphs have this nice property. The smallest counterexample is the graph on five vertices and six edges consisting of a five-cycle and an additional chord. In this case, all roots of the polynomial t6 - t4 + t3 - t2 + 1 are eigenvalues of the transfer matrix. Another counterexample is the product graph C3 × C3. We have also found a bipartite counterexample on ten vertices (most likely not the smallest such graph). This implies that our property is not closed under deletion of edges.