SHIFTED SIMPLICIAL COMPLEXES ARE LAPLACIAN INTEGRAL

ART M. DUVAL AND VICTOR REINER

Abstract. We show that the combinatorial Laplace operators associated to the boundary maps in a shifted simplicial complex have all integer spectra. We give a simple combinatorial interpretation for the spectra in terms of vertex degree sequences, generalizing a theorem of Merris for graphs.

We also conjecture a majorization inequality for the spectra of these Laplace operators in an arbitrary simplicial complex, with equality achieved if and only if the complex is shifted. This generalizes a conjecture of Grone and Merris for graphs.

1. Introduction

This paper is about spectra of combinatorial Laplace operators associated to simplicial complexes. We begin with some history.

The theory of graph Laplacians goes back to Kirchhoff [22] in his study of electrical networks, and his celebrated matrix-tree theorem (see e.g. [21]). The spectra of graph Laplacians gained attention in the late 1960’s through the independent work of Anderson and Morley [2], Fiedler [13], and Kelmans (see references in [20]). For comprehensive bibliographies on graph Laplacians see [27] and [7], and for other aspects of spectra of graphs see [9]. The Laplace operator L(G) for a graph G is defined as follows: L(G) = ∂∂^{T}, where ∂ is the vertex-edge incidence matrix having

• rows indexed by the vertices of G,

• columns indexed by the edges of G,

• the column corresponding to a particular edge containing a +1 and −1 in

the rows that corresponding to that edge’s endpoints. Note that this map ∂ coincides with the boundary map ∂_{1} when one considers the graph G as a 1-dimensional cell complex, with a choice of orientation of each of its edges. The relation of the spectrum of L(G) (and of its close relative ∂^{T} ∂ sometimes called the edge-Laplacian) to the topology and combinatorics of G is well-studied, although much remains to be understood.

One can generalize L(G) to higher dimensions by considering graphs (without self-loops or multiple edges) as simplicial complexes (see e.g. [28]). A simplicial complex K has associated to it chain groups C_{i}(K) and boundary maps ∂_{i}: C_{i}(K) → C_{i−1}(K) satisfying ∂_{i+1}∂_{i} = 0, which are used to define and compute its homology groups H_{i}(K) := ker ∂_{i}/ im ∂_{i+1}. The maps ∂_{i}∂_{i}^{T} and ∂_{i}^{T} ∂_{i} naturally arise in a finite-dimensional version of Hodge theory first explicitly stated by Eckmann [11]. He observed that when working with real coefficients, so that C_{i}(K) is an ℝ-vector space, the operator

Date: May 3, 2000 and, in revised form, August 10, 2000.

2000 Mathematics Subject Classification. Primary 15A42; Secondary 05C65, 05C50, 05E99.

Key words and phrases. Laplace operator, Laplacian, simplicial complex, spectra.

Second author partially supported by a Sloan Foundation Fellowship, and NSF grant DMS-9877047.

L_{i} = ∂_{i+1}∂_{i+1}^{T} + ∂_{i}^{T} ∂_{i}

has the property that its kernel ker L_{i} (the harmonic i-chains) span a subspace isomorphic to H_{i}(K) (see Theorem 3.3 below). In other words, H_{i}(K) is isomorphic to the 0-eigenspace of L_{i}. Based on this fact, Friedman [15] proposed that approximating H_{i}(K) with real coefficients could be done relatively efficiently, compared to the usual method of finding the ranks of the maps ∂_{i} and ∂_{i+1}, by approximating the entire eigenspace decomposition of L_{i} using fast methods applicable to symmetric matrices.

In doing specific examples of such computations, Friedman noticed that certain combinatorially interesting families of complexes, the chessboard complexes, appeared to have L_{i} with all integer spectra, which he and Hanlon [16] later were able to prove. This motivated further work proving that other well-known families of simplicial complexes have L_{i} with integer spectra, specifically the matching complexes [10] and matroid complexes [23].

We should mention that Chung [6] also considered a variant of the maps L_{i} (see Remark 3.4 below), and that the maps ∂_{i}∂_{i}^{T} arose in a beautiful generalization of Kirchhoff’s matrix-tree theorem to higher-dimensional simplicial complexes by Kalai [21]; see also [1].

The current paper arose from two motivations. One was our suspicion that the family of shifted simplicial complexes might also have integer Laplacian spectra. These simplicial complexes arise, among other places, in work of Björner and Kalai [3] because they are extremal in a certain sense with respect to homology and face numbers. They turn out to be extremal in other ways (see Conjecture 1.2 and Section 9 below). Our main result confirms that shifted complexes indeed have integer Laplacian spectra, generalizing a result for degree-maximal or threshold graphs due originally to Kelmans (see [20, Corollary 4.1]). Kelmans’ result was rediscovered independently and elegantly reformulated by Merris [26, Theorem 2], and it is this formulation which we generalize.

The result is not phrased in terms of the spectra of the operators L_{i}, but rather in terms of the equivalent spectra of ∂_{i}∂_{i}^{T} (see Section 3 for the equivalence). It also turns out to be more convenient for this phrasing to consider not a shifted simplicial complex K, but rather a shifted k-family (or k-uniform hypergraph) K, which we think of as being the collection of (k − 1)-dimensional simplices in some shifted simplicial complex (Section 3 shows why it suffices to look at families instead of simplicial complexes). Theorem 1.1. For any shifted k-family K, let s = (s_{1} ≥ s_{2} ≥ …) denote the weakly decreasing rearrangement of the non-zero eigenvalues in the spectrum of ∂_{k−1}∂_{k−1}^{T}. Then we have

s = d^{T}

where here d^{T} denotes the conjugate partition to the degree sequence d of vertices with respect to the k-sets in K.

The proof of Theorem 1.1 is in Section 5.

Our second motivation was the hope that the spectra of shifted simplicial complexes might be extremal in some way that leads to inequalities for the spectra of all complexes. This led us to the following conjecture, generalizing a conjecture of Grone and Merris [19, Conjecture 2] for graphs. As with the above theorem, it is phrased in terms of ∂_{i}∂_{i}^{T} rather than L_{i}, and for k-families rather than simplicial complexes. Conjecture 1.2. For any k-family K, the spectrum s defined as in the previous theorem satisfies

s ⊴ d^{T}

with equality if and only if K is isomorphic to a shifted family. Here ⊴ denotes the majorization partial order, that is

s_{1} ≤ d_{1}^{T}
s_{1} + s_{2} ≤ d_{1}^{T} + d_{2}^{T}
s_{1} + s_{2} + s_{3} ≤ d_{1}^{T} + d_{2}^{T} + d_{3}^{T}
⋮

We think that the evidence for Conjecture 1.2 is quite strong, and is presented in Sections 6 and 7.

The paper is structured as follows.

Section 2 establishes some notation and terminology for simplicial complexes and number partitions.

Section 3 defines the various versions of the combinatorial Laplace operators that we will consider, and explains why their spectra all carry equivalent data in a certain sense. It also reviews and proves Eckmann’s finite-dimensional Hodge Theorem for the sake of completeness.

Section 4 collects various constructions one can apply to k-families or simplicial complexes (including a generalization of the operation of complementation for graphs, canonical Alexander duality, and simplicial joins), and describes how they affect the spectra. Most of these results are used either in the proof of Theorem 1.1 or in the evidence for Conjecture 1.2. In particular, Theorem 4.5, Corollary 4.7 and Theorem 4.10 appear to be new.

Section 5 proves Theorem 1.1.

Section 6 re-states Conjecture 1.2, and proves various partial results as evidence for it. In particular, it is shown that

• the first inequality s_{1} ≤ d_{1}^{T} in the conjectured majorization holds (Proposition 6.2),

• if the majorization inequality in the conjecture holds, then the second assertion about the case of equality follows (Proposition 6.4), and

• the conjecture is consistent with several of the constructions of Section 4

(Propositions 6.5 and 6.7). Section 7 provides further evidence for Conjecture 1.2 by sketching the proof of

the second inequality of the conjectured majorization for the case of graphs.

Section 8 proves some other easy bounds on the spectra that are analogous to ones known in the case of graphs.

Section 9 explores one of the other ways in which shifted k-families are extremal, in that they (properly) contain all k-families whose vertex degree sequences are maximal in majorization order (Proposition 9.3). This generalizes the case k = 2 considered by Merris [26], who refers to shifted graphs as degree-maximal graphs.

Section 10 compares the spectra of Laplace operators as a combinatorial invariant of shifted simplicial complexes with a better-known invariant: the h-triangle introduced by Björner and Wachs. In particular, for nonpure shifted complexes it is shown that neither of these invariants determines the other, except in low dimensions. For pure shifted complexes it is shown how the spectral data naturally refines the h-vector.

2. Notation for simplicial complexes and partitions

Let [n] denote the set {1, 2, …, n}. An abstract simplicial complex K on vertex set [n] is a collection of subsets of [n] (called faces or simplices) which is closed under inclusion, that is, F ∈ K and F′ ⊂ F implies F′ ∈ K. Note that we do not assume all of the singletons v for v ∈ [n] are faces of K, nor do we assume that the empty set ∅ is a face of K. In particular, there is a distinction between the empty complex K = ∅ and the complex K = {∅} which contains the empty set and no other faces. The cardinality of a face F is denoted |F |, and its dimension is |F | − 1. The dimension of the whole complex K is the maximum dimension of a face in K. A face F is a facet of complex K if it is maximal in K, i.e., dim F = dim K. A complex is pure if all of its facets have the same dimension. The set

K_{j} := {F ∈ K: dim K = j}

forms a family of (j+1)-subsets, or a (j+1)-family of subsets of [n], for short. Many of our results will have equivalent phrasings that are sometimes more convenient for k-families of subsets rather than simplicial complexes. The f-vector of K is the sequence

f(K) := (f_{−1}(K), f_{0}(K), f_{1}(K), …)

where f_{j}(K) := |K_{j}|.

We will need a notation for the degree of a vertex v in [n] with respect to the j-dimensional faces K_{j}, or with respect to some (j + 1)-family:

deg_{j}(K, v) := |{F ∈ K: dim F = j, v ∈ F }|.

More generally, we define for a k-family K on [n] and any set A ⊆ [n],

deg(K, A) := |{F ∈ K: A ⊆ F }|.

The j-degree sequence of a simplicial complex K on vertex set [n] is the weakly decreasing rearrangement d_{j}(K) of the sequence deg_{j}(K, 1), …, deg_{j}(K, n), which we will often regard as a number partition.

We next define shifted families and shifted simplicial complexes, which play a central role in the sequel. Definition 2.1. If F = {f_{1} < ⋯ < f_{j}} and G = {g_{1} < ⋯ < g_{j}} are j-subsets of integers, then F ≤_{P} G under the componentwise partial order if f_{p} ≤ g_{p} for all p.

A k-family K is shifted if F ≤_{P} G and G ∈ K together imply that F ∈ K. A simplicial complex K is shifted if K_{j} is shifted for every j.

Shifted complexes and shifting operations have been used extensively in extremal combinatorics, notably by Björner and Kalai to characterize f-vectors and Betti sequences of simplicial complexes [3].

A simple but important property of a shifted family K is that when v < w are two vertices of a shifted family K, then deg(K, v) ≥ deg(K, w); thus, if the vertices of K are numbered {1, …, n}, then

(2.1)  d(K) = (deg(K, 1), …, deg(K, n)).

In other words, the ordering of the degrees of the degree sequence of a shifted family is given by the linear ordering of its vertices.

In general, we will use the following notations for number partitions

λ = (λ_{1}, …, λ_{r})

where λ_{i} ∈ ℕ and λ_{1} ≥ … ≥ λ_{r} ≥ 0. The weight of λ is |λ| := ∑_{i} λ_{i}. The length ℓ(λ) is the number of non-zero parts λ_{i}. The trivial partition is the unique partition with no parts, i.e. having length and weight 0. We will often need to be careful about how many trailing zeroes occur in a partition λ (if any at all). We hope context will always make this clear, but to reduce ambiguities, we introduce the following definition. Definition 2.2. The equivalence relation λ ≗ μ means that λ and μ agree in the multiplicities of all of their non-zero parts, that is, they coincide except for possibly their number of zeroes. We also extend this notation in the obvious way to the case where λ, μ are any weakly decreasing sequences of nonnegative real numbers.

