On the Betti Numbers of Chessboard Complexes

Joel Friedman^{∗}  Phil Hanlon^{†}

May 14, 1997

Abstract

In this paper we study the Betti numbers of a type of simplicial complex known as a chessboard complex. We obtain a formula for their Betti numbers as a sum of terms involving partitions. This formula allows us to determine which is the first nonvanishing Betti number (aside from the 0-th Betti number). We can therefore settle certain cases of a conjecture of Björner, Lovász, Vrećica, and Z̆ivaljević in [BLVZ̆94]. Our formula also shows that all eigenvalues of the Laplacians of the simplicial complexes are integers, and it gives a formula (involving partitions) for the multiplicities of the eigenvalues.

1 Introduction

An admissible rook configuration on an m×n chessboard is a subset of squares of the chessboard such that no two squares lie in the same row or column. The collection of such configurations, C(m, n), is a simplicial complex (i.e. it is closed under taking subsets). These simplicial complexes arise in various settings (see [BLVZ̆94, Z̆V92, Gar79]), especially in some combinatorial geometry problems where understanding their connectivity^{1} was important. In [BLVZ̆94] it is proven that for any m, n, C(m, n) is (ν − 2)-connected, where ν = min(m, n, ⌊(m + n + 1)/3⌋). It was conjectured that C(m, n) is not (ν − 1)-connected.

∗Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, CANADA. jf@math.ubc.ca The author also wishes to thank the NSERC for supporting this research in part.

†Department of Mathematics, University of Michigan, Ann Arbor, MI 48109–1003, U.S.A. hanlon@math.lsa.umich.edu Work partially supported by the NSF.

It is the above conjecture and the observations in [Fri95] which motivate this paper. In [Fri95] the above conjecture was verified in a few cases by computer, and it was empirically discovered that the eigenvalues of the Laplacians of the chessboard complexes are integers. In this paper we give a proof of this fact, a formula for the multiplicity of each eigenvalue of the Laplacian (including, therefore, a formula for each Betti number), and we determine exactly which Betti numbers vanish. This verifies the conjecture in [BLVZ̆94] in certain cases (including some new ones), and shows that in the other cases if the conjecture holds it is due to torsion in the relevant homology group. We explain this paragraph in detail below.

We claim that the connectivity conjecture in [BLVZ̆94] amounts to:

Conjecture 1.1 (Björner, Lovász, Vrećica, and Z̆ivaljević ) For any positive m, n (except m = n = 1) we have H_{ν−1}(X) ≠ 0 (or ≠ Z if ν = 1). where X = C(m, n) and

ν = min(m, n, ⌊(m + n + 1)/3⌋).

Indeed, for ν ≤ 2 the connectivity conjecture was verified in [BLVZ̆94], and our conjecture also hold by the calculations there^{2}. Furthermore, for ν ≥ 3 we already know that C(m, n) is (ν − 2)-connected, and so C(m, n) is connected and π_{1}(C(m, n)) is trivial; by the Hurewicz Theorem (see [Spa66], chapter 7, section 5) we have that C(m, n) is (ν − 2)-connected iff its homology groups from the first up to the (ν − 2)-th are trivial.

In [BLVZ̆94] conjecture 1.1 was proven in a number of cases: (1) m ≤ n with m ≤ 5, excepting C(4, 6), C(5, 7), C(5, 8), and (2) n ≥ 2m − 1. The conjecture was verified via computer in [Fri95] for C(4, 6) and C(5, 8), and was shown to hold for C(5, 7) unless a certain degeneracy holds in Laplacian eigenvalues.

1A topological space, X, is k-connected if for any 0 ≤ r ≤ k, any map from the rdimensional unit sphere to X can be extended to a map from the (r + 1)-dimensional unit ball to X; equivalently, π_{i}(X, x) are trivial for any x ∈ X and i = 0, …, r.

