ALGEBRAIC SHIFTING INCREASES RELATIVE HOMOLOGY

ART M. DUVAL

Abstract. We show that algebraically shifting a pair of simplicial complexes weakly increases their relative homology Betti numbers in every dimension.

More precisely, let Δ(K) denote the algebraically shifted complex of simplicial complex K, and let β_{j}(K, L) = dim_{k} H̃_{j}(K, L; k) be the dimension of the jth reduced relative homology group over a field k of a pair of simplicial complexes L ⊆ K. Then β_{j}(K, L) ≤ β_{j}(Δ(K), Δ(L)) for all j.

The theorem is motivated by somewhat similar results about Gröbner bases and generic initial ideals. Parts of the proof use Gröbner basis techniques.

1. Introduction

Algebraic shifting is a remarkable procedure that finds, for any simplicial complex K, a shifted (and hence combinatorially simpler) simplicial complex Δ(K) with many of the same properties as K. For instance, the f-vector and homology Betti numbers are preserved; Björner and Kalai [BK1] used this fact to characterize the f-vectors and Betti numbers of simplicial complexes.

However, the situation for pairs of complexes and relative homology is different. In a simple example on three vertices (Example 3.1), algebraically shifting a pair of complexes increases their relative homology in dimensions 0 and 1. Upon seeing this one example, Keith Pardue (private communication) conjectured that algebraic shifting always weakly increases relative homology in every dimension. Our main result (Theorem 5.2) is that this conjecture is true.

Pardue’s conjecture was grounded in more than just this one simple example. Algebraic shifting, which takes place in exterior (anti-commutative) algebra, is similar to using Gröbner bases and generic initial ideals in commutative algebra (see Section 3). Quantities such as free resolution Betti numbers weakly increase upon taking generic initial ideals (see, e.g., [Hu1, Hu2, Bi], and Section 3). Pardue’s insight was that these results would carry over to algebraic shifting.

It would be ideal, then, to prove his conjecture by translating the algebraic shifting problem to a generic initial ideal problem, and then invoking the existing results. However, this approach has been unsuccessful, so far. The proof here, while motivated at points by Gröbner basis ideas (see Lemma 4.1), instead directly refines Björner and Kalai’s correspondence between the homology of the original complexes and the combinatorics of the algebraically shifted complexes. The hope is that this result will serve as further evidence of the deeper connection between algebraic shifting and generic initial ideals.

Research performed while a General Member of the Mathematical Sciences Research Institute, Berkeley. Research at MSRI is supported in part by NSF grant DMS-9701755.

Background and notation on simplicial complexes, including homology, shifted complexes, and near-cones is in Section 2. Algebraic shifting is reviewed and compared to generic initial ideals in Section 3. In Section 4, we use Gröbner basis ideas to define a nice basis of a space associated with a pair of complexes (K, L), and then use this basis to compare key components of the homology groups of (K, L) and (Δ(K), Δ(L)). We prove our main result (Theorem 5.2) in Section 5.

2. Simplicial complexes

For basic definitions of simplicial complexes and their homology and relative homology, see, e.g., [Mu, Chapter 1] or [St2, Section 0.3]. We allow the empty simplicial complex ∅ consisting of no faces; all other complexes must contain the empty set as a (−1)-dimensional face. We also allow the complex {∅} consisting of only the empty face, but we do distinguish between the two complexes ∅ and {∅}. Let K_{j} denote the set of j-dimensional faces of a simplicial complex K. The f-vector of K is the sequence (f_{0}, …, f_{d−1}), where f_{j} = f_{j}(K) = |K_{j}| and d − 1 = dim K. The same notion of f-vector will apply in this paper to every finite collection of sets.

Let k be a field, fixed throughout the paper. The jth Betti number of a simplicial complex K is β_{j} = β_{j}(K) = dim_{k} H̃_{j}(K), where H̃_{j}(K) is the jth reduced homology group of K (with respect to k). Similarly, the jth relative Betti number of a pair of simplicial complexes L ⊆ K is β_{j} = β_{j}(K, L) = dim_{k} H̃_{j}(K, L), where H̃_{j}(K, L) is the jth reduced relative homology group of the pair (K, L) (with respect to k).