We will sometimes use the multiplicative notation λ = 1^{m_{1}}2^{m_{2}} ⋯ to mean that λ has m_{i} parts equal to i. The conjugate or transpose partition λ^{T} has parts

λ_{i}^{T} = |{j: λ_{j} ≥ i}|.

For example, we have 1^{m} = (m)^{T}. With these conventions, if K is a simplicial complex,

• the 0-degree sequence d_{0}(K) = 1^{f_{0}(K)},

• the 1-degree sequence d_{1}(K) is what is usually known (see e.g. [30]) as the degree sequence for the graph that is the 1-skeleton of K, and

• the j-degree sequence d_{j}(K) either for j = −1 or for j > dim K is always

the trivial partition with no parts. We will use the following two operations on partitions λ, μ:

• λ∪μ is the ≗-equivalence class whose non-zero parts are the multiset union of the non-zero parts of λ and μ, arranged in weakly decreasing order, and

• λ + μ has parts λ_{i} + μ_{i}, i.e. it is the sum of λ + μ as vectors. When λ = 1^{l_{1}}2^{l_{2}} ⋯ and μ = 1^{m_{1}}2^{m_{2}} ⋯ happen to satisfy m_{i} ≤ l_{i} for each i, we define their difference λ − μ by λ − μ = 1^{l_{1}−m_{1}}2^{l_{2}−m_{2}} · · ·.

The dominance or majorization partial ordering on partitions, and more generally, on weakly decreasing sequences of real numbers, plays an important role in what follows. For

\begin{aligned}λ & = (λ_{1}, …, λ_{r}) \\ μ & = (μ_{1}, …, μ_{s}) \end{aligned}

two weakly decreasing sequences of real numbers with ∑_{i=1}^{s} μ_{s} = ∑_{i=1}^{r} λ_{i}, we say that λ majorizes μ (written μ ⊴ λ) if

∑_{i=1}^{k} μ_{i} ≤ ∑_{i=1}^{k} λ_{i} for k ≤ min(r, s).

We also extend the notation λ ∪ μ to the setting of weakly decreasing sequences of real numbers, and similarly extend the difference notation λ − μ in the case where the multiplicity of each real number in μ is at most the same multiplicity in λ.

It is easy to check (see [24, §I.1, formulas (1.8, 1.11)]) that conjugation has the following properties with respect to the above operations on partitions and dominance order: Lemma 2.3. If λ and μ are two partitions, then

(1) (λ ∪ μ)^{T} = λ^{T} + μ^{T}; and

(2) (λ + μ)^{T} = λ^{T} ∪ μ^{T};

(3) μ ⊴ λ ⇔ λ^{T} ⊴ μ^{T} □

3. Defining spectra of Laplacians

Here we introduce the basic object of our study, the spectra of combinatorial Laplace operators on simplicial complexes.

Given an abstract simplicial complex K on vertex set [n], recall ([28, Chapter 1, §5, 8]) that for each i ≥ −1, the vector space C_{i}(K; ℝ) of (augmented) oriented simplicial i-chains on K with coefficients in ℝ has as ℝ-basis the set of symbols [v_{0}, …, v_{i}] where F = {v_{0}, …, v_{i}} is a face of K, and where v_{0} < … < v_{i} in the usual ordering on [n]. The simplicial boundary map

∂_{i}: C_{i}(K; ℝ) → C_{i−1}(K; ℝ)

is then defined ℝ-linearly by extending the following map on basis elements:

∂_{i}[v_{0}, …, v_{i}] = ∑_{j=0}^{i}(−1)^{j}[v_{0}, …, v̂_{j}, …, v_{i}].

After verifying that

(3.1)  ∂_{i}∂_{i+1} = 0

one can define the (reduced) homology group

H̃_{i}(K; ℝ) := ker ∂_{i}/ im ∂_{i+1}.

Endow C_{i}(K; ℝ) with a positive definite inner product ⟨·, ·⟩ that makes the above basis orthonormal. This allows one to identify the ℝ-dual space

C^{i}(K; ℝ) := Hom_{ℝ}(C_{i}(K; ℝ), ℝ) ≅ C_{i}(K; ℝ)

via this inner product. Under this identification, the coboundary map

δ_{i}: C^{i}(K; ℝ) → C^{i+1}(K; ℝ)

is simply the adjoint ∂_{i+1}^{∗} of the boundary map ∂_{i+1} with respect to this inner product. Definition 3.1. Define three operators C_{i}(K; ℝ) → C_{i}(K; ℝ) using these boundary and coboundary maps:

\begin{aligned}L′_{i} & := ∂_{i+1}∂_{i+1}^{∗} \\ L′′_{i} & := ∂_{i}^{∗}∂_{i} \\ L_{i} & := L′_{i} + L′′_{i} = ∂_{i+1}∂_{i+1}^{∗} + ∂_{i}^{∗}∂_{i} \end{aligned}

The operator L_{i} is usually called the i-dimensional Laplace operator of K. Its spectrum will be our main object of study.

We can be somewhat more explicit about the maps L′_{i}, L′′_{i} after introducing some notation. Given a set F ⊆ [n] with elements v_{0} < … < v_{i}, let [F] denote the oriented simplicial i-chain [v_{0}, …, v_{i}]. Given two sets F, F′ of the same cardinality, let

F △ F′ := (F \F′) ∪ (F′\F)

denote their symmetric difference. When |F △ F′| = 2, say F △ F′ = {i, j} with i < j, define

ϵ(F, F′) := (−1)^{|{k: i<k<j, k∈F ∩F′}|}.

Then we have for any i-dimensional face F of a simplicial complex K

(3.2)  L′_{i}[F] = deg(K_{i+1}, F)[F]  + ∑_{\begin{matrix}F′∈K_{i} \\ |F △F′|=2 \\ F′∪F ∈K_{i+1} \end{matrix}} −ϵ(F, F′)[F′],

(3.3)  L′′_{i}[F] = (i + 1)[F]  + ∑_{\begin{matrix}F′∈K_{i} \\ |F △F′|=2 \end{matrix}} ϵ(F, F′)[F′],

(3.4)  L_{i}[F] = ((i + 1) + deg(K_{i+1}, F))[F]  + ∑_{\begin{matrix}F′∈K_{i} \\ |F △F′|=2 \\ F′∪F ∉K_{i+1} \end{matrix}} ϵ(F, F′)[F′].

We collect here several facts about these operators L′_{i}, L′′_{i}, L_{i}. Firstly, since they have the form ϕ^{∗}ϕ for some ℝ-linear map ϕ, each of L′_{i}, L′′_{i} is self-adjoint and nonnegative definite, and hence so is their sum L_{i}. We define the spectra s′_{i}, s′′_{i}, s_{i}^{tot} of L′_{i}, L′′_{i}, L_{i} to be the weakly decreasing rearrangement of their (real, nonnegative) eigenvalues. As with number partitions, in some situations, we may be sloppy about the number of zeroes contained in these spectra, however this ambiguity will generally be resolved by explicitly stating what the total length of the spectrum is in each case.

As a special case, we have for any simplicial complex K that contains the empty face ∅,

(3.5)  s_{−1}^{tot} = s′_{−1} = (f_{0}(K))

and s_{i}^{tot} = s′_{i} = ∅ for i ≤ −2 or i > dim K. Remark 3.2. There are well-definedness issues for the above spectra, since the definition of the boundary map ∂_{i} involves a choice of ordering of the vertices in the simplicial complex, and also the matrix representing ∂_{i} involves and ordering of the sets which index its rows and columns. We should check that the various spectra will depend on K only up to isomorphism as a simplicial complex.

However, one can check that different orderings of vertices or of the sets indexing the rows and columns of the boundary map will only have the effect of replacing ∂_{i} by α_{i} ∘ ∂_{i} ∘ β_{i} for some operators α_{i}, β_{i} on C_{i}(K; ℝ), C_{i+1}(K, ℝ), respectively. These operators are represented by signed permutation matrices with respect to the bases of simplices, so that they are invertible and satisfy α_{i}^{∗} = α_{i}^{−1} and β_{i}^{∗} = β_{i}^{−1}. Consequently, this has the effect of conjugating L′_{i}(K), L′′_{i}(K) by α_{i}, β_{i}, respectively, which will not affect their spectra.

The combinatorial Laplace operators L_{i} for simplicial complexes (and cell complexes more generally) were introduced by Eckmann; see [14] for some history. He observed the following finite dimensional analogue of the Hodge theory for harmonic differential forms on a Riemannian manifold (see e.g. [15] for a proof).

Let (C_{·}, ∂_{·}) be a complex of ℝ-vector spaces, i.e. ∂_{i}: C_{i} → C_{i−1} is an ℝ-linear map and ∂_{i}∂_{i+1} = 0. Endow each C_{i} with a positive definite inner product, so that one can identify C_{i}^{∗} := Hom_{ℝ}(C_{i}, ℝ) ≅ C_{i}. This allows one to define as above the adjoint maps

∂_{i}^{∗}: C_{i−1} → C_{i}

and the Laplacians

L_{i} = ∂_{i}^{∗}∂_{i} + ∂_{i+1}∂_{i+1}^{∗}: C_{i} → C_{i}.

Theorem 3.3. There is an isomorphism of ℝ-vector spaces

H̃_{i}(C_{·}, ∂_{·}) := ker ∂_{i}/ im ∂_{i+1} ≅ ker L_{i}.

More precisely, there is an orthogonal direct sum decomposition of C_{i} with respect to the chosen inner product

C_{i} = im ∂_{i+1} ⊕ ker L_{i} ⊕ im ∂_{i}^{∗}

in which the first two summands comprise the i-cycles ker ∂_{i}, and the first summand comprises the i-boundaries. □

Note that even though s′_{i} is defined to be the spectrum of L′_{i} = ∂_{i+1}∂_{i+1}^{∗} which acts on C_{i}(K; ℝ), its non-zero parts (i.e. its ≗-equivalence class) depend entirely on the family K_{i+1} of (i + 1)-dimensional faces in K. This is because an i-dimensional face of K that does not lie in any (i + 1)-dimensional face of K is annihilated by ∂_{i+1}^{∗}, and hence gives rise to a 0-eigenspace of L′_{i}.

Similarly, the non-zero parts in the spectrum s′′_{i} of L′′_{i} depend only on the family K_{i}. When we wish to define these operators L′, L′′ and their spectra s′, s′′ for some k-family K, rather than a simplicial complex, we will denote them

L′(K), L′′(K), s′(K), s′′(K)

being careful to specify the space on which L′(K), L′′(K) act so as to fix the number of zero eigenvalues in their spectra. When working with a k-family K, the notation ∂_{K} will always refer to the boundary map ∂_{k−1} which acts on the (k−1)-dimensional chains in the simplicial complex generated by K.

It is well-known that the non-zero eigenvalues and multiplicities of ϕ^{∗}ϕ coincide with those of ϕϕ^{∗} (see e.g. [25, Chapter 9, A.1.a, p. 216]). Consequently, we have

s′′_{i} ≗ s′_{i−1}.

For this reason, we will sometimes use the simpler notation s to refer to the ≗- equivalence class of s′ and s′′ (as we did in the Introduction).

The fact that ∂_{i}∂_{i+1} = 0 immediately implies that

L′_{i} ∘ L′′_{i} = 0 = L′′_{i} ∘ L′_{i}.

Therefore, since L_{i} is the sum of two commuting positive semidefinite operators L′_{i}, L′′_{i} which annihilate each other, the non-zero part of its spectrum is the union of non-zero parts of their spectra, that is,

(3.6)

s_{i}^{tot} ≗ s′_{i} ∪ s′′_{i}  ≗ s′_{i} ∪ s′_{i−1}
s′_{i} ≗ s_{i}^{tot} − s′′_{i} ≗ s_{i}^{tot} − s′_{i−1}

As a consequence, the information carried in the three families of spectra

(s_{−1}^{tot}, s_{0}^{tot}, s_{1}^{tot}, …, s_{dim K}^{tot})
(s′_{−1}, s′_{0}, s′_{1}, …, s′_{dim K−1})
(s′′_{0}, s′′_{1}, s′′_{2}, …, s′′_{dim K})