2Assuming m ≤ n, the ν = 1 case corresponds to either m = 1 (disjoint points) or m = n = 2 (a single edge), and ν = 2 corresponds to either m = 2 < n (a complete graph on more than two vertices) or m = 3 and n = 3, 4 for which the (ν − 1)-th Betti number does not vanish (see [BLVZ̆94], section 2).

Fix m, n, let ν be as before, and let X = C(m, n). Let b_{i}(X) denote the i-th Betti number of X; it equals the rank of H_{i}(X). In this paper we shall prove:

Theorem 1.2 b_{r−1} > 0 iff (n − r)(m − r) ≤ r and n > r or m > r.

This theorem verifies the conjecture for C(4, 6), C(5, 7), C(5, 8) (without computer aid). Moreover, this theorem easily shows that:

Theorem 1.3 For m ≤ n, we have b_{ν−1}(C(m, n)) > 0 iff n ≥ 2m − 4 or (m, n) = (6, 6), (7, 7), (8, 9).

So for such values of m ≤ n the conjecture is verified. For other values of m ≤ n, b_{ν−1}(C(m, n)) = 0; so if H_{ν−1}(C(m, n)) is non-trivial, it is due to torsion. Note that when m = n = 5, indeed H_{2}(C(5, 5)) = (Z/3Z) (see [BLVZ̆94]^{3}), so we can have a vanishing Betti number and nonvanishing homology group. We have not been able to extend our analysis to the homology groups, and to do so would be very important.

Our method is to study the combinatorial Laplacians of the C(m, n). The dimension of the kernel of the i-th Laplacian on C(m, n) is just b_{i}. It was empirically observed in [Fri95] that these Laplacians seem to have integral eigenvalues. We prove this observation, and give a formula for the multiplicity of the eigenvalues in terms of certain partitions. This is theorem 3.9.

We mention an interesting special case of theorem 3.9. For n = m+1, the m-th Laplacian on C(m, n) is just the Laplacian of the Cayley graph, G, on S_{n}, the symmetric group on n elements, with generators (1, n), (2, n), …, (n− 1, n). It follows that its first nonzero Laplacian eigenvalue, λ_{1}, of G is 1 (and that it occurs with multiplicity (n−1)(n−2)). This result was first proven in [FOW85], in a somewhat different fashion. This shows that G is, in a sense, a much better expander than H, the Cayley graph on S_{n} with generators (1, 2), (2, 3), …, (n − 1, n), which has λ_{1} = 2 − 2 cos(π/n) (see [Bac]). This obervation has led to [Fri], where it is shown that among all Cayley graphs on S_{n} with n − 1 generators which are transpositions, G has the largest λ_{1}.

3In [BLVZ̆94] the homology appears as (Z/3Z)^{4}, but Vic Reiner informed us that he and Jack Eagon and Joel Roberts have noted this error, found the above to be correct, and contacted the authors in [BLVZ̆94], who concur with them.

We finish this section by outlining the rest of the paper. In section 2 we review Hodge theory and introduce some notation. In section 3 we prove theorem 3.9, the main theorem in this paper, which gives a formula for the multiplicity of the eigenvalues of the Laplacians in terms of certain partitions via the representation theory of the symmetric group. In section 4 we analyze this formula to find the smallest eigenvalue of the Laplacians, thus determining when the Betti numbers vanish. In section 5 we determine precisely for which m, n we have b_{ν−1} ≠ 0.

2 Hodge Theory and the Laplacian

To compute the Betti numbers we will use the combinatorial Laplacians (see [Hod41, Eck45, Dod76, DP76]). These Laplacians are most easily described via Hodge theory of Hodge [Hod41].

Fix an abstract simplicial complex, X, i.e. a collection of sets closed under taking subsets. By an i-face of X, we mean a subset of size i + 1. Recall that the Betti numbers, b_{i}, are the dimensions of the rational homology groups, H_{i} = ker(∂_{i})/im(∂_{i+1}) of the chain complex,

⋯ ⟶ C_{i+1} ⟶^{∂_{i+1}} C_{i} ⟶^{∂_{i}} C_{i−1} ⟶ ⋯ ⟶ C_{−1} = 0,  (1)