“Reduced” homology means precisely to treat the empty set as a face of any nonempty complex, so β_{0} is one less than the number of connected components of Δ, and hence one less than the “unreduced” β_{0}. Furthermore, β_{−1} = 0, unless Δ = {∅}, in which case β_{−1} = 1. Reduced relative homology, which also treats the empty set as a face of any non-empty complex, is the same as unreduced relative homology, except that β_{−1}({∅}, ∅) = 1; for any other pair of complexes, β_{−1} = 0.

Definition. If S = {s_{1} < ⋯ < s_{j}} and T = {t_{1} < ⋯ < t_{j}} are j-subsets of integers, then:

• S ≤_{P} T under the standard partial order if s_{p} ≤ t_{p} for all p; and

• S <_{L} T under the lexicographic order if there is a q such that s_{q} < t_{q} and s_{p} = t_{p} for p < q .

Lexicographic order is a total order which refines the partial order.

Definition. A collection C of k-subsets is shifted if S ≤_{P} T and T ∈ C together imply that S ∈ C. A simplicial complex Δ is shifted if the set of j-dimensional faces of Δ is shifted for every j.

Björner and Kalai showed in [BK1] that shifted complexes are near-cones, which we now define.

Definition. A near-cone with apex v_{0} is a simplicial complex Δ satisfying the following property: For all F ∈ Δ, if v_{0} ∉ F and w ∈ F, then

(F − {w}) ∪ {v_{0}} ∈ Δ.

For Δ a near-cone with apex v_{0}, let B(Δ) = {F ∈ Δ: F ∪ {v_{0}} ∉ Δ} and Δ′ = {F ∈ Δ: v_{0} ∉ F, F ∪ {v_{0}} ∈ Δ}; then

Δ = (v_{0} ∗ Δ′) ˙∪ B(Δ),

where ∗ denotes topological join (so v_{0} ∗ Δ′ = Δ′ ˙∪ {{v_{0}} ˙∪ F: F ∈ Δ′}). Both Δ′ and Δ′ ˙∪ B(Δ) are subcomplexes of Δ. If B(Δ) = ∅, then Δ is simply a cone.

Note, in particular, that ∅ and {∅} are near-cones (the condition in the definition is vacuous in this case) and that ∅ = v_{0} ∗ ∅ and {∅} = (v_{0} ∗ ∅) ˙∪ {∅}. If Δ is a near-cone with apex v_{0}, then v_{0} is one of the vertices of Δ, unless Δ = ∅ or {∅}.

It is not hard to see that shifted simplicial complexes are near-cones with apex 1. Every F ∈ B(Δ) is maximal in Δ, so the collection of faces in B(Δ) forms an

antichain. Further, f(B(Δ)) = β(Δ), which follows by contracting v_{0} ∗ Δ′ to v_{0}, leaving a sphere for every face in B(Δ) [BK1, Theorem 4.3]. In other words, if Δ is a near-cone with apex v_{0}, then

β_{j}(Δ) = |{F ∈ Δ_{j}: v_{0} ∉ F, v_{0} ˙∪ F ∉ Δ}|. (1)

This observation is generalized by [Du, Lemma 8]: If Γ ⊆ Δ is a pair of near-cones with common apex v_{0}, then

(2) β_{j}(Δ, Γ) = |{F ∈ (Δ − Γ)_{j}: v_{0} ∉ F, v_{0} ˙∪ F ∉ Δ}| + |{G ∈ (Δ − Γ)_{j}: v_{0} ∈ G, G − {v_{0}} ∈ Γ}|.

In light of the formulation of the homology of near-cones that equation (1) gives, equation (2) is approximately the near-cone equivalent of using the long exact sequence (e.g., [Mu, Theorem 23.3])

⋯ → H̃_{j}(L) ⟶^{i_{∗}} H̃_{j}(K) ⟶^{π_{∗}} H̃_{j}(K, L) ⟶^{∂_{∗}} H̃_{j−1}(L) → ⋯ (3)

to compute

β_{j}(K, L) = dim(im(π_{∗})_{j}) + dim(im(∂_{∗})_{j})