are all equivalent, and we will feel free to phrase our results in terms of any of the three. Remark 3.4. In [6], Chung considers a notion of a Laplace operator for a k-uniform hypergraph, that is, for a k-family K, which is phrased slightly differently. She considers

∂_{i+1}∂_{i+1}^{∗} + ρ ∂_{i}^{∗}∂_{i}

where ρ is a certain constant that depends on the structure of K, but is independent of i. On the other hand, it is again clear for the same reasons as were just discussed that the family of spectra of these operators carries equivalent information to that in any of the three families of spectra listed above. Remark 3.5. Note that the spectrum s′′_{i} of ∂_{i}^{∗}∂_{i} carries the same information as the singular values of the boundary operator ∂_{i}, since these are by definition the nonnegative square roots of the entries in s′′_{i}. One can therefore consider the study of spectra of combinatorial Laplacians as the study of singular values of boundary operators.

4. Constructions and their effect on the spectra

In this section we describe some standard constructions of new simplicial complexes or k-families from old ones, and how they affect the Laplacian spectra.

The first two constructions are most easily described on k-families K, that is, K is a collection of k-element subsets of [n]. Let \binom{[n]}{k} denote the complete k-family consisting of all k-subsets of [n]. Definition 4.1. Define two new k-families derived from K by

\begin{aligned}K^{c} & := \binom{[n]}{k}\K = \{F ⊆ [n]: |F | = k, F ∉ K\} \\ K^{∗} & := \{[n]\F: F ∈ K\}. \end{aligned}

Note that • K^{c} is a k-family,

• K^{∗} is an (n − k)-family,

• both of these operations are involutive: (K^{c})^{c} = (K^{∗})^{∗} = K, and

• they commute with each other: K^{c∗} = K^{∗c}. It is our goal to describe the effect these operations have on the spectra s′, s′′ (and hence on their ≗-equivalence class, s).

For the purpose of studying K ↦ K^{∗}, regard L′′_{i} as acting on the |K|-dimensional ℝ-vector space C(K; ℝ) having basis {[F]}_{F ∈K}, and let ϕ: C(K; ℝ) → C(K^{∗}; ℝ) be the ℝ-linear isomorphism defined by

ϕ[F] = (−1)^{∑_{i∈F} i}[[n]\F].

Proposition 4.2. (cf. [23, Proposition 6]) For any k-family K of subsets of [n] we have

(4.1)  L′′(K) + ϕ^{−1}L′′(K^{∗})ϕ = n · id_{C(K;ℝ)}.

Proof. We check Equation (4.1) entry by entry. The ([F], [F′])-entry of L′′(K) is

|F |  if F = F′,
ϵ(F, F′) if F, F′ ∈ K, |F △ F′| = 2,
0  otherwise.

On the other hand, the ([F], [F′])-entry of ϕ^{−1}L′′(K^{∗})ϕ is

|[n]\F |  if F = F′,
(−1)^{∑_{i∈F} i+∑_{i∈F′} i}ϵ([n]\F, [n]\F′) if F, F′ ∈ K, |F △ F′| = 2,
0  otherwise.

It is easy to see from this that the diagonal ([F], [F])-entries in Equation (4.1) are correct. For the off-diagonal ([F], [F′])-entry, it suffices to show that

(4.2)  (−1)^{∑_{i∈F} i+∑_{i∈F′} i}ϵ(F, F′) = −ϵ([n]\F, [n]\F′)

whenever |F △ F′| = 2. To see this, let F △ F′ = {i, j}, and then it is easy to check that

(−1)^{∑_{i∈F} i + ∑_{i∈F′} i} = (−1)^{i+j}

and

ϵ(F, F′) ϵ([n]\F, [n]\F′) = (−1)^{j−i−1}

which gives the desired equality (4.2). □

We immediately deduce Theorem 4.3. In the situation of the previous proposition, the spectra

\begin{aligned}s′′(K) & = (s_{1} ≥ … ≥ s_{|K|}) \\ s′′(K^{∗}) & = (s_{1}^{∗} ≥ … ≥ s_{|K|}^{∗}) \end{aligned}

are related by

(4.3)  s_{i}^{∗} = n − s_{|K|+1−i}

for each i.

For the purposes of studying K ↦ K^{c}, given a k-family K of subsets of [n], regard L′(K) as acting on the \binom{n}{k−1}-dimensional ℝ-vector space C(\binom{[n]}{k−1}; ℝ) having basis \{[F]\}_{F ∈\binom{[n]}{k−1}}. In the case of graphs, the next proposition is well-known (see e.g. [13]) and trivial, but it is not so trivial in higher dimensions, however. Proposition 4.4. For any k-family K of subsets of [n] we have

(4.4)  L′(K) + L′(K^{c}) = L′ (\binom{[n]}{k})

and all three operators L′(K), L′(K^{c}), L′(\binom{[n]}{k}) pairwise commute.

Proof. Equation (4.4) is immediate from the description of L′ given in Equation (3.2) and the definitions of K^{c} and \binom{[n]}{k}.

To show that the three operators pairwise commute, it then suffices to show that L′(K), L′(\binom{[n]}{k}) commute. It follows from our main result Theorem 1.1 (whose proof does not rely on this proposition!) that the space V := C(\binom{[n]}{k−1}; ℝ) decomposes into a direct sum

V = V_{0} ⊕ V_{n}

where V_{0}, V_{n} are the 0-eigenspace and n-eigenspace for L′(\binom{[n]}{k}), respectively.

Since L′(\binom{[n]}{k}) is self-adjoint with respect to the usual inner product ⟨·, ·⟩, it must be that V_{n} = (V_{0})^{⊥}, so that L′(\binom{[n]}{k}) acts by scalars both on V_{0} and on (V_{0})^{⊥}.

We then claim that to show L′(K) commutes with L′(\binom{[n]}{k}), it suffices to show L′(K) annihilates all of V_{0}. To see this claim, note that it would certainly imply that L′(K) preserves V_{0} and commutes with the L′(\binom{[n]}{k}) action there. But it also implies that L′(K) preserves (V_{0})^{⊥}, since it implies L′(K) carries all of V into (V_{0})^{⊥}:

v ∈ V, v_{0} ∈ V_{0} ⇒ ⟨L′(K)(v), v_{0}⟩ = ⟨v, L′(K)(v_{0})⟩ = ⟨v, 0⟩ = 0.

The first equality here uses the self-adjointness of L′(K) with respect to the inner product. Since L′(\binom{[n]}{k}) acts as a scalar on (V_{0})^{⊥}, L′(K) commutes with its action there, and hence commutes with its action on all of V.

So we only need to show L′(K) annihilates all of

V_{0} = ker L′ (\binom{[n]}{k}) = ker(∂_{k−1} ∘ ∂_{k−1}^{∗}) = ker(∂_{k−1}^{∗})

where ∂_{k−1}, ∂_{k−1}^{∗} are the boundary and coboundary maps for the simplicial complex generated by \binom{[n]}{k}, and the last equality is a general linear algebra fact about maps of real inner product spaces.

We note that the coboundaries of (k−2)-subsets F span V_{0} = ker(∂_{k−1}^{∗}), because ∂_{k−1}^{∗} coincides with the coboundary map for the full simplex 2^{[n]} on vertex set [n], and this simplex is ℝ-acyclic due to the contractibility of its geometric realization. Hence it suffices to show that for any k-family K and any (k − 2)-subset F, we have L′(K) ∘ ∂_{k−2}^{∗}[F] = 0. But L′(K) = ∂_{k−1}^{K} ∘ (∂_{k−1}^{K})^{∗}, where ∂_{k−1}^{K}, (∂_{k−1}^{K})^{∗} are the boundary and coboundary maps for the simplicial complex generated by K. Therefore, it would suffice to prove the stronger assertion that

(∂_{k−1}^{K})^{∗} ∘ ∂_{k−2}^{∗}[F] = 0.

This would follow if we can show

(∂_{k−1}^{K})^{∗} ∘ ∂_{k−2}^{∗}[F] = (∂_{k−1}^{K})^{∗} ∘ (∂_{k−2}^{K})^{∗}[F]

since the latter always vanishes due to the application of two coboundary maps in the simplicial complex generated by K. To see this last equality, note that (∂_{k−1}^{K})^{∗}∂_{k−2}^{∗}[F] is a signed sum of oriented simplices [H] where the summation runs over pairs (H, G) in which F ⊂ G ⊂ H, k = |H| = |G| + 1 = |F | + 2, and G is arbitrary but H must lie in K. On the other hand, (∂_{k−1}^{K})^{∗}(∂_{k−2}^{K})^{∗}[F] is a similar sum, except that now G is constrained to lie in the simplicial complex generated by K. But this constraint is already implicitly present in the first summation, since H is in K and G ⊂ H. □

We immediately deduce

Theorem 4.5. In the situation of the previous proposition, the spectra

\begin{aligned}s′(K) & = (s_{1} ≥ … ≥ s\binom{n−1}{k}) \\ s′(K^{c}) & = (s_{1}^{c} ≥ … ≥ s\binom{n−1}{k}^{c}) \end{aligned}

both end with at least \binom{n−1}{k−2} zeroes. The rest of their spectra are related by

(4.5)  s_{i}^{c} = n − s_{\binom{n−1}{k−1}+1−i}

for each i ≤ \binom{n−1}{k−1}.

Having already discussed the two operations K ↦ K^{∗} and K ↦ K^{c} on kfamilies, it is now easy to understand the effect on the spectra of an operation on simplicial complexes sometimes known as the canonical Alexander dual or blocker (see e.g. [21, §6]). Definition 4.6. For a simplicial complex K on vertex set [n], the canonical Alexander dual K^{∨} is defined by

K^{∨} := {[n]\A: A ∉ K}.

In other words, the (i + 1)-family K_{i} of i-simplices in K and the (n − i − 1)-family K_{n−i−2}^{∨} of (n − i − 2)-simplices in K^{∨} are related by

K_{n−i−2}^{∨} = (K_{i})^{c∗} = (K_{i})^{c∗}.

It is well-known and not hard to show (see e.g. [21, §6]) that Alexander duality implies

H̃_{i}(K; ℤ) ≅ H̃^{n−i−3}(K^{∨}; ℤ).

and hence

H̃_{i}(K; ℝ) ≅ H̃^{n−i−3}(K^{∨}; ℝ) ≅ H̃_{n−i−3}(K^{∨}; ℝ)^{∗}

via the Universal Coefficient Theorems [28]. Consequently, the multiplicity of zero in s_{i}^{tot}(K) must coincide with the multiplicity of zero in s_{n−i−3}^{tot}(K^{∨}). The following corollary shows that much more is true. Corollary 4.7. Let K be a simplicial complex on vertex set [n], and K^{∨} its canonical Alexander dual. Let s_{i}^{tot}(K) denote the spectrum of

∂_{i+1}∂_{i+1}^{∗} + ∂_{i}^{∗}∂_{i}: C_{i}(K; ℝ) → C_{i}(K; ℝ).

Then for each i = −1, 0, 1, 2, …, n − 2,

• for every eigenvalue λ strictly less than n, the multiplicities of λ in s_{i}^{tot}(K) and s_{n−i−3}^{tot}(K^{∨}) are the same,

• the difference in multiplicities of the eigenvalue n is exactly

mult_{n} s_{i}^{tot}(K) − mult_{n} s_{n−i−3}^{tot}(K^{∨}) = f_{i}(K) − f_{n−i−3}(K^{∨})

= f_{i}(K) + f_{i+1}(K) − \binom{n}{i + 2}

where we recall that f_{i}(K) := |K_{i}| is the number of i-dimensional simplices of K.

Proof. As mentioned above, Alexander duality already implies the assertion for the multiplicity of the eigenvalue 0.

For eigenvalues λ not equal to 0 or n, note that combining Theorems 4.3 and 4.5 implies that for any k-family L, the multiplicities of λ in L and in L^{∗c} = L^{c∗} are the same. This implies in our situation that

∂_{i}^{∗}∂_{i}(K) and ∂_{n−i−2}∂_{n−i−2}^{∗}(K^{∨})