where C_{i} is the space of formal R-linear sums of oriented i-dimensional faces, i.e. oriented subsets of the abstract simplicial complex of size i + 1, and ∂_{i} is the boundary map (see [Mun84]), given by

∂_{i}(v_{j_{1}} ∧ ⋯ ∧ v_{j_{i+1}}) = ∑_{k=1}^{i+1}(−1)^{k+1}v_{j_{1}} ∧ ⋯ ∧ v_{j_{k−1}} ∧ v_{j_{k+1}} ∧ ⋯ ∧ v_{j_{i+1}}.

Hodge theory works for an arbitrary chain complex over R (or any field of characteristic 0, such as Q or C). Recall that a chain complex is a collection, C_{i}, of vector spaces, with maps ∂_{i}: C_{i} → C_{i−1}, as in equation 1, such that ∂_{i−1} ∘ ∂_{i} = 0 for all i. Endowing each C_{i} with an inner product, we get maps ∂_{i}^{∗}: C_{i−1} → C_{i} (i.e. the transpose of ∂_{i}), and thus a Laplacian, Δ_{i}: C_{i} → C_{i}, for each i, defined by

Δ_{i} = ∂_{i+1}∂_{i+1}^{∗} + ∂_{i}^{∗}∂_{i}.

For each i we define the set of harmonic i-forms to be

H_{i} = {c ∈ C_{i}|Δ_{i}c = 0}.

For chain complexes where each C_{i} is a finite dimensional R-vector space, Hodge theory involves only elementary linear algebra, and says:

Proposition 2.1 (Hodge theory) For each i we have H_{i} ≅ H_{i}, in that each member of H_{i} gives rise to a class in H_{i}, and each class in H_{i} contains a unique harmonic form in H_{i}.

Proof Follows easily from the facts that (1) A = ∂_{i}^{∗}∂_{i} and B = ∂_{i+1}∂_{i+1}^{∗} are positive semi-definite and commute, satisfying AB = BA = 0, and (2) imS = imS ∘ S^{∗} for any map of finite inner product spaces, S: V → W.

□

3 Laplacian Eigenvalues: A Formula

In this section we give a formula for the multiplicity of the eigenvalues of the Laplacian on chessboard complexes.

Let [1..n] denote {1, 2, …, n}, and let [1..n]^{(r)} denote the set of tuples I = (i_{1}, …, i_{r}) with i_{1}, …, i_{r} distinct integers in [1..n]. Let S_{t} denote the symmetric group on t elements which we take to be [1..t], and let S_{t_{1},...,t_{k}} = S_{t_{1}} × ⋯ × S_{t_{k}}. Then S_{n} acts on [1..n] in the obvious way, (σ, i) ↦ σ(i), and this gives rise to an S_{n} action on [1..n]^{(r)}. Also S_{r} acts on [1..n]^{(r)} in the obvious way, namely

τ(i_{1}, …, i_{r}) = (i_{τ(1)}, ⋯, i_{τ(r)}).

Let C[1..n]^{(r)} be the vector space of formal C-linear combinations of [1..n]^{(r)} elements; it becomes an S_{r,n}-module.

Fix m, n. Let V = C{z_{i,j}} with i ∈ [1..m] and j ∈ [1..n] be the vector space of formal C-linear combinations of the z_{ij}’s. Clearly, for X = C(m, n) we have

C_{r−1} = Span ⟨z_{IJ} = z_{i_{1}j_{1}} ∧ ⋯ ∧ z_{i_{r}j_{r}} | I ∈ [1..m]^{(r)}, J ∈ [1..n]^{(r)}⟩ ,

viewed as a subspace of ⋀^{r} V, and we have ∂_{r−1} is given by extending by linearity the map:

∂_{r−1}(z_{IJ}) = ∑_{k=1}^{r}(−1)^{k+1}z_{i_{1}j_{1}} ∧ ⋯ ∧ z_{i_{k−1}j_{k−1}} ∧ z_{i_{k+1}j_{k+1}} ∧ ⋯ ∧ z_{i_{r}j_{r}}.