for an arbitrary pair (K, L).

3. Algebraic shifting

Algebraic shifting transforms a simplicial complex into a shifted simplicial complex with the same f-vector and Betti numbers. It also preserves many algebraic properties of the original complex. Algebraic shifting was introduced by Kalai in [Ka1]; our exposition is summarized from [BK1] and included for completeness (see also [BK2, Ka2]). We start with the exterior face ring.

Definition. Let K be a (d − 1)-dimensional simplicial complex with vertices V = {e_{1}, …, e_{n}} linearly ordered e_{1} < ⋯ < e_{n}. Let Λ(kV) denote the exterior algebra of the vector space kV; it has a k-vector space basis consisting of all the monomials e_{S} := e_{i_{1}}∧⋯∧e_{i_{j}}, where S = {e_{i_{1}} < ⋯ < e_{i_{j}}} ⊆ V (and e_{∅} = 1). Note that Λ(kV) = ⊕_{j=0}^{n}Λ^{j}(kV) is a graded k-algebra, and that Λ^{j}(kV) has basis {e_{S}: |S| = j}. Let (I_{K})_{j} be the subspace of Λ^{j+1}(kV) generated by the basis {e_{S}: |S| = j + 1, S ∉ K}. Then I_{K} := ⊕_{j=−1}^{d−1}(I_{K})_{j} is the homogeneous graded ideal of Λ(kV) generated by {e_{S}: S ∉ K}. Let Λ_{j}[K] := Λ^{j+1}(kV)/(I_{K})_{j}. Then the graded quotient algebra Λ[K] := ⊕_{j=−1}^{d−1}Λ_{j}[K] = Λ(kV)/I_{K} is called the exterior face ring of K (over k).

The exterior face ring is the exterior algebra analogue to the Stanley-Reisner face ring of a simplicial complex [St2]. For x ∈ kV, let x̃ denote the image of x in Λ[K].

Definition (Kalai). Let {f_{1}, …, f_{n}} be a “generic” basis of kV, i.e.,

f_{i} = ∑_{j=1}^{n} α_{ij}e_{j},

where the α_{ij}’s are n^{2} transcendentals, algebraically independent over k. Define f_{S} := f_{i_{1}} ∧ ⋯ ∧ f_{i_{j}} for S = {i_{1} < ⋯ < i_{j}} (and set f_{∅} = 1). Let

Δ(K, k) := {S ⊆ [n]: f̃_{S} ∉ span{f̃_{R}: R <_{L} S}}

be the algebraically shifted complex obtained from K; we will write Δ(K) instead of Δ(K, k) when the field is understood to be k. In other words, the j-subsets of Δ(K) can be chosen by listing all the j-subsets of [n] in lexicographic order and omitting those that are in the span of earlier subsets on the list, modulo I_{K} and with respect to the f-basis.

The algebraically shifted complex Δ(K) is (as its name suggests) shifted, and is independent of the numbering of the vertices of K [BK1, Theorem 3.1].

It is easy to see that algebraic shifting preserves the f-vector, i.e., f_{j}(K) = f_{j}(Δ(K)). Björner and Kalai [BK1] showed that algebraic shifting also preserves Betti numbers, i.e., β_{j}(K) = β_{j}(Δ(K)). The reason lies in the relation between algebraic shifting and coboundaries. Define the weighted coboundary operator δ: Λ[K] → Λ[K] by δ(x) = f̃_{1} ∧ x, so

δ(ẽ_{S}) = f̃_{1} ∧ ẽ_{S} = ∑_{j=1}^{n} α_{1j}ẽ_{j} ∧ ẽ_{S} = ∑_{\begin{matrix}j∉S \\ S∪\{j\}∈K \end{matrix}} ±α_{1j}ẽ_{S∪\{j\}}

(hence the name weighted coboundary operator). Betti numbers may be computed using this δ, i.e., β_{j}(K) = dim_{k}(ker δ)_{j}/(im δ)_{j} [BK1, pp. 289–290]. Furthermore, the action of δ on many members of the f̃-basis is easy to describe: δ(f̃_{F}) equals f̃_{1 ˙∪F} if 1 ∉ F and 1 ˙∪ F ∈ Δ(K), but is zero if 1 ∈ F (the third case, when 1 ∉ F, but 1 ˙∪ F ∉ Δ(K), is harder, and we shall not need it).