will have the same multiplicity of λ, and similarly for

∂_{i+1}∂_{i+1}^{∗}(K) and ∂_{n−i−3}^{∗}∂_{n−i−3}(K^{∨}).

Consequently, Equation (3.6) implies that their sums

∂_{i+1}∂_{i+1}^{∗}(K) + ∂_{i}^{∗}∂_{i}(K) and ∂_{n−i−3}^{∗}∂_{n−i−3}(K^{∨}) + ∂_{n−i−2}∂_{n−i−2}^{∗}(K^{∨})

will also have the same multiplicity of λ, as desired.

Since we have shown that the multiplicities of all eigenvalues other than n are the same for the two maps, it must be that multiplicities of n account for the difference between the dimensions of the vectors spaces C_{i}(K; ℝ), C_{n−i−3}(K^{∨}) on which they act. The second assertion of the proposition then follows immediately. □

The last operation we will discuss is the simplicial join. Definition 4.8. Given a simplicial complex K_{1} on [m] and a simplicial complex K_{2} on [n], their join K_{1} ∗ K_{2} is the simplicial complex on [m + n] consisting of all simplices of the form F_{1} ˙∪ F_{2}, where F_{1} ∈ K_{1} so that F_{1} ⊆ [m], and F_{2} ⊆ [m + 1, n] := {m + 1, m + 2, …, n} is obtained from some face of K_{2} by adding m to each of its elements. Here, ˙∪ denotes disjoint union. Proposition 4.9. For any simplicial complexes K_{1}, K_{2} and every i, the map ϕ defined ℝ-linearly by

[F_{1}] ⊗ [F_{2}] ↦ [F_{1} ˙∪ F_{2}]

identifies the vector spaces

⨁_{(i_{1},i_{2}) : i_{1}+i_{2}+1=i} C_{i_{1}}(K_{1}; ℝ) ⊗ C_{i_{2}}(K_{2}; ℝ) ≅ C_{i}(K_{1} ∗ K_{2}; ℝ)

and has the following property with respect to the Laplacians L of the appropriate dimensions in K_{1}, K_{2}, and K_{1} ∗ K_{2}:

(4.6)  L(K_{1} ∗ K_{2}) = L(K_{1}) ⊗ id + id ⊗ L(K_{2})

Proof. We will temporarily use the notations

∂, ∂^{∗}, L′, L′′, L,
∂_{K_{1}}, ∂_{K_{1}}^{∗}, L′_{K_{1}}, L′′_{K_{1}}, L_{K_{1}},
∂_{K_{2}}, ∂_{K_{2}}^{∗}, L′_{K_{2}}, L′′_{K_{2}}, L_{K_{2}}

for the boundary, coboundary, and Laplacian maps of appropriate dimensions in the complexes K_{1} ∗ K_{2}, K_{1}, K_{2}, respectively.

It is then straightforward to check that ∂, ∂^{∗} act on a typical chain [F_{1}] ⊗ [F_{2}] as graded derivations, i.e.

∂ = ∂_{K_{1}} ⊗ id + (−1)^{|F_{1}|}id ⊗ ∂_{K_{2}}
∂^{∗} = ∂_{K_{1}}^{∗} ⊗ id + (−1)^{|F_{1}|}id ⊗ ∂_{K_{2}}^{∗}

and consequently L′, L′′ behave as follows:

L′ = L′_{K_{1}} ⊗ id + (−1)^{|F_{1}|+1}∂_{K_{1}}^{∗} ⊗ ∂_{K_{2}} + (−1)^{|F_{1}|}∂_{K_{1}} ⊗ ∂_{K_{2}}^{∗} + id ⊗ L′_{K_{2}}
L′′ = L′′_{K_{1}} ⊗ id + (−1)^{|F_{1}|−1}∂_{K_{1}} ⊗ ∂_{K_{2}}^{∗} + (−1)^{|F_{1}|}∂_{K_{1}}^{∗} ⊗ ∂_{K_{2}} + id ⊗ L′′_{K_{2}}

Adding the last two equations gives the desired formula:

L = L_{K_{1}} ⊗ id + id ⊗ L_{K_{2}}.
□

We immediately deduce Theorem 4.10. If K_{1} and K_{2} are two simplicial complexes, and ∗ denotes the join, then

s_{i}^{tot}(K_{1} ∗ K_{2}) = ⋃_{\begin{matrix}i_{1}+i_{2}+1=i \\ λ_{1}∈s_{i_{1}}^{tot}(K_{1}), λ_{2}∈s_{i_{2}}^{tot}(K_{2}) \end{matrix}} λ_{1} + λ_{2}.

Corollary 4.11. If K is a simplicial complex, and 1 ∗ K denotes the cone over K, then

s′_{i}(1 ∗ K) ≗ 1^{f_{i}(K)} + (s′_{i−1}(K) ∪ s′_{i}(K))

for all i.

Proof. First we apply Theorem 4.10, with K_{1} being the simplicial complex on one vertex, and K = K_{2}. It is easy to check that s_{−1}^{tot}(K_{1}) = s_{0}^{tot}(K_{1}) = (1), and that s_{i}^{tot}(K_{1}) is the the trivial partition for all other i. Then Theorem 4.10 says

(4.7)  \begin{aligned}s_{i}^{tot}(1 ∗ K) & = ( ⋃_{λ_{1}∈s_{i−1}^{tot}(K)} λ_{1} + 1) ∪ ( ⋃_{λ_{2}∈s_{i}^{tot}(K)} 1 + λ_{2}) \\ & = (1^{f_{i−1}(K)} + s_{i−1}^{tot}(K)) ∪ (1^{f_{i}(K)} + s_{i}^{tot}(K)). \end{aligned}

Next we prove

s′_{i}(1 ∗ K) ≗ 1^{f_{i}(K)} + s_{i}^{tot}(K)

by induction on i; the result then follows by Equation (3.6). For i = −1,

s′_{−1}(1 ∗ K) = f_{0}(1 ∗ K) = 1 + f_{0}(K) = 1^{f_{−1}(K)} + s_{−1}^{tot}(K),

by Equation (3.5). So let i ≥ 0; then

s′_{i}(1 ∗ K) ≗ s_{i}^{tot}(1 ∗ K) − s′_{i−1}(1 ∗ K)  by Equation (3.6)
≗ s_{i}^{tot}(1 ∗ K) − (1^{f_{i−1}(K)} + s_{i−1}^{tot}(K))  by induction
= ((1^{f_{i}(K)} + s_{i}^{tot}(K)) ∪ (1^{f_{i−1}(K)} + s_{i−1}^{tot}(K)))
− (1^{f_{i−1}(K)} + s_{i−1}^{tot}(K))  by Equation (4.7)
= 1^{f_{i}(K)} + s_{i}^{tot}(K).
□

5. The main theorem

The goal of this section is to prove the main result Theorem 1.1 about the spectra for shifted families. We recall the statement of the theorem after establishing some notation to which we will adhere throughout the section.

Let K be a k-family, that is, a collection of k-element subsets of [n]. Let s(K) or just s denote the ≗-equivalence class of the spectrum of L′(K) = ∂_{k−1}∂_{k−1}^{T}. Let d(K) = d_{k−1}(K) denote the degree sequence of vertices with respect to the k-sets in K. Theorem 1.1. For any shifted k-family K, the spectrum s of its Laplacian L′(K) satisfies

s = d^{T}

where here d^{T} is the conjugate partition to the degree sequence d of vertices with respect to the k-sets in K.

As discussed in the introduction, in the case k = 2, the integrality of s is a result of Kelmans (see [20, Corollary 4.1]). Kelmans’ result was independently rediscovered by Merris [26], and elegantly reformulated as in the above theorem. We devote the remainder of this section to its proof.

Given a k-family on [n], define a new (k − 1)-family and k-family on the vertex set [2, n] := {2, 3, …, n} called, respectively, the link and deletion of vertex 1 in K:

\begin{aligned}link_{K}1 & := \{A\\{1\}: 1 ∈ A ∈ K\} \\ del_{K}1 & := \{A ∈ K: 1 ∉ A\}. \end{aligned}

There is always a decomposition

(5.1)  K = (1 ∗ link_{K}1) ˙∪ del_{K}1

where 1 ∗ link_{K}1 denotes the k-family {{1} ˙∪ A: A ∈ link_{K}1}, i.e. the collection of sets of K that contain 1. (See Definition 6.6 below.)

We say that K is a near-cone with apex 1 if for every set A in del_{K}1 and every a in A one has that A\{a} lies in link_{K}1. The relation between shifted families and near-cones is given by the following proposition, whose easy proof we omit. Lemma 5.1. Let K be a k-family on [n]. Then K is shifted if and only if K is a near-cone with apex 1, and both link_{K}1, del_{K}1 are shifted families with respect to the ordered vertex set [2, n].

In light of this lemma, the following two lemmas about the behavior of s and d^{T} for near-cones and shifted complexes immediately give a proof of Theorem 1.1 by induction on n. Lemma 5.2. If K is a k-family which is a near-cone with apex 1, then

d(K)^{T} ⊵ 1^{|link_{K}1|} + (d(link_{K}1)^{T} ∪ d(del_{K}1)^{T}).

Furthermore, when K is shifted, the above majorization inequality is an equality.

Proof. By taking the conjugate partition on both sides and using Proposition 2.3, we must show that

d(K) ⊴ (|link_{K}1|) ∪ (d(link_{K}1) + d(del_{K}1)).

By the definition of link_{K}1, the vertex 1 of K lies in exactly |link_{K}1| sets of K. So the left and right-hand sides of the desired inequality are both partitions that contain the part |link_{K}1|. We can therefore remove this part from both sides, and instead prove

d′(K) ⊴ d(link_{K}1) + d(del_{K}1).

where here d′(K) denotes the partition obtained from d(K) by removing the part |link_{K}1| corresponding to the vertex 1.

Now let

D′(K), D(link_{K}1), D(del_{K}1)

denote the unsorted degree sequences for the ordered vertex set [2, n] that correspond after sorting to

d′(K), d(del_{K}1), d(link_{K}1)

respectively. From the decomposition (5.1) it follows that

D′(K) = D(del_{K}1) + D(link_{K}1)

as vectors of nonnegative integers in ℕ^{n−1}. On the other hand, it is easy to see [25, Chapter 6, A.1] that if d′, d_{1}, d_{2} are the sorted partitions corresponding to any three vectors D′, D_{1}, D_{2} of nonnegative integers satisfying

D′ = D_{1} + D_{2}

then

d′ ⊴ d_{1} + d_{2}.

This proves the desired inequality, and hence completes the proof of the first assertion.

For the second assertion, note that when K is shifted, Equation (2.1) guarantees the ordered degree sequences D′(K), D(link_{K}1), D(del_{K}1) coincide with d′(K), d(link_{K}1), d(del_{K}1). Hence the last inequality above becomes an equality, which when traced backwards proves the second assertion. □

Lemma 5.3. If K is a k-family which is a near-cone with apex 1, then

s(K) ≗ 1^{|link_{K}1|} + (s(link_{K}1) ∪ s(del_{K}1)).

Proof. Let K′ be the (k − 1)-dimensional simplicial complex generated by link_{K}1 ˙∪ del_{K}1. Recall that (K′)_{j} denotes the (j + 1)-family of j-dimensional faces of K′. Since del_{K}1 is a k-family and link_{K}1 is a (k − 1)-family,

(5.2)  (K′)_{k−1} = del_{K}1;

the near-cone condition on K further implies

(5.3)  (K′)_{k−2} = link_{K}1.

Now let 1 ∗ K′ denote the simplicial complex cone over K′. Then

(5.4)  (1 ∗ K′)_{k−1} = (1 ∗ (K′)_{k−2}) ˙∪ (K′)_{k−1} = (1 ∗ link_{K}1) ˙∪ del_{K}1 = K.

Thus

s(K) ≗ s′_{k−2}(1 ∗ K′)  by Equation (5.4)
≗ 1^{f_{k−2}(K′)} + (s′_{k−3}(K′) ∪ s′_{k−2}(K′)) by Corollary 4.11
≗ 1^{|link_{K}1|} + (s(link_{K}1) ∪ s(del_{K}1)) by Equations (5.3) (twice) and (5.2).