We make V into an inner product space by making {z_{i,j}} orthonormal; this induces the inner product on ⋀^{r} V where {z_{IJ}} are orthonormal. This determines

∂_{r}^{∗}(z_{IJ}) = ∑_{α∉I, β∉J} z_{αβ} ∧ z_{IJ}

and thereby determines the Laplacians.

The following proposition follows easily:

Proposition 3.1 For any r we have:

Δ_{r−1} = (r + (n − r)(m − r))I + A_{r−1} + B_{r−1},

where I is the identity,

A_{r−1}(z_{IJ}) = ∑_{k=1}^{r} ∑_{ℓ∉I} z_{i_{1}j_{1}} ∧ ⋯ ∧ z_{ℓj_{k}} ∧ ⋯ ∧ z_{i_{r}j_{r}},

and

B_{r−1}(z_{IJ}) = ∑_{k=1}^{r} ∑_{ℓ∉J} z_{i_{1}j_{1}} ∧ ⋯ ∧ z_{i_{k}ℓ} ∧ ⋯ ∧ z_{i_{r}j_{r}}.

So to understand Δ_{r−1} it sufficies to understand K_{r−1} = A_{r−1} + B_{r−1}.

We now describe a method to determine the eigenvalues and eigenspaces of K_{r−1}. Since S_{r,n} acts on the I ∈ [1..n]^{(r)}, and since S_{r,m} acts on the J ∈ [1..m]^{(r)}, we have a natural S_{r,n,r,m} action on the z_{IJ}’s and therefore on C_{r−1}. Note that K_{r−1} commutes with this action; hence the eigenspaces we seek decompose into S_{r,n,r,m} irreducibles, and we will be able to understand them more easily this way.

First of all, it will be easier to study K_{r−1} and C_{r−1} by deriving them as the antisymmetric parts of a tensor product of spaces. So set

V_{r−1} = Span ⟨z^{IJ} = z_{i_{1}j_{1}} ⊗ ⋯ ⊗ z_{i_{r}j_{r}} | I ∈ [1..m]^{(r)}, J ∈ [1..n]^{(r)}⟩ ,

viewed as a subspace of V^{⊗r}. Let K_{r−1} = A_{r−1} + B_{r−1} act on V_{r−1} via

A_{r−1}(z^{IJ}) = ∑_{k=1}^{r} ∑_{ℓ∉I} z_{i_{1}j_{1}} ⊗ ⋯ ⊗ z_{ℓj_{k}} ⊗ ⋯ ⊗ z_{i_{r}j_{r}},

and

B_{r−1}(z^{IJ}) = ∑_{k=1}^{r} ∑_{ℓ∉J} z_{i_{1}j_{1}} ⊗ ⋯ ⊗ z_{i_{k}ℓ} ⊗ ⋯ ⊗ z_{i_{r}j_{r}}.

The natural S_{r,n,r,m} action on the z^{IJ}’s gives one on V_{r−1}.

Embedding S_{r} diagonally into S_{r,r} gives the S_{r} action on V_{r−1} which just permutes tensors. C_{r−1} can be viewed as the subspace of V_{r−1} of skew symmetric tensors, and clearly:

Proposition 3.2 The map π: V_{r−1} → V_{r−1} given by

π = \frac{1}{r!} ∑_{σ∈S_{r}} sgn(σ)σ  (2)

is a projection onto C_{r−1}. We have that π commutes with A_{r−1} and B_{r−1}, and A_{r−1}, B_{r−1} restricted to C_{r−1} are just A_{r−1}, B_{r−1}.

Now we seek to understand K_{r−1} acting on V_{r−1}. We start by observing that:

V_{r−1} ≅ C[1..n]^{(r)} ⊗ C[1..m]^{(r)}

as S_{r,n,r,m} modules.