What about relative homology? First, we note a result of Kalai’s [Ka2, Theorem 2.2] that if L ⊆ K is a pair of simplicial complexes, then Δ(L) ⊆ Δ(K). For every pair (K, L), we may then consider the pair (Δ(K), Δ(L)). In contrast to the single complex case, however, the homology of (K, L) and (Δ(K), Δ(L)) need not coincide, as the following example shows.

Example 3.1. Let K be the simplicial complex on vertices {1, 2, 3} whose maximal faces are {1} and {2, 3}, and L be the subcomplex consisting of just the two vertices {1} and {2}. The only shifted complex with three vertices and one edge has maximal faces {1, 2} and {3}, so this must be Δ(K). Furthermore, L is the only simplicial

[figure: 1; 2; 3; (Δ(K), Δ(L)); 2; 1; 3; (K, L)]

Figure 1. Example 3.1

complex with two vertices and no edges, so Δ(L) = L. (See Figure 1.) But then it is easy to see that (Δ(K), Δ(L)) has non-trivial relative homology in dimensions 0 and 1, while (K, L) has no non-trivial relative homology.

Thus, the relative Betti numbers of (Δ(K), Δ(L)) are all at least as large as those of (K, L). Theorem 5.2 shows that this is true for any pair (K, L).

Algebraic shifting is the exterior algebra analogue of generic initial ideals and Gröbner bases in commutative algebra, in the following way. If I_{K} were instead a monomial ideal of a polynomial ring, then the algorithm used to create the list of non-faces of Δ(K) would instead create a list of monomials generating the generic initial ideal of I_{K}, denoted Gin(I_{K}). For further details of generic initial ideals, see, for instance [Ei, Section 15.9]. For more about the relationship between generic initial ideals and algebraic shifting, see [HT]. For a more general exterior algebra version of Gröbner bases and generic initial ideals, see [AHH, Section 1].

Theorem 5.2 bears some resemblance to results about generic initial ideals (Section 3). For instance, Hulett [Hu1, proof of Lemma 1.24], [Hu2, p. 2338] and Bigatti [Bi, proof of Theorem 3.7] have shown that for any homogeneous ideal I in a polynomial ring, the free resolution Betti numbers of its generic initial ideal Gin(I) are at least as large as those of I.

4. Relative homology

In order to say anything about (Δ(K), Δ(L)), we must first consider (K, L). For Q = K − L (the “Q” is for “quotient”), we define Δ(Q) = Δ(K) − Δ(L). This is primarily a combinatorial definition, with the algebra hidden in the computation of Δ(K) and Δ(L). We now examine how to interpret Δ(Q) algebraically. Let

Q̃ = span{ẽ_{F}: F ∈ Q}.

It is not hard to see, then, that we may algebraically shift the subcomplex L using Λ[K] instead of Λ[L], by modding out by Q̃ on Λ[K] instead of by I_{L} on Λ[L], since Q̃ = Ĩ_{L} (see [Du, Section 3]).

Lemmas 4.1 and 4.2 show how Δ(Q) is related to Q̃, namely that Δ(Q) indexes a nice basis of Q̃; the construction is motivated by Gröbner basis ideas. Then, guided by earlier results about Q̃ (summarized here as Lemma 4.3), we use this basis of Q̃ in Lemmas 4.4 and 4.5 to compare key subspaces of H̃(K, L) and H̃(Δ(K), Δ(L)).

Lemma 4.1. If F ∈ Δ(Q), then there is a unique linear combination ∑\begin{matrix}G<_{L}F \\ G∈Δ(L) \end{matrix} a_{G}f̃_{G},

such that f̃_{F} − ∑\begin{matrix}G<_{L}F \\ G∈Δ(L) \end{matrix} a_{G}f̃_{G} ∈ Q̃.

Proof. Since F ∈ Δ(Q), and hence F ∉ Δ(L), we have

f̃_{F} − ∑_{G<_{L}F} a_{G}f̃_{G} ∈ I_{L} = Q̃ (4)