Here we are using, in the first and last equivalence, that s′_{i} depends only upon (i + 1)-dimensional faces.

□

The proof of Theorem 1.1 (specifically Lemma 5.3) actually established a stronger result which applies to families that are not necessarily shifted: Corollary 5.4. If K is a near-cone and s(link_{K}1) and s(del_{K}1) are integral, then so is s(K). □ Example 5.5. We use Corollary 5.4 to find a non-shifted family K with s(K) integral.

Define a 3-family K on vertex set [6] by letting

link_{K}1 = {23, 24, 25, 26, 34, 35, 36, 45},
del_{K}1 = {236}.

(For clarity’s sake, we are omitting the commas and set brackets in and around individual sets.) One can easily verify that both link_{K}1 and del_{K}1 are isomorphic to shifted families. Hence s(link_{K}1) and s(del_{K}1) are integral by Theorem 1.1, and thus s(K) is integral by Corollary 5.4. But one can check that K is not isomorphic to a shifted family.

One can, of course, rephrase the main result in terms of the spectra of L_{i}(K) for a simplicial complex K:

Corollary 5.6. If K is a shifted simplicial complex, then

s_{i}^{tot}(K) ≗ d_{i}(K)^{T} ∪ d_{i+1}(K)^{T} .

Proof. Apply Equation (3.6) to Theorem 1.1. □

6. A conjecture on the spectra

The goal of this section is to recall and present evidence for Conjecture 1.2, which generalizes a conjecture of Grone and Merris [19, Conjecture 2].

We adhere to the same notation as in the previous section, that is, for a kfamily K, we let s = s(K) denote the ≗-equivalence class of the spectrum of L′(K) = ∂_{k−1}∂_{k−1}^{T}, and d(K) = d_{k−1}(K) denotes the degree sequence of vertices with respect to the k-sets in K.

Conjecture 1.2. For any k-family K,

s ⊴ d^{T}

with equality if and only if K is isomorphic to a shifted family.

We remark that half of the “if and only if” assertion about the case of equality is exactly Theorem 1.1. It will also be shown (in Proposition 6.4 below) that the other half of this “if and only if” actually would follow if we knew the majorization inequality asserted in the first part of the conjecture.

We begin by proving some weaker consequences of the conjecture. Note that the majorization inequality says that if s(K) = (s_{1}, s_{2}, …) with s_{1} ≥ s_{2} ≥ ⋯, and d(K)^{T} = (d_{1}^{T} , d_{2}^{T} , …) then

s_{1} ≤ d_{1}^{T}
s_{1} + s_{2} ≤ d_{1}^{T} + d_{2}^{T}
s_{1} + s_{2} + s_{3} ≤ d_{1}^{T} + d_{2}^{T} + d_{3}^{T}
⋮
∑_{j} s_{j} ≤ ∑_{j} d_{j}^{T}

and so we first observe that the last inequality is actually always an equality:

Proposition 6.1.

∑_{j} s_{j} = ∑_{j} d_{j}^{T}

Proof.

∑_{j} d_{j}^{T} = ∑_{j} d_{j}

= ∑_{i=1}^{n}|{A ∈ K: i ∈ A}|

= ∑_{B⊂[n],|B|=k−1}|{A ∈ K: B ⊂ A}|

= Trace ∂_{K}∂_{K}^{∗}

= ∑_{j} s_{j}

□

The first inequality in the conjectured majorization Conjecture 1.2 is easy (and was already known for graphs [19, p. 226]): Proposition 6.2.

s_{1} ≤ d_{1}^{T}

Proof. Note that d_{1}^{T} is simply the number of vertices in [n] which lie in some subset of K, that is, the number of non-isolated vertices with respect to K. Since isolated vertices will only add zero rows to the various Laplacian matrices, and hence only add zeroes to their spectra, we may assume without loss of generality that d_{1}^{T} = n. Hence we must show s_{1} ≤ n.

We give three proofs of this. The first uses Theorem 4.3 relating the spectra of K and K^{∗}, which asserts that each entry s_{i} in the spectrum for K is either 0 or of the form n − s_{j}^{∗} for some entry s_{j}^{∗} in the spectra for K^{∗}. Since all the s_{j}^{∗} are nonnegative, we conclude that s_{i} ≤ n for each i.

Similarly one can use Theorem 4.5 relating the spectra of K and K^{c} to prove s_{i} ≤ n in exactly the same way.

Lastly, one can use a monotonicity property of s_{1} with respect to the family K which follows from the variational characterization [25, Chapter 20, A.1, p. 510] of s_{1}. We know that

s_{1}(K) = max_{x∈ℝ^{\binom{[n]}{k−1}}\\{0\}} \frac{x^{T} ∂_{K}∂_{K}^{∗}x}{x^{T} x} = max_{x∈ℝ^{\binom{[n]}{k−1}}\\{0\}} \frac{∥∂_{K}^{∗}x∥^{2}}{∥x∥^{2}} .

From this it follows that s_{1} for K is bounded above by s_{1} for the complete k-family \binom{[n]}{k}, since for any x in ℝ^{\binom{[n]}{k−1}},

∥∂_{K}^{∗}x∥^{2} ≤ ∥∂\binom{[n]}{k}^{∗}x∥^{2}.

But we know \binom{[n]}{k} has s_{1} = n by Theorem 1.1. □

From the previous proposition, we know that s_{i} lies in the range [0, n] for each i, and the same is trivially true for d: we have 0 ≤ d_{i}^{T} ≤ n since d is a partition with n parts. Therefore Conjecture 1.2 has consequences regarding the relation between multiplicities of the values 0 and n in s and d. These consequences turn out to be true, and for the purposes of stating them most conveniently, we regard both s = (s_{1}, …, s_{|K|}) and d = (d_{1}^{T} , …, d_{|K|}^{T}) as sequences of length |K|, thinking of s as the spectrum of the |K| × |K| matrix ∂_{K}^{∗}∂_{K}. We also recall from Section 4 that K^{∗} is the (n − k)-family defined by

K^{∗} = {[n]\A: A ∈ K}.

Proposition 6.3. The multiplicity of 0 (resp. n) in s is at least (resp. at most) the multiplicity of 0 (resp. n) in d^{T}, with equality if and only if K (resp. K^{∗}) is a near-cone.

Proof. The assertions for the multiplicity of n follow from the same assertions for the multiplicity of 0 using Theorem 4.3, so we only need to prove the latter assertions.

One can check that the multiplicity of 0 in d^{T} is exactly |K| − δ, where δ is the maximum degree of a vertex in [n] with respect to the k-family K. Let v in [n] be a vertex that achieves this maximum degree δ. Then |K| − δ is exactly the number of maximal faces of K that do not contain v. Thus we must show the following

Claim. The rank of the top homology group in the simplicial complex \overline{K} generated by a k-family K is at most the number of sets in K not containing v.

To see this, note that the sets in K which contain v generate a contractible subcomplex S (the closed star of v) in \overline{K} having v as a cone point. By contracting this subcomplex S to a point, one obtains from K a homotopy equivalent cell complex \overline{K}/S having one top dimensional cell for each set in K that does not contain v. Since homology groups are invariants of homotopy type, and the homology of a cell complex can be computed by a cellular chain complex, this proves the claim. The desired inequality follows.

Note also that if equality occurs, then every top dimensional cell in K/S corresponding to some set in K that does not contain v must be attached to the contracted subcomplex S along its entire boundary. But this exactly says that every subset of a set in del_{K}v having co-cardinality one must lie in link_{K}v, i.e. K is a near-cone with apex v. □

We can now show that the first assertion in Conjecture 1.2 implies the second. Proposition 6.4. If we know that s ⊴ d^{T} holds for every k-family, then s(K) = d^{T} (K) implies K is isomorphic to a shifted family.

Proof. We use induction on n. Assume K is a k-family on [n] with s(K) = d(K)^{T}. Then Proposition 6.3 implies that K is a near-cone on some vertex, which we may assume without loss of generality is vertex 1. By Proposition 5.1, it would suffice to show that link_{K}1, del_{K}1 satisfy the same equality s = d^{T}. To see this, we exhibit a sequence of majorization inequalities and equalities, which will be justified below:

1^{|link_{K}1|} + (d(link_{K}1)^{T} ∪ d(del_{K}1)^{T}) ⊵^{(1)} 1^{|link_{K}1|} + (s(link_{K}1) ∪ s(del_{K}1))
=^{(2)} s(K)
= d(K)^{T}

⊵^{(3)} 1^{|link_{K}1|} + (d(link_{K}1)^{T} ∪ d(del_{K}1)^{T}).

The inequality ⊵^{(1)} comes from the assumption that s ⊴ d^{T} applied to both families link_{K}1, del_{K}1, and uses the fact [25, Chapter 5, A.7(i), p. 121] that if α ⊴ β then for any γ one has

α ∪ γ ⊴ β ∪ γ.

The equality =^{(2)} follows from Lemma 5.3, since K is a near-cone. The next equality is our hypothesis. The last inequality ⊵^{(3)} follows from Lemma 5.2.

Since the sequence of inequalities and equalities begins and ends with the same partition, we conclude that every inequality must actually be an equality. In particular, that ⊵^{(1)} is an equality, when combined with the assumption that s ⊴ d^{T} applies to link_{K}1 and del_{K}1, implies

s(link_{K}1) = d(link_{K}1)^{T} ,
s(del_{K}1) = d(del_{K}1)^{T} .

Thus, induction applies and the proof is complete. □

A further piece of evidence for Conjecture 1.2 is its consistency with some of the constructions of Section 4. Proposition 6.5. For any k-family K on [n], one has

s(K) ⊴ d(K)^{T}
⇔ s(K^{∗}) ⊴ d(K^{∗})^{T}
⇔ s(K^{c}) ⊴ d(K^{c})^{T} .

Proof. For weakly decreasing sequences of nonnegative real numbers

λ = (λ_{1} ≥ λ_{2} ≥ … ≥ λ_{r})

and positive integers a satisfying a ≥ λ_{1}, define the complementation of λ within a^{r} to be the weakly decreasing sequence

a^{r}\λ = (a − λ_{r} ≥ a − λ_{r−1} ≥ … ≥ a − λ_{1}).

It is easy to check that this operation preserves majorization

λ ⊴ μ ⇔ a^{r}\λ ⊴ a^{r}\μ,

and also that it commutes with conjugation whenever a is a nonnegative integer and λ is a partition

(a^{r}\λ)^{T} = r^{a}\λ^{T} .

This applies to our situation since Theorems 4.3 and 4.5 imply that

\begin{aligned}s′(K^{∗}) & = n^{|K|}\s′(K) \\ s′′(K^{c}) & = n^{\binom{n−1}{k−1}}\s′′(K) \end{aligned}

and it is easy to check that

\begin{aligned}d(K^{∗}) & = |K|^{n}\d(K) \\ d(K^{c}) & = \binom{n − 1}{k − 1}^{n}\d(K) \end{aligned}

so that

\begin{aligned}d(K^{∗})^{T} & = n^{|K|}\d(K)^{T} \\ d(K^{c})^{T} & = n^{\binom{n−1}{k−1}}\d(K)^{T} . \end{aligned}

Since s is the ≗-equivalence class of either s′ or s′′, the result follows. □

Note that the previous proposition reduces the proof of Conjecture 1.2 to the cases of k-families K where |K| ≤ \frac{1}{2} \binom{n}{k} and where also k ≤ \frac{n}{2}. However we are not hopeful that this reduction will be useful.

Conjecture 1.2 is also consistent with the simplicial join, which is defined for families the same way it is defined for simplicial complexes (Definition 4.8). Definition 6.6. Given a k_{1}-family K_{1} on [m] and a k_{2}-family on [n], their join K_{1} ∗ K_{2} is the (k_{1} + k_{2})-family on [m + n] consisting of all sets of the form F_{1} ˙∪ F_{2}, where F_{1} ∈ K_{1} so that F_{1} ⊆ [m], and F_{2} ⊆ [m+1, n] is obtained from some member of K_{2} by adding m to each of its elements. Thus