Next we explain how K_{r−1} can be understood in terms of a certain conjugacy class sum. For an integer p we define T_{p} to be the element of CS_{p}

T_{p} = ∑_{1≤i<j≤p}(i, j).

It acts as a scalar multiplication by an integer on each irreducible of S_{p}, and the particular integer can be easily determined from the partition indexing the irreducible. On CS_{r,n} ≅ CS_{r} ⊗ CS_{n} we define the difference:

D_{r,n} = 1 ⊗ T_{n} − T_{r} ⊗ 1 − \binom{n − r}{2}1 ⊗ 1

Clearly the element D_{r,n} ⊗ 1 ∈ CS_{r,n} ⊗ CS_{r,m} = CS_{r,n,r,m} gives the same action on V_{r−1} as does A_{r−1}. Similarly 1 ⊗ D_{r,m}, interpreted accordingly, equals B_{r−1}. Since T_{p}’s actions on S_{p} irreducibles is, in a sense, understood, we will get a similar understanding of K_{r−1}’s action on V_{r−1} (and of K_{r−1}’s on C_{r−1}) as soon as we decompose V_{r−1} into S_{r,n,r,m} irreducibles.

We begin this decomposition by the following:

Theorem 3.3 As an S_{r,n} module we have that C[1..n]^{(r)} decomposes as:

C[1..n]^{(r)} ≅ ⨁_{λ⊢n, (n−r)⊆λ} S^{λ/(n−r)} ⊗ S^{λ}

We first explain this theorem. By λ ⊢ n we mean that λ is a partition of n. To each such partition, λ, there is an naturally associated irreducible representation S^{λ} of S_{n}. Partitions have a natural partial order^{4} ⊆. By (n − r) we mean the one element partition of n − r. For α ⊆ β there is natural “skew representation,” S^{β/α}, having the property that for each γ the multiplicity of S^{γ} in S^{β/α} is the Littlewood-Richardson coefficient c_{γ,α}^{β}; see [JK81, Mac95]. Proof First we notice that as S_{r,n}-modules,

C[1..n]^{(r)} ≅ ϵ ⊗CS_{n−r} CS_{n},

where ϵ is the trivial representation of S_{n−r}, and where the right-hand-side is viewed as an S_{r,n}-module as in [Han]. The theorem then follows from proposition 4.9 of [Han].

□

To finish our analysis it suffices to understand the action of T_{p} on S_{p} irreducibles, to understand the Littlewood-Richardson coefficients in our case, and to combine the results. To this end we have the standard results. From [Dia88] pages 36 and fact 2 on page 40 (and see [Mac95] page 118) we have

Lemma 3.4 If λ ⊢ p, then T_{p} acts on S^{λ} as a constant, C_{λ}, times the identity, where C_{λ} = ∑_{x∈λ} c_{x}, the sum being over the squares, x, in the Ferrers diagram of λ, and where c_{x} is the “content” of x, i.e. its horizontal coordinate minus its vertical coordinate.

Definition 3.5 Let α and β be partitions with α contained in β. We say that β/α is a horizontal strip if β can be obtained from α by adding at most one square in each column.

4There are many partial orders on partitions. The partial order α ⊆ β used here means that the Ferrers diagram of α fits into that of β; i.e. if α = (α_{1}, …) and β = (β_{1}, …), then α_{i} ≤ β_{i} for all i.

Note that in this definition we have identified a partition with its Ferrers diagram. We will continue to do so throughout this article.

From [Mac95] page 143 we have:

Lemma 3.6 c_{α,(n−r)}^{λ} is 1 or 0 according to whether or not λ/α is a horizontal strip.

We now make some simple conclusions:

Corollary 3.7 As an S_{r,n,r,m}-module, V_{r−1} splits as a direct sum of S^{α,λ,β,μ}, where

1. S^{α,λ,β,μ} = S^{α} ⊗ S^{λ} ⊗ S^{β} ⊗ S^{μ},