for some a_{G}. We may iterate this process on the f̃_{G}’s for which G ∉ Δ(L), replacing them by lexicographically earlier linear combinations that are equal modulo I_{L} = Q̃ until every G in equation (4) is in Δ(L). This eventually terminates, since lexicographic order is a total order. (In Gröbner basis theory, this procedure is known as finding the normal form [AL, Definition 2.1.3].)

To show these a_{G} are unique, assume that also

f̃_{F} − ∑_{\begin{matrix}G<_{L}F \\ G∈Δ(L) \end{matrix}} b_{G}f̃_{G} ∈ Q̃. (5)

Then by subtracting equation (5) from equation (4), we get

∑_{\begin{matrix}G<_{L}F \\ G∈Δ(L) \end{matrix}}(b_{G} − a_{G})f̃_{G} ∈ Q̃. (6)

If any b_{G} − a_{G} in equation (6) is non-zero, let G_{0} index the lexicographically last of these; then

(a_{G_{0}} − b_{G_{0}})f̃_{G_{0}} − ∑_{\begin{matrix}G<_{L}G_{0} \\ G∈Δ(L) \end{matrix}}(b_{G} − a_{G})f̃_{G} ∈ Q̃,

and

f̃_{G_{0}} − ∑_{\begin{matrix}G<_{L}G_{0} \\ G∈Δ(L) \end{matrix}} (\frac{b_{G} − a_{G}}{a_{G_{0}} − b_{G_{0}}} ) f̃_{G} ∈ Q̃,

which contradicts G_{0} ∈ Δ(L).

Definition. By Lemma 4.1, we may define, for any F ∈ Δ(Q), γ̃_{F} supported on Δ(L) such that f̃_{F} − γ̃_{F} ∈ Q̃.

Lemma 4.2. {f̃_{F} − γ̃_{F}: F ∈ Δ(Q)} is a basis of Q̃.

Proof. We first show that {f̃_{F} − γ̃_{F}: F ∈ Δ(Q)} is linearly independent. Assume otherwise;

∑_{F ∈Δ(Q)} b_{F} (f̃_{F} − γ̃_{F}) = 0, (7)

where b_{F_{0}} ≠ 0 for some F_{0} ∈ Δ(Q). When expanding the sum on the left-hand side of equation (7) in the {f̃_{F}: F ∈ Δ(K)} basis, the coefficient of f̃_{F_{0}} will be b_{F_{0}} ≠ 0, since the γ̃_{F} are all supported on Δ(L), and so cannot cancel f̃_{F_{0}}. So {f̃_{F} −γ̃_{F}: F ∈ Δ(Q)} is a set of |Δ(Q)| linearly independent vectors in Q̃.

On the other hand, Q̃ is a |K − L| = |Δ(Q)|-dimensional vector space, so {f̃_{F} − γ̃_{F}: F ∈ Δ(Q)} must be a basis.

Now we see how Q̃ can help compute homology and relative homology. We adopt the shorthand

δ^{−1}Q̃ = {x̃ ∈ Λ[K]: δx̃ ∈ Q̃}.

Lemma 4.3. For any pair of simplicial complexes L ⊆ K,

(a) β_{j}(L) = dim((δ^{−1}Q̃)/(im δ + Q̃))_{j}; and
(b) β_{j}(K, L) = dim((ker δ ∩ Q̃)/(δQ̃))_{j}.

Proof. This is [Du, Lemmas 2 and 4], where the notation Λ[Σ] was used in place of Q̃.

Lemma 4.3(b) suggests that in order to compute β_{j}(K, L), we examine ker δ ∩ Q̃ and δQ̃. However, im δ ∩ Q̃ turns out to be easier to handle than ker δ ∩ Q̃. The next two lemmas compare im δ ∩ Q̃ and δQ̃ to subspaces of Q̃ indexed by combinatorially defined sets of Δ(Q). These two comparisons will combine to prove the key inequality in the proof of Theorem 5.2.

Lemma 4.4. im δ ∩ Q̃ ⊆ span{f̃_{1 ˙∪F} − γ̃_{1 ˙∪F}: 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)}.