\overline{K_{1} ∗ K_{2}} = \overline{K_{1}} ∗ \overline{K_{2}},

where \overline{K} denotes the simplicial complex generated by a family K. Proposition 6.7. If K_{1} and K_{2} are families such that s(K_{1}) ⊴ d(K_{1})^{T} and s(K_{2}) ⊴ d(K_{2})^{T}, then s(K_{1} ∗ K_{2}) ⊴ d(K_{1} ∗ K_{2})^{T}.

Proof. For a partition λ = (λ_{1}, …, λ_{r}) = 1^{l_{1}}2^{l_{2}} ⋯ and a positive integer c, define new partitions

cλ = (cλ_{1}, …, cλ_{r})

(multiply each part by c), and

λ^{c} = 1^{cl_{1}}2^{cl_{2}} ⋯

(repeat each part c times). It is a routine calculation that (cλ)^{T} = (λ^{T})^{c}.

Let v be a vertex of K_{1}, so v is also a vertex of K_{1} ∗ K_{2}. For every F_{1} ∈ K such that v ∈ F_{1}, all |K_{2}| of the members F_{2} of K_{2} satisfy v ∈ F_{1} ˙∪ F_{2} ∈ K_{1} ∗ K_{2}; thus deg(K_{1} ∗ K_{2}, v) = |K_{2}| deg(K_{1}, v). Similarly, if w ∈ K_{2}, then deg(K_{1} ∗ K_{2}, w) = |K_{1}| deg(K_{2}, w). It follows that

d(K_{1} ∗ K_{2}) = |K_{2}|d(K_{1}) ∪ |K_{1}|d(K_{2}).

Therefore

d(K_{1} ∗ K_{2})^{T} = (|K_{2}|d(K_{1}) ∪ |K_{1}|d(K_{2}))^{T}
= (|K_{2}|d(K_{1}))^{T} + (|K_{1}|d(K_{2}))^{T}
= (d(K_{1})^{T})^{|K_{2}|} + (d(K_{2})^{T})^{|K_{1}|}.

For an arbitrary k-family K with corresponding (k − 1)-dimensional simplicial complex \overline{K}, we have s(K) = s′′_{k−1}(\overline{K}) = s_{k−1}^{tot}(\overline{K}), with the convention (to which we will adhere for the remainder of the proof) that s(K) has |K| parts, by adding trailing zeroes where necessary. Theorem 4.10 thus implies

(6.1)  s(K_{1} ∗ K_{2}) = ⋃_{\begin{matrix}λ_{1}∈s(K_{1}) \\ λ_{2}∈s(K_{2}) \end{matrix}} λ_{1} + λ_{2}.

The components of the right-hand side of Equation (6.1) are those of the vector

s(K_{1})^{|K_{2}|} + S_{2},

where S_{2} is the vector obtained by concatenating |K_{1}| copies of s(K_{2}) together. Clearly the sorted partition corresponding to S_{2} is s(K_{2})^{|K_{1}|}, and so, as in the proof of Lemma 5.2, it is easy to see [25, Chapter 6, A.1] that

s(K_{1} ∗ K_{2}) ⊴ s(K_{1})^{|K_{2}|} + s(K_{2})^{|K_{1}|}.

We now conclude

s(K_{1} ∗ K_{2}) ⊴ s(K_{1})^{|K_{2}|} + s(K_{2})^{|K_{1}|}
⊴ (d(K_{1})^{T})^{|K_{2}|} + (d(K_{2})^{T})^{|K_{1}|}
= d(K_{1} ∗ K_{2})^{T} .
□

7. The second inequality for graphs

The goal of this section is to prove Theorem 7.1. For 2-families (graphs), the second inequality

s_{1} + s_{2} ≤ d_{1}^{T} + d_{2}^{T}

in Conjecture 1.2 is valid.

Our method is a sequence of reductions to special families of graphs for which we can verify the theorem with the aid of a computer algebra package. We do not expect this proof to generalize to the other inequalities, nor to prove the second inequality for k-families with k arbitrary. For this reason and to save space, we give only a sketch of the proof. Step 1. For any k-family K we have

(7.1)  s_{1} + s_{2} ≤ d_{1}^{T} + d_{2}^{T} + 2(k − 1).

The proof relies on the decomposition (as square matrices of size \binom{n}{k−1})

L′(K) = L′(K_{1}) + L′(K_{2})

where K_{1} is the collection of all A in K that do not contain any vertices of degree one, and K_{2} = K − K_{1}. A theorem of Fan [25, Chapter 9, G.1, p. 241], then says that

s_{1}(K) + s_{2}(K) ≤ s_{1}(K_{1}) + s_{2}(K_{1}) + s_{1}(K_{2}) + s_{2}(K_{2}).

Proposition 6.2 gives the trivial upper bounds s_{1}(K_{1}), s_{2}(K_{1}) ≤ d_{2}^{T} (K). By classifying the vertices of degree one into equivalence classes according to the unique (k−1)-subset with which they form a set of K, one can decompose K_{2} into a disjoint union of shifted families to which Theorem 1.1 applies. Letting b_{1} ≥ b_{2} ≥ … ≥ b_{r} denote the sizes of these equivalence classes (so ∑_{i} b_{i} = d_{1}^{T} (K) − d_{2}^{T} (K)), one obtains the inequality

s_{1}(K) + s_{2}(K) ≤ 2d_{2}^{T} + b_{1} + b_{2} + 2(k − 1)
≤ 2d_{2}^{T} + (d_{1}^{T} − d_{2}^{T}) + 2(k − 1)
= d_{1}^{T} + d_{2}^{T} + 2(k − 1)

Note that we have in fact shown something slightly stronger: whenever we have the inequality

(7.2)  d_{1}^{T} − d_{2}^{T} − (b_{1} + b_{2}) = b_{3} + b_{4} + ⋯ + b_{r} ≥ 2(k − 1)

the second inequality of Conjecture 1.2 follows. Step 2. We use the previous comment to reduce Theorem 7.1 to some special cases.

Note that since k = 2 for graphs, and b_{i} ≥ 1 for each i, the inequality (7.2) holds whenever r ≥ 4, or when r = 3 and b_{3} ≥ 2. Consequently Theorem 7.1 follows if we can show it for graphs having r = 1, for those having r = 2, and for those having r = 3 with b_{3} = 1. Step 3. A further (independent) reduction comes from monotonicity properties of the eigenvalues.

Variational characterizations of eigenvalues [25, Chapter 20, A.2] imply that adding an edge between two previously unconnected vertices of G can only make the quantity s_{1}(G) + s_{2}(G) weakly increase. Since adding edges between vertices of G with degree at least 2 will not affect d_{2}^{T} (G) nor d_{1}^{T} (G), we are reduced to proving Theorem 7.1 for graphs in which the vertices of degree at least 2 induce a complete subgraph G.

Combining this with Step 2 reduces us to some very special graphs. Given positive integers b_{1}, …, b_{r} and a positive integer a ≥ r, define a graph G_{a,b_{1},b_{2},..,b_{r}} as follows: G_{a,b_{1},b_{2},..,b_{r}} contains the complete graph on vertex set [a], and then b_{1} + … + b_{r} other vertices of degree one in which the first b_{1} all have vertex 1 as a common neighbor, the next b_{2} all have vertex 2 as a common neighbor, etc. Then Theorem 7.1 holds for all graphs G assuming that it holds for

• G_{a,b_{1}} with a ≥ 1 and

• G_{a,b_{1},b_{2}} with a ≥ 2 and b_{1}, b_{2} ≥ 1,

• G_{a,b_{1},b_{2},1} with a ≥ 3 and b_{1}, b_{2} ≥ 1.

On the other hand, G_{a,b_{1}} is shifted, so the theorem follows from Theorem 1.1 in this case. Therefore we only need to deal with the latter two families. Step 4. We now attack the special cases G_{a,b_{1},b_{2}}, G_{a,b_{1},b_{2},1} by examining their characteristic polynomials. It is possible to exhibit a large part of the eigenspace decomposition of their Laplacians directly, which we explain here for the slightly more general case of G_{a,b_{1},b_{2},b_{3}}.

Let x = (x_{1}, x_{2}, …, x_{a+b_{1}+b_{2}+b_{3}})^{T} be a typical vector on which L′(G_{a,b_{1},b_{2},b_{3}}) acts. Then (cf. [12, proof of Theorem 5.2] and [19, proof of Theorem 4]) one can easily check directly that

• all vectors x having

x_{4} + x_{5} + ⋯ + x_{a} = 0

and all other coordinates 0 form an (a − 4)-dimensional subspace inside the a-eigenspace for L′(G_{a,b_{1},b_{2},b_{3}}),

• all vectors x having

x_{a+1} + ⋯ + x_{a+b_{1}} = x_{a+b_{1}+1} + ⋯ + x_{a+b_{1}+b_{2}}
= x_{a+b_{1}+b_{2}+1} + ⋯ + x_{a+b_{1}+b_{2}+b_{3}} = 0

and all other coordinates 0 form a (b_{1} + b_{2} + b_{3} − 3)-dimensional subspace inside the 1-eigenspace for L′(G_{a,b_{1},b_{2},b_{3}}).

By choosing natural bases for the orthogonal complement of these eigenspaces, one can write down the following expressions for their characteristic polynomials:

det(xI − L′(G_{a,b_{1},b_{2}})) = (x − 1)^{b_{1}+b_{2}−2}(x − a)^{a−3} det(xI − A)
det(xI − L′(G_{a,b_{1},b_{2},1})) = (x − 1)^{b_{1}+b_{2}−2}(x − a)^{a−4} det(xI − B)

where A and B are two explicit symmetric matrices, of size 5 and 7 respectively, having entries which are simple algebraic functions of a, b_{1}, b_{2}.

As a consequence of these expressions, one can check that Theorem 7.1 will follow for G_{a,b_{1},b_{2}} and G_{a,b_{1},b_{2},1} if we can show these two assertions:

(1) For a ≥ 2 and b_{1}, b_{2} ≥ 1, the matrix A has the sum of its largest two eigenvalues at most 2a + b_{1} + b_{2},

(2) For a ≥ 3 and b_{1}, b_{2} ≥ 1, the matrix B has the sum of its largest two

eigenvalues at most 2a + b_{1} + b_{2} + 1. Step 5. In this last step, a computer plays a role, and we illustrate the argument for the matrix A (the argument for B is similar).

The second additive compound of a matrix M [25, Chapter 19 §F, p. 505] is a matrix M^{(2)} whose largest eigenvalue is the sum of the two largest eigenvalues of M. Consequently, we must show A^{(2)} has all eigenvalues at most 2a + b_{1} + b_{2}. A pleasant feature in our situation is that A^{(2)} turns out to have entries which are polynomials in a, b_{1}, b_{2}.

Equivalently we need to show A^{(2)}−(2a+b_{1}+b_{2})I has all nonpositive eigenvalues, and for this it is sufficient to show that all coefficients of powers x^{i} in the expansion of

det(xI − (A^{(2)} − (2a + b_{1} + b_{2})I)) = det((x − (2a + b_{1} + b_{2}))I − A^{(2)})

are nonnegative (for a ≥ 2 and b_{1}, b_{2} ≥ 1). To do this, we used a computer algebra package to expand

[det((x − (2a + b_{1} + b_{2}))I − A^{(2)})]\begin{matrix}a↦α+2 \\ b_{1}↦β_{1}+1 \\ b_{2}↦β_{2}+1 \end{matrix} .

and checked a sufficient condition: that every coefficient of every monomial in the variables α, β_{1}, β_{2}, x is nonnegative.

8. Some easy spectrum bounds

In this section we discuss some easy inequalities on the spectrum s for a general k-family, which generalize well-known inequalities for the case of graphs (k = 2). Again we adhere to the notation of the previous two sections.

Our first inequality is a direct consequence of Schur’s Dominance Theorem [25, Chapter 9, B.1, p. 218] saying that the spectrum of a real symmetric matrix majorizes the weakly decreasing rearrangement of its diagonal entries. In order to apply this to L′(K), we note from Equation (3.2) that its diagonal entries are the degrees of (k − 1)-subsets of [n] with respect to K, that is, the quantities deg(K, A) as A runs though \binom{[n]}{k−1}. For a k-family K on [n], let