2. the sum is over all α, β ⊢ r, λ ⊢ n, and μ ⊢ m, such that c_{α,(n−r)}^{λ} = c_{β,(m−r)}^{μ} = 1, i.e. such that λ/α and μ/β are horizontal strips,

3. since the splitting is as S_{r,n,r,m}-modules, the actions of π and K_{r−1} factor through each direct summand, and

4. K_{r−1} acts as the identity times

C_{λ} + C_{μ} − C_{α} − C_{β} − \binom{n − r}{2} − \binom{m − r}{2}

on the summand S^{α,λ,β,μ} (if present).

Now consider π, as in equation 2, as an element of CS_{r,r}. We have:

Lemma 3.8 The image of π (π viewed as an element of CS_{r,r}) on S^{α} ⊗ S^{β} for α, β ⊢ r is {0} unless α = β′, i.e. α and β are conjugate partitions, in which case the image is one dimensional.

Proof The alternating representation, S^{1^{r}}, can be viewed as a (one dimensional) S_{r}-submodule, A, of CS_{r}. π, viewed as an element of CS_{r}, clearly acts as projection onto A. It follows that for λ ⊢ r we have π is the identity or 0 according to whether or not λ = 1^{r} (the partition (1, 1, …, 1)). So the action of π on S^{α} ⊗ S^{β} (viewed as an S_{r}-module) depends on how many copies of S^{1^{r}} lie inside of it (viewed as an S_{r}-module). Since S^{β′} = S^{β} ⊗ S^{1^{r}}, this number of copies is the same as the number of copies of the trivial representation inside of S^{α} ⊗ S^{β′}. Since all characters of S_{r} are real (see [JK81]), we have S^{β′} ≃ (S^{β′})^{∗}, and so S^{α} ⊗ S^{β′} ≃ Hom(S^{α}, S^{β′}) as representations, where g ∈ S_{r} acts on f ∈ Hom by taking it to the map u ↦ gf(g^{−1}u). So the S_{r} invariants of the above Hom are just those elements of Hom which are intertwining maps. By Schur’s Lemma the dimension of such maps is 1 or 0 depending on whether or not α = β′.

□

This lemma simplifies things, for clearly C_{α} = −C_{β} for α = β′.

We recall that f^{λ} = dim(S^{λ}) is a positive integer; it can be computed via the hook length formula (see [Mac95]).

We summarize our finding as follows:

Theorem 3.9 The eigenvalues of Δ_{r−1} on C_{r−1} are as follows: for every α ⊢ r, λ ⊢ n, and μ ⊢ m such that λ/α and μ/α′ are horizontal strips, we have an f^{λ}f^{μ}-dimensional eigenspace of eigenvalue

(r + (n − r)(m − r) − \binom{n − r}{2} − \binom{m − r}{2}) + C_{λ} + C_{μ}.

Corollary 3.10 All the eigenvalues of Δ_{r−1} on C(m, n) are integers.

4 The Betti Numbers

Now we apply theorem 3.9 to find out which Betti numbers vanish. Although the formula in theorem 3.9 is not quite explicit, it allows us to easily enough tell whether or not a 0 eigenvalue in Δ_{r−1} occurs.

Theorem 4.1 For X = C(m, n) we have b_{r−1} = 0 iff (m − r)(n − r) > r.

More generally, we can give a fairly simple formula for the multiplicity of the smallest eigenvalue of Δ_{r−1}, and the above theorem is a corollary. Our formula involves the following notion:

Definition 4.2 For α ⊢ r and integer n ≥ r, the minimally horizontally built partition of size n from α is the partition obtained by adding one square to α in each of the first n − r columns. We denote it α[n].

Note that of all horizontal strips β/α with α fixed and β ⊢ n, clearly β = α[n] has the minimum content.

Definition 4.3 Given non-negative integers a, b, we say that α is a, bsubrectangular if α is contained in the a × b rectangle. We say that α is a, b-super-rectangular if it contains the a × b rectangle and if no square of α lies past the a-th column and the b-th row simultaneously. By R_{a,b} and S_{a,b} we denote respectively the a, b-subrectangular and super-rectangular partitions.