Proof. Let x̃ ∈ im δ ∩ Q̃. By Lemma 4.2, we can write

x̃ = ∑_{G∈Δ(Q)} a_{G}(f̃_{G} − γ̃_{G}) (8)

uniquely, since x̃ ∈ Q̃. Similarly, by [BK1, equation (3.5)], we can also write

x̃ = ∑_{\begin{matrix}1∉F \\ 1 ˙∪F ∈Δ(K) \end{matrix}} b_{F} f̃_{1 ˙∪F} (9)

uniquely, since x̃ ∈ im δ. Now, by definition, the support of γ̃_{G} is entirely on Δ(L). Of course, the support of x̃ in Δ(Q) must be the same in equations (8) and (9), so we must be able to write every G ∈ Δ(Q) such that a_{G} ≠ 0 as G = 1 ˙∪ F for some F. Therefore, equation (8) can be rewritten as

x̃ = ∑_{\begin{matrix}1∉F \\ 1 ˙∪F ∈Δ(Q) \end{matrix}} a_{1 ˙∪F} (f̃_{1 ˙∪F} − γ̃_{1 ˙∪F}),

implying the lemma.

Lemma 4.5. There is a subspace Q̃′ of Q̃ such that

dim δQ̃′ = |{F ∈ Δ(Q): 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)}|.

Proof. Let Q̃′ = span{f̃_{F} − γ̃_{F}: F ∈ Δ(Q), 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)}. First note that by definition of γ̃_{F} (and F ∈ Δ(Q)), each f̃_{F} − γ̃_{F} ∈ Q̃, so Q̃′ is a subspace of Q̃. Clearly, we only need to show that {δ(f̃_{F} − γ̃_{F}): F ∈ Δ(Q), 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)} is linearly independent.

By definition of γ̃_{F} and Lemma 4.1, we may write each

f̃_{F} − γ̃_{F} = f̃_{F} − ∑_{\begin{matrix}G<_{L}F \\ G∈Δ(L) \end{matrix}} b_{F,G}f̃_{G}

for some b_{F,G}’s. Furthermore, we are assuming 1 ˙∪ F ∈ Δ(Q) for each F, so 1 ˙∪ F ∈ Δ(K), and thus δf̃_{F} = f̃_{1 ˙∪F}. For each G <_{L} F, if 1 ∈ G, then δf̃_{G} = 0; otherwise 1 ˙∪ G <_{L} 1 ˙∪ F ∈ Δ(K), so 1 ˙∪ G ∈ Δ(K), and δf̃_{G} = f̃_{1 ˙∪G}. Therefore

δ(f̃_{F} − γ̃_{F}) = f̃_{1 ˙∪F} − ∑_{\begin{matrix}G<_{L}F \\ 1∉G, G∈Δ(L) \end{matrix}} b_{F,G}f̃_{1 ˙∪G}.

To show that {δ(f̃_{F} − γ̃_{F}): F ∈ Δ(Q), 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)} is linearly independent, assume

0 = ∑_{\begin{matrix}F ∈Δ(Q) \\ 1∉F, 1 ˙∪F ∈Δ(Q) \end{matrix}} c_{F} (f̃_{1 ˙∪F} − ∑_{\begin{matrix}G<_{L}F \\ 1∉G, G∈Δ(L) \end{matrix}} b_{F,G}f̃_{1 ˙∪G}). (10)

Now, f_{1 ˙∪G}’s appearing in equation (10) all satisfy G ∈ Δ(L), while all the f̃_{1 ˙∪F} ’s satisfy F ∈ Δ(Q), so there is no cancellation between the f̃_{1 ˙∪G}’s and the f̃_{1 ˙∪F} ’s. But all the f̃_{1 ˙∪F} ’s are distinct members of the {f̃_{H}: H ∈ Δ(K)} basis, so there is no cancellation among the f̃_{1 ˙∪F} ’s. Therefore all the c_{F} ’s must be zero, and the δ(f̃_{F} − γ̃_{F})’s are linearly independent.

5. Proof of main theorem

We start with an easy lemma.

Lemma 5.1. If I, J, and K are subspaces of a vector space and I ⊆ K, then