d^{(k−1)}(K) = (d_{1}^{(k−1)}, …, d\binom{n}{k−1}^{(k−1)})

denote this degree sequence of all (k − 1)-subsets of [n] with respect to K written in weakly decreasing order. We then immediately deduce Proposition 8.1. For any k-family

d^{(k−1)} ⊴ s. □

Note that the first inequality in this majorization asserts that the maximum degree d_{1}^{(k−1)} of a (k − 1)-subset with respect to K satisfies d_{1}^{(k−1)} ≤ s_{1}. One can say something much stronger.

Proposition 8.2. (cf. [19, Corollary 2]) For any k-family,

d_{1}^{(k−1)} + k − 1 ≤ s_{1} ≤ d_{1}^{(k−1)} + d_{2}^{(k−1)} + ⋯ + d_{k}^{(k−1)}.

Proof. The lower bound on s_{1} can be obtained using the variational characterization

s_{1} = max_{x∈ℝ^{|K|}≠0} \frac{x^{T} ∂_{K}^{∗}∂_{K}x}{x^{T} x}.

Let D = d_{1}^{(k−1)}. By its definition, we can find a (k − 1)-subset A that lies in exactly D sets A_{1}, …, A_{D} of K. Letting ϵ(A_{i}, A) = (−1)^{r} when A_{i}\A is the r^{th} smallest element of A_{i}, a direct calculation shows that the vector x ∈ ℝ^{|K|} having A_{i}^{th} coordinate ϵ(A_{i}, A) and all other coordinates zero satisfies

x^{T} ∂_{K}^{∗}∂_{K}x = D(D + k − 1).

Clearly x^{T} x = D, so we conclude that

s_{1} ≥ \frac{x^{T} ∂_{K}^{∗}∂_{K}x}{x^{T} x} = \frac{D(D + k − 1)}{D} = D + k − 1.

The upper bound on s_{1} follows from Gershgorin’s Theorem [17] applied to L′′(K) = ∂_{K}^{∗}∂_{K}. Recall that Gershgorin’s Theorem says a complex N × N matrix A = (a_{ij}) has every eigenvalue lying in at least one of the disks |z − a_{ii}| ≤ ρ_{i}, where ρ_{i} = ∑_{j}|a_{ij}|. If row i of L′′(K) corresponds to a k-subset A in K, then a glance at Equation (3.3) shows that a_{ii} = k. Furthermore, each non-zero entry in row i is a ±1, with the number of such entries being the sum of deg(K, A′) − 1 as A′ runs through the (k − 1)-subsets contained in A. Since there are k distinct such (k − 1)-subsets A′, this sum is at most (d_{1}^{(k−1)} − 1) + ⋯ + (d_{k}^{(k−1)} − 1), which then gives an upper bound for ρ_{i}. Consequently,

s_{1} ≤ a_{ii} + ρ_{i}
≤ k + (d_{1}^{(k−1)} − 1) + ⋯ + (d_{k}^{(k−1)} − 1)
= d_{1}^{(k−1)} + d_{2}^{(k−1)} + ⋯ + d_{k}^{(k−1)}.
□

Remark 8.3. One might try to apply Gershgorin’s Theorem to L′(K), but one obtains in general only the weaker inequality

s_{1} ≤ kd_{1}^{(k−1)}.

Proposition 8.1 raises a question about its consistency with Conjecture 1.2. The truth of Conjecture 1.2 together with Proposition 8.1 would imply d^{(k−1)} ⊴ s ⊴ d^{T}. It is therefore reassuring to note that the following weaker consequence is valid, whose simple proof was pointed out to us by X. Dong: Proposition 8.4.

(8.1)  d^{(k−1)} ⊴ d^{T} .

Proof. Something yet more general follows from the half of the Gale-Ryser Theorem [25, Chapter 7, C.1, p. 176] which says that for any matrix of 0’s and 1’s, the weakly decreasing rearrangement of the row sums are dominated by the transpose of the weakly decreasing rearrangement of the column sums. If K is a k-family and we let d^{(i)} denote the weakly decreasing rearrangement of the degrees deg(K, A) for i-subsets A, then we have more generally that

d^{(i)} ⊴ (d^{(k−i)})^{T} .

This follows from consideration of the (0, 1)-matrix whose rows are indexed by i-subsets, columns are indexed by (k − i)-subsets, and the entry indexed by the i-subset A and (k − i)-subset B is 1 exactly when the disjoint union of A and B is a subset in K. □

For graphs, we have k = 2, i = 1 and

d^{(i)} = d^{(k−i)} = d^{(1)} =: d

is the degree sequence of the graph. Here it is known that degree sequences d are characterized by the following set of stronger inequalities [30]

(8.2)  ∑_{i=1}^{k}(d_{i} + 1) ≤ ∑_{i=1}^{k} d_{i}^{T}

for 1 ≤ k ≤ f(d), where f(d) is the size of the Durfee square of d when thought of as a partition, i.e. f(d) = |{i: d_{i} ≥ i}|.

In particular, the first inequality of (8.2) says d_{1} + 1 ≥ d_{1}^{T}, which motivated a conjecture of Grone and Merris [19, Conjecture 1] that was proven by Grone [18]. Grone’s result strengthens Proposition 8.1 to the following majorization inequality in the case k = 2:

(8.3)  (d_{1} + 1, d_{2}, d_{3}, …, d_{n−2}, d_{n−1}, d_{n} − 1) ⊴ s.

For arbitrary k, it is easy to see that

(8.4)  d_{1}^{(k−1)} + k − 1 ≤ d_{1}^{T} ,

so that the first inequality in Conjecture 1.2 (which we know is true by Proposition 6.2) is consistent with the first inequality of Proposition 8.1. The preceding discussion motivates the following questions. Question 8.5. Is there a set of valid inequalities generalizing (8.1), (8.2), and (8.4) for an arbitrary k-family? Question 8.6. Is there a majorization inequality relating d^{(k−1)} and s that generalizes both Proposition 8.1 and (8.3), and that is valid for arbitrary k-families?

9. Shifted versus degree-maximal complexes

The goal of this section is to explore how the relationship between shifted graphs, degree sequences, and the majorization partial order ⊴ extends to higher dimensional k-families.

A partition is graphic if it is the degree sequence of some graph. Ruch and Gutman proved that if β is graphic and α ⊴ β, then α is also graphic [30, Theorem 1]. We generalize graphic partitions in the obvious way, by calling a partition krealizable if it is the degree sequence of a k-family. Ruch and Gutman’s theorem now extends directly. Proposition 9.1. If β is k-realizable and α ⊴ β, then α is k-realizable.

Proof. Let K be the k-family such that β = d(K), and number the vertices of K such that deg(K, v) = β_{v}. By induction, we may assume β covers α in the majorization partial order, i.e., there is some m such that

β_{m} = α_{m} + 1
β_{m+1} = α_{m+1} − 1
β_{j} = α_{j} for all other j.

Since α is a partition, then,

β_{m} = α_{m} + 1 ≥ α_{m+1} + 1 > α_{m+1} − 1 = β_{m+1}.

Because β_{m} > β_{m+1}, there is some set B ∈ K containing vertex m but not vertex m + 1, such that A := B\{m} ˙∪ {m + 1} ∉ K. Then α = d(K\{B} ˙∪ {A}). □

In the language of posets, Proposition 9.1 says that the k-realizable partitions form an order ideal in the poset of partitions partially ordered by ⊴.

Merris [26] defined a graph to be degree-maximal (or maximal ) if its degree sequence is majorized by no other graphic partition. Proposition 9.2. A graph is degree-maximal if and only if it is shifted.

Proof. Peled and Srinivasan [29, Theorem 5.8] proved that a graph is degreemaximal if and only if it is threshold. But one of several equivalent definitions of threshold graphs is easily seen to be the definition of shifted graphs [8, Corollary 1A]. □

Following Merris, we will say a k-family is degree-maximal if its degree sequence is majorized by no other k-realizable partition. Proposition 9.2 extends to higher dimensions in only one direction, as the following proposition and example show. Proposition 9.3. If a k-family is degree-maximal, then it is shifted.

Proof. Let K be a degree-maximal k-family. In order to show that K is shifted, it suffices, by induction, to show that if A covers B in ≤_{P}, then A ∈ K implies B ∈ K. So assume A ∈ K and that A covers B, i.e., m ∈ B, m + 1 ∉ B, and A = B\{m} ˙∪ {m + 1} for some m. We will show B ∈ K.

Let α = d(K), and number the vertices of K such that deg(K, v) = α_{v}. Let β be the partition defined by β_{m} = α_{m} + 1, β_{m+1} = α_{m+1} − 1, and β_{j} = α_{j} for all other j. Thus d(K) = α ⊴ β, and so β is not k-realizable, because K is degreemaximal. It follows that B ∈ K; for otherwise β = d(K\{A} ˙∪ {B}). Therefore K is shifted. □

Example 9.4. We construct, for any k ≥ 3, a k-family that is shifted but not degree-maximal.

For k = 3, we will construct a 3-family on vertex set [10] that is shifted, but not degree-maximal. First, define a pair of 3-families, K′_{1} = {159, 267, 348} and K′_{2} = {168, 24(10), 357} (omitting commas and brackets of individual sets). Now let K_{0} be the shifted 3-family consisting of all 3-subsets of [10] that precede one of the 3-sets of K′_{1} and K′_{2} in the componentwise partial order ≤_{P}, and let K_{1} = K_{0} ˙∪ K′_{1} and K_{2} = K_{0} ˙∪ K′_{2}. It is not hard to verify that K_{1} and K_{2} are shifted, but that d(K_{2}) ◁ d(K_{1}). Therefore K_{2} is shifted, but not degree-maximal.

For k > 3, simply append new vertices v_{1}, …, v_{k−3} to every set in both K_{1} and K_{2} of the previous example, and order the vertices v_{1} < ⋯ < v_{k−3} < 1 < ⋯ < 10.

Combining Propositions 9.2 and 9.3, and Example 9.4, we see that the degree sequences of shifted families include the maximal elements of the order ideal of k-realizable partitions, but only when k = 2 is this inclusion an equality.

10. Numerology: Spectra and h-triangles of shifted complexes

In this section we compare two natural isomorphism invariants of shifted simplicial complexes – their h-triangle as defined by Björner and Wachs [4, 5] on the one hand, and their Laplacian spectra (or equivalently their degree sequences, by Theorem 1.1) on the other. We will describe the circumstances under which either of these sets of data determine one another. Throughout, some details are omitted for the sake of brevity.

The h-triangle was defined by Björner and Wachs for arbitrary simplicial complexes [4, Definition 3.1], but we will use the following formulation, valid only for shifted complexes (see [4, Theorem 3.4] and [5, Corollary 11.4]): If K is a shifted simplicial complex, then

(10.1)  h_{k,i}(K) = |{facets F ∈ K: |F | = k, init(F) = k − i}|,

where

init(F) = min{r: r ∉ F } − 1

is the length of the largest “initial segment” of a set of positive integers F, and is 0 if there is no initial segment (i.e., 1 ∉ F). For a pure (d − 1)-dimensional shifted complex, then clearly the only non-zero entries of the h-triangle are {h_{d,i}: i = 0, …, d} and comprise the usual h-vector.

The following example shows that the h-triangle of a shifted complex does not determine its spectra, even for pure shifted complexes, in any positive dimension. Example 10.1. We construct, for any k ≥ 2, two pure (k − 1)-dimensional shifted complexes with the same h-triangle, but different spectra.

Let K_{0} be the pure (k − 1)-dimensional shifted complex on vertex set [k + 3] whose facets consist of all k-sets that precede either A_{1} = [k − 2] ∪ {k, k + 3} or A_{2} = [k − 2] ∪ {k + 1, k + 2} in the componentwise partial order ≤_{P}. Let K_{1} = K_{0} ˙∪ {A_{1}} and K_{2} = K_{0} ˙∪ {A_{2}}. Clearly, K_{1} and K_{2} are shifted. It is also easy to check, by Equation (10.1), that K_{1} and K_{2} have the same h-triangle, but that, by Theorem 1.1, they have different spectra.