We remark that S_{0,0} is empty and that if a > 0 or b > 0 (or both) then S_{a,b} contains one partition of size n for any n > 0.

Our main theorem is:

Theorem 4.4 For (m − r)(n − r) ≤ r we have

b_{r−1} = ∑_{α⊢r, α∈S_{n−r,m−r}} f^{α[n]}f^{α′[m]};

in this case b_{r−1} > 0 unless m = n = r (in which case S_{n−r,m−r} is empty and it is easily checked that Δ_{r−1} is r times the identity). For (m − r)(n − r) > r the smallest eigenvalue of Δ_{r−1} is (m−r)(n−r)−r (in particular b_{r−1} = 0), and its multiplicity is given by:

∑_{α⊢r, α∈R_{n−r,m−r}} f^{α[n]}f^{α′[m]}.

Proof Fix α ⊢ r, and let λ = α[n]. As mentioned before, clearly λ is the partition of least content such that λ/α is a horizontal strip and λ ⊢ n. Consider the “excess content” of λ with respect to α, i.e. the sum of the c_{x} with x ranging over the λ − α squares (which equals C_{λ} − C_{α}). Clearly the excess content is

\binom{n − r}{2} − r

if n − r ≥ col(α), where col(α) is the number of nonempty columns of α. Furthermore, when n − r < col(α), we have that the excess content is

\binom{n − r}{2} − r + E

where E is the number of squares of α in its last col(α) − (n − r) columns. Doing the same for α′ and μ = α′[m], we get an excess content of

\binom{m − r}{2} − r + F,

where F is the number of squares of α in its last row(α) − (m − r) rows (if this number is positive, and otherwise F = 0). Since C_{α} + C_{α′} = 0, we have that

C_{λ} + C_{ν} = \binom{n − r}{2} + \binom{m − r}{2} − 2r + E + F.

It follows that the smallest eigenvalue of Δ_{r−1} to which α contributes as in the formula in theorem 3.9 is

(n − r)(m − r) − r + E + F.  (3)

It follows that α contributes multiplicity f^{α[n]}f^{α′[m]} to the eigenvalue 0 iff r = (n−r)(m−r)+E +F, which will be the case iff r ≥ (n−r)(m−r) and α is (n−r), (m−r)-super-rectangular. Hence the formula for r ≥ (n−r)(m−r), the case m = n = r being special in that S_{n−r,m−r} is the empty set— in this case we easily check that Δ_{r−1} is r times the identity. For r < (n−r)(m−r), the minimum value of the expression in equation 3 is (n − r)(m − r) − r, and is achieved iff E = F = 0, i.e. for those α’s which are (n − r), (m − r)- subrectangular.

□

5 The Conjecture of Björner, Lovász, Vrećica, and Z̆ivaljević

Now we draw some conclusions about the Björner, Lovász, Vrećica, and Z̆ivaljević conjecture based on the formula in the last section. Recall, b_{r−1} > 0 iff (m−r)(n−r) ≤ r. So we can verify the conjecture when ν ≥ (m−ν)(n−ν). We may assume m ≤ n. When 2m − 1 ≤ n we have ν = m and, of course ν ≥ (m − ν)(n − ν) (also the conjecture was verified in [BLVZ̆94] in this case).

For 2m − 1 > n we have ν = ⌊(m + n + 1)/3⌋. So let n = 2m − 1 − c, assuming c ≥ 1. We have ν = m−⌈c/3⌉. If c = 1, 2, 3 we have ν = m−1 and (m − ν)(n − ν) = m − c so that ν ≥ (m − ν)(n − ν). We shall show that for c ≥ 4 there are only finitely many values of n, m for which ν ≥ (m−ν)(n−ν) holds.

For c ≥ 0 the condition ν ≥ (m − ν)(n − ν) amounts to

m − ⌈c/3⌉ ≥ ⌈c/3⌉(m + ⌈c/3⌉ − 1 − c),