dim(K/I) = dim((K ∩ J)/(I ∩ J)) + dim((K + J)/(I + J)).

Proof. Simply expand the right-hand side as

(dim(K ∩ J) − dim(I ∩ J)) + ((dim K + dim J − dim(K ∩ J)) − (dim I + dim J − dim(I ∩ J)))

by the standard vector space argument dim(A + B) = dim A + dim B − dim(A ∩ B), applied twice. This expression then easily simplifies to dim K − dim I = dim(K/I).

Theorem 5.2. For any pair of simplicial complexes L ⊆ K,

β_{j}(K, L) ≤ β_{j}(Δ(K), Δ(L))

for all j.

Proof. Because Δ(K) and Δ(L) are shifted, and therefore near-cones with apex 1, we may use equations (1) and (2) to compute the homology of Δ(K), Δ(L), and (Δ(K), Δ(L)). The sets in these equations overlap in a nice way. In particular, if we let

C_{KQ} = {F ∈ Δ(Q): 1 ∉ F, 1 ˙∪ F ∉ Δ(K)},
C′_{LQ} = {G ∈ Δ(Q): 1 ∈ G, G − 1 ∈ Δ(L)},
C_{LQ} = {F ∈ Δ(L): 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)}, and
C_{KL} = {F ∈ Δ(L): 1 ∉ F, 1 ˙∪ F ∉ Δ(K)},

then it is not hard to see, from equation (1), that

β_{j}(Δ(K)) = |(C_{KQ})_{j}| + |(C_{KL})_{j}|,
β_{j}(Δ(L)) = |(C_{LQ})_{j}| + |(C_{KL})_{j}|,

and, from equation (2), that

β_{j}(Δ(K), Δ(L)) = |(C_{KQ})_{j}| + |(C′_{LQ})_{j}|.

(We name these sets “C” because they are combinatorial.) An easy bijection (F ↔ 1 ˙∪ F = G) shows that

|(C_{LQ})_{j}| = |(C′_{LQ})_{j+1}|.

Continuing the analogy begun at the end of Section 2 between formulas for homology of near-cones and the long exact sequence (3), C_{KQ} corresponds to im π_{∗}, C_{LQ} and C′_{LQ} correspond to im ∂_{∗}, and C_{KL} corresponds to im i_{∗}.

We can find “corresponding” subspaces in Λ[K]; define

A_{KQ} = (ker δ ∩ Q̃)/(im δ ∩ Q̃),
A′_{LQ} = (im δ ∩ Q̃)/(δQ̃),
A_{LQ} = (δ^{−1}Q̃)/(ker δ + Q̃), and
A_{KL} = (ker δ + Q̃)/(im δ + Q̃).

(We name these spaces “A” because they are algebraic.) Then by Lemma 5.1,

β_{j}(K) = dim(A_{KQ})_{j} + dim(A_{KL})_{j};

by Lemma 4.3,

β_{j}(L) = dim(A_{LQ})_{j} + dim(A_{KL})_{j}, and
β_{j}(K, L) = dim(A_{KQ})_{j} + dim(A′_{LQ})_{j};

and, by [Du, Lemma 5],

(A_{LQ})_{j} ≅ (A′_{LQ})_{j+1}.

We will show how the dimension of each A subspace compares with the cardinality of the corresponding C set with the same subscript. Because algebraic shifting preserves homology,

(11)  dim(A_{LQ})_{j} + dim(A_{KL})_{j} = β_{j}(L) = β_{j}(Δ(L)) = |(C_{LQ})_{j}| + |(C_{KL})_{j}|

and

(12)  dim(A_{KQ})_{j} + dim(A_{KL})_{j} = β_{j}(K) = β_{j}(Δ(K)) = |(C_{KQ})_{j}| + |(C_{KL})_{j}|.

By Lemma 4.4,

dim(im δ ∩ Q̃)_{j+1} ≤ |{F ∈ Δ(K)_{j}: 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)}|,

and by Lemma 4.5,

dim(δQ̃)_{j+1} ≥ dim(δQ̃′)_{j+1}
= |{F ∈ Δ(Q)_{j}: 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)}|.