The reverse situation, how much information about the h-triangle of a shifted complex is conveyed by its spectra, depends upon the dimension of the complex.

In dimension 1, Ruch and Gutman showed that the degree sequence of a degreemaximal graph completely determines the graph up to isomorphism [30, p. 290]. By Proposition 9.2 and Theorem 1.1, then the spectra of a shifted graph determine the graph up to isomorphism, and hence determine the h-triangle.

For 2-dimensional shifted simplicial complexes, the spectra do not determine the complex up to isomorphism, but they do determine the h-triangle, as the following example (found using Stembridge’s MAPLE package posets [31]) and proposition show. Example 10.2. We construct a pair of non-isomorphic shifted 2-dimensional complexes with the same spectra.

Let K_{1} be the simplicial complex on vertex set [9] consisting of: all subsets of [9] with 2 or fewer elements; the five 3-sets (omitting set brackets and commas) 168, 239, 248, 267, 457; and all 3-subsets of [9] that precede one of these five 3-sets in the componentwise partial order ≤_{P}. Let K_{2} be the simplicial complex on vertex set [9] consisting of: all subsets of [9] with 2 or fewer elements; the four 3-sets 149, 258, 367, 456; and all 3-subsets of [9] that precede one of these four 3-sets in the componentwise partial order ≤_{P}. It is easy to see that K_{1} and K_{2} are shifted, and not hard to see that they are not isomorphic. But one may also check that d_{2}(K_{1}) = d_{2}(K_{2}), and thus, by Theorem 1.1, that K_{1} and K_{2} have the same spectra. Proposition 10.3. The spectra of a 2-dimensional shifted complex determine its h-triangle.

Proof (Sketch). A series of routine exercises show that Equation (10.1) implies h_{3,0} = 1, h_{0,0} = h_{1,0} = h_{2,0} = 0, h_{3,1} = |{v: deg_{2}(K, v) > 0}| − 3 = (d_{2})_{1}^{T} − 3 = (s′_{1})_{1} − 3, and h_{2,1} + h_{3,1} = |{v: deg_{1}(K, v) > 0}| − 3 = (d_{1})_{1}^{T} − 3 = (s′_{0})_{1} − 3. Combining Theorem 3.3 with [4, Corollary 4.2], we see that h_{j,j} is the multiplicity of 0 in s_{j−1}^{tot}, for j = 1, 2, 3. Finally, from Equation (10.1), one may easily verify that h_{3,0} + h_{3,1} + h_{3,2} + h_{3,3} equals the number of parts (including 0’s) of s_{2}^{tot}. □

Finally, the following example shows how, for 3-dimensional shifted simplicial complexes, the spectra do not even determine the h-triangle. Example 10.4. We construct a pair of shifted 3-dimensional complexes with the same spectra, but different h-triangles.

Let F_{11} = {1, 3, 6, 8}, F_{12} = {2, 4, 5, 7}, F_{21} = {1, 2, 7, 8}, and F_{22} = {3, 4, 5, 6}. Also let K_{0} be the simplicial complex on vertex set [8] consisting of: all subsets of [8] with 3 or fewer elements; and all 4-subsets of [8] that precede one of F_{11}, F_{12}, F_{21}, or F_{22} in the componentwise partial order ≤_{P}. Let K_{1} = K_{0} ˙∪ {F_{11}, F_{12}} and K_{2} = K_{0} ˙∪ {F_{21}, F_{22}}. It is easy to see that K_{1} and K_{2} are shifted. It is also easy to see, by Theorem 1.1, that K_{1} and K_{2} have the same spectra, but, by Equation (10.1), different h-triangles.

We now outline how, on the other hand, the spectra of a pure shifted complex naturally refine its f-vector and h-vector. Definition 10.5. For a simplicial complex K, and for λ one of its possible eigenvalues, let f_{j−1}^{λ} denote the multiplicity of eigenvalue λ in s_{j−1}^{tot}(K). Similarly, for λ ≠ 0, let (f′)_{j−1}^{λ} denote the multiplicity of λ in s′_{j−1}(K).

Note that the f_{j−1}^{λ} are a refinement of the f-vector, in that

(10.2)  ∑_{λ} f_{j−1}^{λ}(K) = dim C_{j−1}(K; ℝ) = f_{j−1}(K).

Also note that Equation (3.6) implies

(10.3)  f_{j−1}^{λ} = (f′)_{j−1}^{λ} + (f′)_{j−2}^{λ}

for λ ≠ 0.

Recall the h-vector of a (d − 1)-dimensional simplicial complex is defined from the f-vector by

∑_{i=0}^{d} h_{i}(x + 1)^{d−i} = ∑_{j=0}^{d} f_{j−1}x^{d−j}.

We similarly define h_{i}^{λ} from f_{j−1}^{λ} and, for λ ≠ 0, (h′)_{i}^{λ} from (f′)_{j−1}^{λ} by

∑_{i=0}^{d} h_{i}^{λ}(x + 1)^{d−i} = ∑_{j=0}^{d} f_{j−1}^{λ}x^{d−j}

and

∑_{i=0}^{d−1}(h′)_{i}^{λ}(x + 1)^{(d−1)−i} = ∑_{j=0}^{d−1}(f′)_{j−1}^{λ}x^{(d−1)−j}.

Since h_{i} and each h_{i}^{λ} are defined from f_{j−1} and f_{j−1}^{λ} by the exact same linear equations, the linear relations (10.2) imply the corresponding relations

(10.4)  ∑_{λ} h_{i}^{λ} = h_{i}.

Proposition 10.6. For λ ≠ 0,

h_{i}^{λ} = \begin{cases}(h′)_{i}^{λ} & if i ≤ d − 1 \\ 0 & if i = d \end{cases} .

In other words, the refined h^{λ}-vector (h_{0}^{λ}, …, h_{d}^{λ}) is just the refined (h′)^{λ}-vector ((h′)_{0}^{λ}, …, (h′)_{d−1}^{λ}) with an extra zero at the end. The proof of Proposition 10.6 consists of routine summation manipulations using the definitions of h_{i}^{λ} and (h′)_{i}^{λ}, and Equation (10.3). Theorem 10.7. Let K be a pure (d − 1)-dimensional shifted simplicial complex, and 0 ≤ i ≤ d − 1. Then (h′)_{i}^{λ}(K) equals the cardinality of the set

S = {facets F ∈ K: λ ∈ F, λ+1 ∉ F, F \{λ}∪{λ+1} ∉ K, init(F \{λ}) = d−i−1}.

In particular, (h′)_{i}^{λ}(K) is nonnegative.

Proof (Sketch). It is not hard to see that, because K is shifted,

|S| = |{facets F ∈ K: λ ∈ F, λ + 1 ∉ F, init(F \{λ}) = d − i − 1}|
− |{facets H ∈ K: λ ∉ H, λ + 1 ∈ H, init(H) = d − i − 1}|.

It thus suffices to find a way to build K one facet at a time, such that when facet F is added: if either λ, λ + 1 ∈ F or λ, λ + 1 ∉ F, then (h′)^{λ} is unchanged; if λ ∈ F and λ + 1 ∉ F, then (h′)^{λ} just increases by one in the ith component, where init(F \{λ}) = d − i − 1; and if λ ∉ F and λ + 1 ∈ F, then (h′)^{λ} just decreases by one in the ith component, where init(F) = d − i − 1.

It is straightforward to verify that these conditions are met when facets are added to K in the reverse lexicographic order because this order is a shelling order [5, Corollary 11.4]. It is necessary to use Theorem 1.1 here, but in the following equivalent formulation: For any shifted family K, the multiplicity of λ in s(K) equals the number of sets A of K such that λ ∈ A, λ+1 ∉ A, and A\{λ}∪{λ+1} ∉ K. □

Corollary 10.8. For a pure (d − 1)-dimensional shifted simplicial complex, the numbers h_{i}^{λ} nonnegatively refine the usual h-vector; i.e., ∑_{λ} h_{i}^{λ} = h_{i} for all i, and h_{i}^{λ} ≥ 0 for all λ and i.

Proof. Combine Theorem 10.7, Equation (10.4), and Proposition 10.6. □

11. Acknowledgements

The authors thank Alan Edelman for Remark 3.5, Eric Babson for Proposition 6.7, Xun Dong for the proof of Proposition 8.4, John Stembridge for help in using his MAPLE package posets to find Example 10.2, and the referee for suggested improvements.

References

1. R. M. Adin, Counting colorful multi-dimensional trees, Combinatorica 12 (1992), 247–260.

2. W. N. Anderson and T. D. Morley, Eigenvalues of the Laplacian of a graph, Univ. of Maryland Tech. Report TR-71-45 (1971); Linear and Multilinear Algebra 18 (1985), 141-145.

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

4. A. Björner and M. Wachs, Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc. 348 (1996), 1299–1327.

5. , Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), 3945–3975.

6. F. Chung, The Laplacian of a hypergraph, DIMACS Ser. in Discrete Math. Theoret. Comput. Sci. 10 (1993), 21-36.

7. , Spectral Graph Theory, CBMS Reg. Conf. Ser. in Math. 92, Amer. Math. Soc., Providence, RI, 1997.

8. V. Chvatal and P. L. Hammer, Aggregation of inequalities in integer programming, Studies in integer programming (P. Hammer, et. al., eds.); Ann. Discrete Math. 1 (1977), 145–162.

9. D. M. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs. Theory and Applications, 3rd ed., Johann Ambrosius Barth, Heidelberg, 1995.

10. X. Dong and M. Wachs, Combinatorial Laplacian of the matching complex, Electron. J. Combin. 9 (2002), #R17, 11 pp.

11. B. Eckmann, Harmonische Funktionen und Randwertaufgaben in einem Komplex, Comment. Math. Helv. 17 (1945), 240-255.

12. I. Faria, Multiplicity of integer roots of polynomials of graphs, Linear Algebra Appl. 229 (1995), 15–35.

13. M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973), 298-305.

14. R. Forman, Combinatorial differential topology and geometry, New perspectives in algebraic combinatorics, Math. Sci. Res. Inst. Publ. 38, 1999.

15. J. Friedman, Computing Betti numbers via combinatorial Laplacian, Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, 1996), ACM, New York, 1996, pp. 386–391.

16. J. Friedman and P. Hanlon, On the Betti numbers of chessboard complexes, J. Algebraic Combin. 8 (1998), 193–203.

17. S. Gershgorin, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk 7 (1931), 749-754.

18. R. Grone, Eigenvalues and the degree sequence of graphs, Linear and Multilinear Algebra 39 (1995), 133-136.

19. R. Grone and R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math. 7 (1994), 221–229.

20. P. L. Hammer and A. K. Kelmans, Laplacian spectra and spanning trees of threshold graphs, Discrete Appl. Math. 65 (1996), 255–273.

21. G. Kalai, Enumeration of Q-acyclic simplicial complexes, Israel J. Math. 45 (1983), 337–351.

22. G. Kirchhoff, Über de Auflösung der Gleichungen auf welche man bei der Untersuchen der linearn Vertheilung galvanischer Ströme gefüht wird, Ann. Der Phys. und Chem. 72 (1847), 495-508.

23. W. Kook, V. Reiner, and D. Stanton, Combinatorial Laplacians of matroid complexes, J. Amer. Math. Soc. 13 (2000), 129–148.

24. I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd ed., Oxford University Press, New York, 1995.

25. A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and its Applications, Academic Press, New York, 1979.

26. R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199 (1994), 381–389.

27. , Laplacian matrices of graphs: a survey Linear Algebra Appl. 197/198 (1994), 143– 176.

28. J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley, Menlo Park CA, 1984.

29. U. Peled and M. Srinivasan, The polytope of degree sequences, Linear Algebra Appl. 114/115 (1989), 349–377.

30. E. Ruch and I. Gutman, The branching extent of graphs, J. Combin. Inform. System Sci. 4 (1979), 285–295.

31. J. Stembridge, The MAPLE package posets, available at

    http://www.math.lsa.umich.edu/~jrs/maple.html#posets.

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

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

School of Mathematics, University of Minnesota, Minneapolis, MN 55455

   E-mail address: reiner@math.umn.edu