which for c ≥ 4 is to say

m ≤ \frac{⌈c/3⌉(c − ⌈c/3⌉)}{⌈c/3⌉ − 1};

the condition m ≤ n amounts to m ≥ c + 1. Hence for c ≥ 4 the two conditions amount to:

c + 1 ≤ m ≤ \frac{⌈c/3⌉(c − ⌈c/3⌉)}{⌈c/3⌉ − 1}.

The cases c = 4, 5, 6 therefore give three (m, n) pairs, namely (6, 6), (7, 7), (8, 9). For c ≥ 7 we have ⌈c/3⌉ ≥ 3, and so

⌈c/3⌉(⌈c/3⌉ + 1) ≥ 3(⌈c/3⌉ + 1) > c + 1.

Hence

⌈c/3⌉ − (c + 1) > −⌈c/3⌉^{2},

and adding ⌈c/3⌉c to both sides yields:

(c + 1)(⌈c/3⌉ − 1) > ⌈c/3⌉(c − ⌈c/3⌉)

and so

c + 1 > \frac{⌈c/3⌉(c − ⌈c/3⌉)}{⌈c/3⌉ − 1}.

Hence for c ≥ 7 there are no possible values of m.

We summarize our findings:

Theorem 5.1 For m ≤ n and 2m − 4 ≤ n we have b_{ν−1}(X) > 0 where X = C(m, n) and ν = min(m, n, ⌊(m + n + 1)/3⌋). The same holds for (m, n) = (6, 6), (7, 7), (8, 9). In all other cases we have b_{ν−1}(X) = 0.

References

[Bac] Bacher. Valeur propre minimale du laplacien de Coxeter pour le group symétrique. Journal of Algebra, 167:460–472.

[BLVZ̆94] A. Björner, L. Lovász, S.T. Vrećica, and R.T. Z̆ivaljević. Chessboard complexes and matching complexes. J. London Math. Soc., 49:25–39, 1994.

[Dia88] P. Diaconis. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, 1988.

[Dod76] Jozef Dodziuk. Finite-difference approach to the Hodge theory of harmonic forms. American Journal of Mathematics, 98:79–104, 1976.

[DP76] J. Dodziuk and V.K. Patodi. Riemannian structures and triangulations of manifolds. J. of the Indian Math. Soc., 40:1–52, 1976.

[Eck45] B. Eckmann. Harmonische Funktionen und Randwertaufgaben in einem Komplex. Commentarii Math. Helvetici, 17:240–245, 1944– 45.

[FOW85] L. Flatto, A.M. Odlyzko, and D.B. Wales. Random shuffles and group representations. Annals of Probability, 13:154–178, 1985.

[Fri] J. Friedman. On Cayley graphs of S_{n} generated by transpositions. To appear.

[Fri95] J. Friedman. Computing Betti numbers via combinatorial Laplacians. November 1995. To appear in STOC 1996.

[Gar79] P.F. Garst. Some Cohen-Macaulay complexes and group actions. Ph.D. Thesis, 1979. University of Madison, Wisconsin.

[Han] Phil Hanlon. A random walk on the rook placements on a Ferrer’s board. Electronic Journal of Combinatorics. To appear.

[Hod41] W.V.D. Hodge. The Theory and Applications of Harmonic Integrals. Cambridge University Press, 1941.

[JK81] G. James and A. Kerber. The Representation Theory of the Symmetric Group. Addison-Welsey, 1981.

[Mac95] I.G. Macdonald. Symmetric Functions and Hall Polynomials. Oxford University Press, Second edition, 1995.

[Mun84] James R. Munkres. Elements of Algebraic Topology. Benjamin/Cummings, 1984.

[Spa66] Edwin H. Spanier. Algebraic Topology. McGraw-Hill, 1966. (also available from Springer-Verlag).

[Z̆V92] R.T. Z̆ivaljević and S.T. Vrećica. The colored Tverberg’s problem and complexes of injective functions. J. Combin. Theory Ser. A, 61:309–318, 1992.