(The index shift, of j + 1 to j, in the above inequalities arises because the (j + 1)- dimensional basis elements for im δ ∩ Q̃ and δQ̃′ are the (j + 1)-dimensional elements f̃_{1 ˙∪F} −γ̃_{1 ˙∪F} and δ(f̃_{F} −γ̃_{F}), respectively, each of which is (j +1)-dimensional precisely when F is j-dimensional.) Since Δ(L) is the complement of Δ(Q) with respect to Δ(K), then,

dim(A′_{LQ})_{j+1} = dim((im δ ∩ Q̃)/(δQ̃))_{j+1} = dim(im δ ∩ Q̃)_{j+1} − dim(δQ̃)_{j+1}
≤ |{F ∈ Δ(L)_{j}: 1 ∉ F, 1 ˙∪ F ∈ Δ(Q)}|
= |(C_{LQ})_{j}|,

and so

dim(A_{LQ})_{j} = dim(A′_{LQ})_{j+1} ≤ |(C_{LQ})_{j}| = |(C′_{LQ})_{j+1}|

Equation (11) then implies

dim(A_{KL})_{j} ≥ |(C_{KL})_{j}|,

so by equation (12),

dim(A_{KQ})_{j} ≤ |(C_{KQ})_{j}|,

and so finally

β_{j}(K, L) = dim(A_{KQ})_{j} + dim(A′_{LQ})_{j} ≤ |(C_{KQ})_{j}| + |(C′_{LQ})_{j}| = β_{j}(Δ(K), Δ(L)).

Acknowledgements. I gratefully acknowledge help from conversations with Keith Pardue, Frank Sottile, and Eric Babson.

References

[AL] W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics 3, American Mathematical Society, Providence, RI, 1994.

[AHH] A. Aramova, J. Herzog, T. Hibi, “Gotzmann theorems for exterior algebras and combinatorics,” J. Alg. 191 (1997), 174–211.

[Bi] A. Bigatti, “Upper bounds for the Betti numbers of a given Hilbert function,” Comm. Alg. 21 (1993), 2317–2334.

[BK1] A. Björner and G. Kalai, “An extended Euler-Poincaré theorem,” Acta Math. 161 (1988), 279–303.

[BK2] A. Björner and G. Kalai, “On f-vectors and homology,” in Combinatorial Mathematics: Proceedings of the Third International Conference (G. Bloom, R. Graham, J. Malkevitch, eds.); Ann. N. Y. Acad. Sci. 555 (1989), 63–80.

[Du] A. Duval, “On f-vectors and relative homology,” J. Alg. Comb., to appear.

[Ei] D. Eisenbud, Commutative Algebra with a View Towards Algebraic Geometry, Spinger-Verlag, New York, 1995.

[HT] J. Herzog and N. Terai, “Stable properties of algebraic shifting,” preprint, 1998.

[Hu1] H. Hulett, Maximum Betti Numbers for a Given Hilbert Function, Ph. D. thesis, University of Illinois at Urbana-Champaign, 1993.

[Hu2] H. Hulett, “Maximum Betti numbers for a given Hilbert function,” Comm. Alg. 21 (1993), 2335–2350.

[Ka1] G. Kalai, “Characterization of f-vectors of families of convex sets in R^{d}, Part I: Necessity of Eckhoff’s conditions,” Israel J. Math. 48 (1984), 175–195.

[Ka2] G. Kalai, Algebraic Shifting, unpublished manuscript (July 1993 version).

[Mu] J. Munkres, Elements of Algebraic Topology, Benjamin/Cummings, Menlo Park, CA, 1984.

[St1] R. Stanley, “Generalized h-vectors, intersection cohomology of toric varieties, and related results,” in Commutative Algebra and Combinatorics (M. Nagata and H. Matsumura, eds.), Advanced Studies in Pure Mathematics 11, Kinokuniya, Tokyo, and North-Holland, Amsterdam/New York, 1987, 187–213.

[St2] R. Stanley, Combinatorics and Commutative Algebra, 2nd ed., Birkhäuser, Boston, 1996.

University of Texas at El Paso, Department of Mathematical Sciences, El Paso, TX 79968-0514

  E-mail address: artduval@math.utep.edu