%-----------------------------------------------------------------------
% Beginning of journal.top
%-----------------------------------------------------------------------
%
% This is a journal topmatter template file for use with AMS-LaTeX.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Replace amsart by the documentclass for the target journal.
%\documentclass{tran-l}
\documentclass{amsart}
\usepackage{amssymb,amscd,amsthm,verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% What we had before
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%\documentclass{amsart}
%%%\usepackage{amssymb,amscd,amsthm,verbatim}
%%%
%%%% "plain" theorem style; all of these share the same counter
%%%\newtheorem{proposition}{Proposition}[section]
%%%\newtheorem{theorem}[proposition]{Theorem}
%%%\newtheorem{corollary}[proposition]{Corollary}
%%%\newtheorem{lemma}[proposition]{Lemma}
%%%\newtheorem{conjecture}[proposition]{Conjecture}
%%%\newtheorem{question}[proposition]{Question}
%%%%restatements
%%%\newtheorem*{restate-main}{Theorem \ref{main-theorem}}
%%%\newtheorem*{restate-GM}{Conjecture \ref{GM-conjecture}}
%%%
%%%\theoremstyle{definition}
%%%\newtheorem{remark}[proposition]{Remark}
%%%\newtheorem{definition}[proposition]{Definition}
%%%\newtheorem{example}[proposition]{Example}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% If your version of amsart.cls is version 1.2 (before December 1999),
% uncomment the following definition.
%\renewcommand{\subjclassname}{%
% \textup{2000} Mathematics Subject Classification}
% Update the information and uncomment if AMS is not the copyright holder.
%\copyrightinfo{2000}{American Mathematical Society}
% "plain" theorem style
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
%restatements
\newtheorem*{restate-main}{Theorem \ref{main-theorem}}
\newtheorem*{restate-GM}{Conjecture \ref{GM-conjecture}}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{claim}{Claim}
\newtheorem{step}{Step}
\numberwithin{equation}{section}
\newcommand{\id}{\mathrm{id}}
\newcommand{\s}{\mathbf{s}}
\newcommand{\stot}{\mathbf{s}^{tot}}
\newcommand{\dd}{\mathbf{d}}
\newcommand{\aaa}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\f}[2]{f^{#1}_{#2}}
\newcommand{\fp}[2]{(f')^{#1}_{#2}}
\newcommand{\h}[2]{h^{#1}_{#2}}
\newcommand{\hp}[2]{(h')^{#1}_{#2}}
\newcommand{\integers}{\mathbb Z}
\newcommand{\reals}{\mathbb R}
\newcommand{\rationals}{\mathbb Q}
\newcommand{\skel}[1]{^{[#1]}}
\newcommand{\collC}{\mathcal C}
\newcommand{\calS}{\mathcal S}
\newcommand{\disun}{\mathbin{\dot{\cup}}} %from Mark Purtill
\newcommand{\condns}[2]{\substack{#1 \\ #2}}
\newcommand{\maj}{\trianglelefteq}
\newcommand{\majneq}{\triangleleft}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand \naturals{{\mathbb N}}
\newcommand{\balpha}{\boldsymbol{\alpha}}
\newcommand{\bbeta}{\boldsymbol{\beta}}
\newcommand{\blambda}{\boldsymbol{\lambda}}
\newcommand{\bmu}{\boldsymbol{\mu}}
%\newcommand \im{\mathrm{im}}
%\newcommand \Hom{\mathrm{Hom}}
%\newcommand \mult{\mathrm{mult}}
\newcommand \del{\mathrm{del}}
\newcommand \link{\mathrm{link}}
%\newcommand{\degr}{\mathrm{deg}}
%\newcommand{\init}{\mathrm{init}}
%
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\mult}{mult}
%\DeclareMathOperator{\del}{del}
%\DeclareMathOperator{\link}{link}
\DeclareMathOperator{\degr}{deg}
\DeclareMathOperator{\init}{init}
\DeclareMathOperator{\Trace}{Trace}
\begin{document}
\title{Shifted simplicial complexes are Laplacian integral}
% Remove or comment out any unused author tags.
% author one information
\author{Art M. Duval}
\address{Department of Mathematical Sciences\\
University of Texas at El Paso\\
El Paso, TX 79968-0514}
\email{artduval@math.utep.edu}
% author two information
\author{Victor Reiner}
\address{School of Mathematics\\
University of Minnesota\\
Minneapolis, MN 55455}
\email{reiner@math.umn.edu}
\thanks{Second author partially supported by a Sloan Foundation Fellowship,
and NSF grant DMS-9877047.}
% Use this \subjclass if you are using amsart version 2.0 (December 1999).
\subjclass[2000]{Primary 15A42; Secondary 05C65, 05C50, 05E99}
% Use this one if you are using an older version of amsart.
%\subjclass{}
\date{May 3, 2000 and, in revised form, August 10, 2000.}
\keywords{Laplace operator, Laplacian, simplicial complex, spectra}
\begin{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.
\end{abstract}
\maketitle
%-----------------------------------------------------------------------
% End of journal.top
%-----------------------------------------------------------------------
%\newcounter{alphcount}
%\renewcommand{\thealphcount}{(\alph{alphcount})}
%\newenvironment{alph-list}{\begin{list}{\thealphcount}{\usecounter{alphcount}}}%
% {\end{list}}
%\newcounter{romcount}
%\renewcommand{\theromcount}{(\roman{romcount})}
%\newenvironment{rom-list}{\begin{list}{\theromcount}{\usecounter{romcount}}}%
% {\end{list}}
\section{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 \cite{Kirchhoff}
in his study of electrical networks, and his celebrated matrix-tree
theorem (see e.g.\ \cite{Kalai}).
The spectra of graph Laplacians gained attention in the late 1960's
through the independent work of Anderson and Morley \cite{AndersonMorley},
Fiedler \cite{Fiedler}, and Kelmans (see references in \cite{HammerKelmans}).
For comprehensive bibliographies on graph Laplacians
see \cite{Merris-survey} and \cite{Chung-book},
and for other aspects of spectra of graphs see \cite{CDS}.
The Laplace operator $L(G)$ for a graph $G$
is defined as follows: $L(G)= \partial \partial^T$, where
$\partial$ is the {\it vertex-edge incidence matrix} having
\begin{itemize}
\item
rows indexed by the vertices of $G$,
\item
columns indexed by the edges of $G$,
\item
the column corresponding to a particular
edge containing a $+1$ and $-1$ in the rows that corresponding to that
edge's endpoints.
\end{itemize}
Note that this map $\partial$ coincides with the {\it boundary map}
$\partial_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
$\partial^T \partial$ sometimes called the {\it 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 {\it simplicial complexes} (see e.g.\ \cite{Munkres}). A simplicial
complex $K$ has associated to it chain groups $C_i(K)$ and boundary maps
$\partial_i\colon C_i(K) \rightarrow C_{i-1}(K)$ satisfying
$\partial_{i+1} \partial_i = 0$, which are used to define
and compute its {\it homology groups}
$H_i(K) :=\ker \partial_i / \im \partial_{i+1}$.
The maps $\partial_i \partial_i^T$ and $\partial_i^T \partial_i$
naturally arise in a finite-dimensional version of Hodge theory first explicitly
stated by Eckmann \cite{Eckmann}. He observed that
when working with real coefficients, so that $C_i(K)$ is
an $\reals$-vector space, the operator
$$
L_i=\partial_{i+1} \partial_{i+1}^T
+\partial_i^T \partial_i
$$
has the property that its kernel $\ker L_i$ (the {\it
harmonic $i$-chains}) span a subspace isomorphic to $H_i(K)$
(see Theorem \ref{Hodge-theorem} below).
In other words, $H_i(K)$ is isomorphic to the $0$-eigenspace of $L_i$.
Based on this fact, Friedman \cite{Friedman} 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 $\partial_i$
and $\partial_{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 {\it
chessboard complexes}, appeared to have $L_i$ with all integer spectra,
which he and Hanlon \cite{FriedmanHanlon} 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 {\it matching complexes }\cite{DongWachs} and {\it matroid
complexes }\cite{KookReinerStanton}.
We should mention that Chung \cite{Chung}
also considered a variant of the maps $L_i$ (see Remark \ref{Chung-remark}
below), and that the maps $\partial_i \partial_i^T$
arose in a beautiful generalization of Kirchhoff's matrix-tree theorem to
higher-dimensional simplicial complexes by Kalai \cite{Kalai}; see also
\cite{Adin}.
The current paper arose from two motivations. One was our
suspicion that the family of {\it shifted} simplicial
complexes might also have integer Laplacian spectra. These simplicial
complexes arise, among other places,
in work of Bj\"orner and Kalai \cite{BjornerKalai}
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 \ref{GM-conjecture} and
Section \ref{degree-maximal-section} below).
Our main result confirms that shifted complexes indeed have integer
Laplacian spectra, generalizing a result for {\it degree-maximal} or
{\it threshold} graphs due originally to Kelmans
(see \cite[Corollary 4.1]{HammerKelmans}). Kelmans' result
was rediscovered independently and elegantly reformulated by Merris
\cite[Theorem 2]{Merris}, 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
$\partial_i \partial_i^T$ (see Section \ref{define-Laplacians}
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 {\it $k$-family}
(or {\it $k$-uniform hypergraph}) $K$, which we think of as being
the collection of $(k-1)$-dimensional simplices in some shifted simplicial
complex (Section \ref{define-Laplacians} shows why it suffices
to look at families instead of simplicial complexes).
\begin{theorem}
\label{main-theorem}
For any shifted $k$-family $K$, let $\s=(s_1 \geq s_2 \geq \ldots)$
denote the weakly decreasing rearrangement of the non-zero eigenvalues in the
spectrum of $\partial_{k-1} \partial_{k-1}^T$.
Then we have
$$
\s = \dd^T
$$
where here $\dd^T$ denotes the conjugate partition to
the degree sequence $\dd$ of vertices with respect
to the $k$-sets in $K$.
\end{theorem}
The proof of Theorem \ref{main-theorem} is in Section
\ref{main-theorem-section}.
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 {\it all} complexes. This led us to the following
conjecture, generalizing a conjecture of Grone and Merris
\cite[Conjecture 2]{GroneMerris} for graphs. As with the above theorem,
it is phrased in terms of $\partial_i \partial_i^T$ rather than $L_i$,
and for $k$-families rather than simplicial complexes.
\begin{conjecture}
\label{GM-conjecture}
For any $k$-family $K$, the spectrum $\s$ defined as in the previous
theorem satisfies
$$
\s \maj \dd^T
$$
with equality if and only if $K$ is isomorphic to
a shifted family.
\end{conjecture}
\noindent
Here $\maj$ denotes the majorization partial order,
that is
$$
\begin{aligned}
s_1 &\leq d_1^T \\
s_1+s_2 &\leq d_1^T+d_2^T \\
s_1+s_2+s_3 &\leq d_1^T+d_2^T+d_3^T\\
&\vdots
\end{aligned}
$$
We think that the evidence for Conjecture \ref{GM-conjecture} is
quite strong, and is presented in Sections \ref{conjecture-section}
and \ref{second-inequality-for-graphs-section}.
The paper is structured as follows.
Section \ref{notation} establishes
some notation and terminology for simplicial complexes
and number partitions.
Section \ref{define-Laplacians} 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 \ref{constructions} 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 \ref{main-theorem} or
in the evidence for Conjecture \ref{GM-conjecture}.
In particular, Theorem \ref{Kc-spectrum-theorem},
Corollary \ref{spectra-Alexander-dual} and Theorem \ref{spectra-join}
appear to be new.
Section \ref{main-theorem-section} proves Theorem \ref{main-theorem}.
Section \ref{conjecture-section} re-states Conjecture \ref{GM-conjecture},
and proves various partial results as evidence for it. In particular,
it is shown that
\begin{itemize}
\item
the first inequality $s_1 \leq d_1^T$
in the conjectured majorization holds (Proposition \ref{first-GM-inequality}),
\item
if the
majorization inequality in the conjecture holds, then the second
assertion about the case of equality follows (Proposition \ref{half-implies-other-half}), and
\item
the conjecture is consistent with several of the constructions
of Section \ref{constructions} (Propositions
\ref{consistent-with-constructions} and \ref{consistent-with-joins}).
\end{itemize}
Section \ref{second-inequality-for-graphs-section} provides further
evidence for Conjecture \ref{GM-conjecture} by sketching the
proof of the second inequality of the conjectured majorization for the
case of graphs.
Section \ref{easy-bounds} proves some other easy bounds
on the spectra that are analogous to ones known in the case
of graphs.
Section \ref{degree-maximal-section} 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 \ref{maximal-shifted}). This
generalizes the case $k=2$ considered by Merris \cite{Merris}, who
refers to shifted graphs as {\it degree-maximal graphs}.
Section \ref{numerology} 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\"orner 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.
\section{Notation for simplicial complexes and partitions}
\label{notation}
Let $[n]$ denote the set $\{1,2,\ldots,n\}$.
An {\it abstract simplicial complex} $K$ on vertex set $[n]$ is
a collection of subsets of $[n]$ (called {\it faces} or {\it simplices})
which is closed under inclusion,
that is, $F \in K$ and $F' \subset F$ implies $F' \in K$. Note that
we do not assume all of the singletons ${v}$ for $v \in [n]$ are
faces of $K$, nor do we assume that the empty set $\emptyset$ is
a face of $K$. In particular, there is a distinction between
the empty complex $K=\emptyset$ and the complex $K=\{\emptyset\}$
which contains the empty set and no other faces.
The cardinality of a face $F$ is denoted $\abs{F}$, and its {\it dimension}
is $\abs{F}-1$. The dimension of the whole complex $K$ is the maximum dimension
of a face in $K$.
A face $F$ is a {\it facet} of complex $K$ if it is maximal in $K$, i.e.,
$\dim F = \dim K$. A complex is {\it pure} if all of its facets have the
same dimension.
The set
$$
K_j:=\{F \in K\colon \dim K = j\}
$$
forms a family of $(j+1)$-subsets, or a $(j+1)$-{\it 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 {\it $f$-vector} of $K$ is the
sequence
$$
f(K) := (f_{-1}(K), f_0(K), f_1(K),\ldots)
$$
where $f_j(K) := \abs{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:
$$
\degr_j(K,v) := \abs{\{F \in K\colon \dim F = j,\ v \in F\}}.
$$
More generally, we define for a $k$-family $K$ on $[n]$ and any set
$A \subseteq [n]$,
$$
\degr(K,A):=\abs{\{F \in K\colon A \subseteq F\}}.
$$
The {\it $j$-degree sequence} of a simplicial complex $K$ on vertex
set $[n]$ is the weakly decreasing rearrangement $\dd_j(K)$ of the sequence
$\degr_j(K,1),\ldots,\degr_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.
\begin{definition}
If $F=\{f_1<\cdots \dim K$ is always the trivial partition with no parts.
\end{itemize}
We will use the following two operations on partitions $\blambda,
\bmu$:
\begin{itemize}
\item
$\blambda \cup \bmu$ is the $\circeq$-equivalence class
whose non-zero parts are the multiset
union of the non-zero parts of $\blambda$ and $\bmu$, arranged in weakly
decreasing order, and
\item
$\blambda + \bmu$ has parts $\lambda_i + \mu_i$,
i.e.\ it is the sum of $\blambda + \bmu$ as vectors.
\end{itemize}
When $\blambda = 1^{l_1} 2^{l_2} \cdots$ and
$\bmu = 1^{m_1} 2^{m_2} \cdots$ happen to satisfy $m_i \leq l_i$
for each $i$, we define their {\it difference} $\blambda - \bmu$ by
$\blambda - \bmu = 1^{l_1-m_1} 2^{l_2-m_2} \cdots$.
The {\it dominance} or {\it 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}
\blambda &= (\lambda_1,\ldots,\lambda_r)\\
\bmu&= (\mu_1,\ldots,\mu_s)
\end{aligned}
$$
two {\it weakly decreasing} sequences of real numbers with
$\sum_{i=1}^s \mu_s = \sum_{i=1}^r \lambda_i$, we say that
$\blambda$ {\it majorizes} $\bmu$ (written $\bmu \maj \blambda$) if
$$
\sum_{i=1}^k \mu_i \leq \sum_{i=1}^k \lambda_i
\text{ for }k \leq \min(r,s).
$$
We also extend the notation $\blambda \cup \bmu$ to
the setting of weakly decreasing sequences of real numbers,
and similarly extend the difference notation $\blambda - \bmu$ in the
case where the multiplicity of each real number
in $\bmu$ is at most the same multiplicity in $\blambda$.
It is easy to check (see \cite[\S I.1, formulas (1.8, 1.11)]{Macdonald})
that conjugation has the following properties with respect to the above
operations on partitions and dominance order:
\begin{lemma}\label{partition-transpose}
If $\blambda$ and $\bmu$ are two partitions, then
\begin{enumerate}%\begin{alph-list}
\item%\label{union-transpose}
$(\blambda \cup \bmu)^T = \blambda^T + \bmu^T$; and
\item%\label{sum-transpose}
$(\blambda + \bmu)^T = \blambda^T \cup \bmu^T$;
\item%\label{majorization-transpose}
$\bmu \maj \blambda \Leftrightarrow \blambda^T \maj \bmu^T$ \qed
\end{enumerate}%\end{alph-list}
\end{lemma}
\section{Defining spectra of Laplacians}
\label{define-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 (\cite[Chapter 1, \S 5, 8]{Munkres}) that for each $i \geq -1$,
the vector space $C_i(K;\reals)$ of
{\it (augmented) oriented simplicial $i$-chains} on
$K$ with coefficients in $\reals$ has as $\reals$-basis
the set of symbols $[v_0,\ldots,v_i]$ where $F=\{v_0,\ldots,v_i\}$
is a face of $K$, and where $v_0 < \ldots < v_i$ in the usual
ordering on $[n]$. The {\it simplicial boundary map}
$$
\partial_i\colon C_i(K;\reals) \rightarrow C_{i-1}(K;\reals)
$$
is then defined $\reals$-linearly by extending the following
map on basis elements:
$$
\partial_i [v_0,\ldots,v_i] =
\sum_{j=0}^i (-1)^j[v_0,\ldots,\hat{v_{j}},\ldots,v_i].
$$
After verifying that
\begin{equation}
\label{boundarysquared-is-zero}
\partial_i \partial_{i+1}=0
\end{equation}
\noindent
one can define the {\it (reduced) homology group}
$$
\tilde{H}_i(K;\reals) := \ker \partial_i / \im \partial_{i+1}.
$$
Endow $C_i(K;\reals)$ with a positive definite inner product
$\langle \cdot, \cdot \rangle$ that makes the above basis orthonormal.
This allows one to identify the $\reals$-dual space
$$
C^i(K;\reals) := \Hom_\reals(C_i(K;\reals), \reals) \cong C_i(K;\reals)
$$
via this inner product. Under this identification, the
{\it coboundary map}
$$
\delta_i\colon C^i(K;\reals) \rightarrow C^{i+1}(K;\reals)
$$
is simply the {\it adjoint} $\partial_{i+1}^*$ of the boundary map
$\partial_{i+1}$ with respect to this inner product.
\begin{definition}
Define three operators $C_i(K;\reals) \rightarrow C_i(K;\reals)$
using these boundary and coboundary maps:
$$
\begin{aligned}
L'_i &:=\partial_{i+1} \partial_{i+1}^* \\
L''_i &:=\partial_i^* \partial_i \\
L_i&:=L'_i + L''_i = \partial_{i+1} \partial_{i+1}^*
+\partial_i^* \partial_i
\end{aligned}
$$
The operator $L_i$ is usually called the
{\it $i$-dimensional Laplace operator
of $K$}. Its spectrum will be our main object of study.
\end{definition}
We can be somewhat more explicit about the maps $L'_i, L''_i$
after introducing some notation. Given a set $F \subseteq [n]$
with elements $v_0 < \ldots < v_i$, let $[F]$ denote the
oriented simplicial $i$-chain $[v_0, \ldots, v_i]$. Given
two sets $F,F'$ of the same cardinality, let
$$
F \vartriangle F' := (F \backslash F') \cup (F' \backslash F)
$$
denote their symmetric difference. When $\abs{F \vartriangle F'}=2$,
say $F \vartriangle F' = \{i,j\}$ with $i \dim K$.
\begin{remark}
There are well-definedness issues for the above spectra,
since the definition of the boundary map $\partial_i$
involves a choice of ordering of the vertices in the simplicial
complex, and also the matrix representing $\partial_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 $\partial_i$ by $\alpha_i \circ \partial_i \circ \beta_i$
for some operators $\alpha_i, \beta_i$ on $C_i(K;\reals), C_{i+1}(K,\reals)$,
respectively. These operators are represented
by signed permutation matrices with respect to the bases of simplices,
so that they are invertible and satisfy
$\alpha_i^*=\alpha_i^{-1}$ and $\beta_i^*=\beta_i^{-1}$.
Consequently, this has the effect of conjugating $L_i'(K), L''_i(K)$
by $\alpha_i, \beta_i$, respectively, which will not affect their
spectra.
\end{remark}
The combinatorial Laplace operators $L_i$ for simplicial complexes
(and cell complexes more generally) were introduced by Eckmann;
see \cite{Forman} 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.\ \cite{Friedman} for a proof).
Let $(C_\cdot, \partial_\cdot)$ be a complex of $\reals$-vector
spaces, i.e.\ $\partial_i\colon C_i \rightarrow C_{i-1}$ is an $\reals$-linear
map and $\partial_i \partial_{i+1}=0$. Endow each $C_i$
with a positive definite inner product, so that one can
identify $C^*_i : = \Hom_\reals(C_i, \reals) \cong C_i$.
This allows one to define as above the adjoint maps
$$
\partial_i^*\colon C_{i-1} \rightarrow C_i
$$
and the Laplacians
$$
L_i = \partial^*_i \partial_i + \partial_{i+1} \partial_{i+1}^*\colon
C_i \rightarrow C_i.
$$
\begin{theorem}
\label{Hodge-theorem}
There is an isomorphism of $\reals$-vector spaces
$$
\tilde{H}_i(C_\cdot,\partial_\cdot)
:= \ker \partial_i/ \im \partial_{i+1}
\cong \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 \partial_{i+1} \oplus \ker L_i \oplus \im \partial_i^*
$$
in which the first two summands comprise the $i$-cycles $\ker \partial_i$,
and the first summand comprises the $i$-boundaries. \qed
\end{theorem}
Note that even though $\s'_i$ is defined to
be the spectrum of $L'_i = \partial_{i+1} \partial_{i+1}^*$
which acts on $C_i(K;\reals)$, its non-zero parts
(i.e.\ its $\circeq$-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 $\partial_{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
$\partial_K$ will always refer to the boundary map $\partial_{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 $\phi^* \phi$ coincide with those of $\phi \phi^*$
(see e.g.\ \cite[Chapter 9, A.1.a, p.\ 216]{MarshallOlkin}). Consequently, we have
$$
\s''_i \circeq \s_{i-1}'.
$$
For this reason, we will sometimes use the simpler notation
$\s$ to refer to the $\circeq$-equivalence class of
$\s'$ and $\s''$ (as we did in the Introduction).
The fact that $\partial_i \partial_{i+1} = 0$ immediately
implies that
$$
L'_i \circ L''_i = 0 = L''_i \circ 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,
\begin{equation}\label{s-union-minus}
%\begin{array}{lll}
\begin{aligned}
\stot_i &\circeq \s'_i \cup \s''_{i} &&\circeq \s'_i \cup \s'_{i-1}
% \label{s-union}
\\
\s'_i& \circeq \stot_i - \s''_{i} &&\circeq \stot_i - \s'_{i-1}
%\label{s-minus}
\end{aligned}
%\end{array}
\end{equation}
\noindent
As a consequence, the information carried in the three families of
spectra
$$
\begin{aligned}
&(\stot_{-1},\stot_0,\stot_1,\ldots,\stot_{\dim K})\\
&(\s'_{-1},\s'_0,\s'_1,\ldots,\s'_{\dim K -1})\\
&(\s''_0,\s''_1,\s''_2,\ldots,\s''_{\dim K})
\end{aligned}
$$
are all equivalent, and we will feel free to phrase our
results in terms of any of the three.
\begin{remark}
\label{Chung-remark}
In \cite{Chung}, 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
$$
\partial_{i+1} \partial^*_{i+1} + \rho \,\, \partial^*_i \partial_i
$$
where $\rho$ 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.
\end{remark}
\begin{remark}
\label{singular-values}
Note that the spectrum $\s''_i$ of $\partial_i^* \partial_i$
carries the same information as the {\it singular values} of
the boundary operator $\partial_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.
\end{remark}
\section{Constructions and their effect on the spectra}
\label{constructions}
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 {\it complete} $k$-family
consisting of {\it all} $k$-subsets of $[n]$.
\begin{definition}
Define two new $k$-families derived from $K$ by
$$
\begin{aligned}
K^c &:= \binom{[n]}{k} \backslash K = \{F \subseteq [n]\colon \abs{F}=k, F \not\in K\}\\
K^* &:= \{[n] \backslash F\colon F \in K\}.
\end{aligned}
$$
\end{definition}
Note that
\begin{itemize}
\item
$K^c$ is a $k$-family,
\item
$K^*$ is an $(n-k)$-family,
\item
both of these operations are involutive: $(K^c)^c = (K^*)^* = K$, and
\item
they commute with each other: $K^{c*} = K^{*c}$.
\end{itemize}
\noindent
It is our goal to describe the effect these operations have on the
spectra $\s', \s''$ (and hence on their $\circeq$-equivalence class,
$\s$).
For the purpose of studying $K \mapsto K^*$,
regard $L''_i$ as acting on the $\abs{K}$-dimensional $\reals$-vector
space $C(K;\reals)$ having basis $\{[F]\}_{F \in K}$, and
let $\phi\colon C(K;\reals) \rightarrow C(K^*;\reals)$ be the
$\reals$-linear isomorphism defined by
$$
\phi[F] = (-1)^{\sum_{i \in F} i} [[n]\backslash F].
$$
\begin{proposition}
\textup{(}cf. \cite[Proposition 6]{KookReinerStanton}\textup{)}
For any $k$-family $K$ of subsets of $[n]$ we have
\begin{equation}
\label{K*-operator-equation}
L''(K) + \phi^{-1} L''(K^*) \phi = n \cdot \id_{C(K;\reals)}.
\end{equation}
\end{proposition}
\begin{proof}
We check Equation \eqref{K*-operator-equation} entry by entry.
The $([F],[F'])$-entry of $L''(K)$ is
$$
%\left\{
%\begin{matrix}
\begin{cases}
\abs{F} &\text{ if $F = F'$,}\\
\epsilon(F,F') & \text{ if $F, F' \in K, \abs{F \vartriangle F'}=2$,} \\
0 & \text{ otherwise. }
%\end{matrix}
%\right.
\end{cases}
$$
On the other hand, the $([F],[F'])$-entry of $\phi^{-1} L''(K^*) \phi$ is
$$
%\left\{
%\begin{matrix}
\begin{cases}
\abs{[n] \backslash F} &\text{ if $F = F'$,}\\
(-1)^{\sum_{i \in F}i + \sum_{i \in F'}i}
\epsilon([n] \backslash F, [n] \backslash F')
& \text{ if $F,F' \in K,
\abs{F \vartriangle F'}=2$,} \\
0 & \text{ otherwise. }
\end{cases}
%\end{matrix}
%\right.
$$
It is easy to see from this that the diagonal $([F],[F])$-entries
in Equation \eqref{K*-operator-equation} are correct. For the off-diagonal
$([F],[F'])$-entry, it suffices to show that
\begin{equation}
\label{sign-equality}
(-1)^{\sum_{i \in F}i + \sum_{i \in F'}i}
\epsilon(F,F') = - \epsilon([n] \backslash F, [n] \backslash F')
\end{equation}
whenever $\abs{F \vartriangle F'}=2$. To see this, let
$F \vartriangle F' =\{i,j\}$, and then it is easy to check that
$$
(-1)^{\sum_{i \in F}i \,\, + \,\, \sum_{i \in F'}i} = (-1)^{i+j}
$$
and
$$
\epsilon(F,F') \,\, \epsilon([n] \backslash F, [n] \backslash F') = (-1)^{j-i-1}
$$
which gives the desired equality \eqref{sign-equality}.
\end{proof}
We immediately deduce
\begin{theorem}
\label{K*-spectrum-theorem}
In the situation of the previous proposition, the spectra
$$
\begin{aligned}
\s''(K)&=(s_1 \geq \ldots \geq s_{\abs{K}})\\
\s''(K^*)&=(s^*_1 \geq \ldots \geq s^*_{\abs{K}})
\end{aligned}
$$
are related by
\begin{equation}
\label{K*-spectrum-equation}
s^*_i = n-s_{\abs{K}+1-i}
\end{equation}
for each $i$.
\end{theorem}
For the purposes of studying $K \mapsto K^c$, given
a $k$-family $K$ of subsets of $[n]$, regard $L'(K)$ as
acting on the $\binom{n}{k-1}$-dimensional $\reals$-vector
space $C(\binom{[n]}{k-1};\reals)$ having basis
$\{[F]\}_{F \in \binom{[n]}{k-1}}$. In the case of graphs,
the next proposition is well-known (see e.g.\ \cite{Fiedler})
and trivial, but it is not so trivial in higher dimensions,
however.
\begin{proposition}
For any $k$-family $K$ of subsets of $[n]$ we have
\begin{equation}
\label{Kc-operator-equation}
L'(K) + L'(K^c) = L'\left( \binom{[n]}{k} \right)
\end{equation}
and all three operators $L'(K), L'(K^c), L'( \binom{[n]}{k})$
pairwise commute.
\end{proposition}
\begin{proof}
Equation \eqref{Kc-operator-equation} is immediate from
the description of $L'$ given in Equation \eqref{explicit-L'} 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 \ref{main-theorem}
(whose proof does not rely on this proposition!)
that the space $V:=C(\binom{[n]}{k-1};\reals)$
decomposes into a direct sum
$$
V = V_0 \oplus 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 $\langle \cdot , \cdot \rangle$,
it must be that $V_n = (V_0)^\perp$, so that $L'(\binom{[n]}{k})$
acts by scalars both on $V_0$ and on $(V_0)^\perp$.
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)^\perp$, since it implies
$L'(K)$ carries {\it all} of $V$ into $(V_0)^\perp$:
$$
v \in V, v_0 \in V_0 \,\, \Rightarrow \,\,
\langle L'(K)(v), v_0 \rangle =
\langle v, L'(K)(v_0) \rangle =
\langle v, 0 \rangle =
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)^\perp$,
$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'\left(\binom{[n]}{k}\right) =
\ker( \partial_{k-1} \circ \partial_{k-1}^* )
= \ker( \partial_{k-1}^*)
$$
where $\partial_{k-1}, \partial_{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(\partial_{k-1}^*)$, because $\partial_{k-1}^*$
coincides with the coboundary map for the full simplex $2^{[n]}$
on vertex set $[n]$, and this simplex is $\reals$-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) \circ \partial_{k-2}^* [F] = 0$.
But $L'(K) = \partial^K_{k-1} \circ (\partial^K_{k-1})^*$, where
$\partial^K_{k-1}, (\partial^K_{k-1})^*$ are the boundary
and coboundary maps for the simplicial complex generated by $K$.
Therefore, it would suffice to prove the stronger assertion that
$$
(\partial^K_{k-1})^* \circ \partial_{k-2}^* [F] = 0.
$$
This would follow if we can show
$$
(\partial^K_{k-1})^* \circ \partial_{k-2}^* [F] =
(\partial^K_{k-1})^* \circ (\partial^K_{k-2})^* [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
$(\partial^K_{k-1})^* \partial_{k-2}^* [F]$ is a signed
sum of oriented simplices $[H]$ where the summation runs
over pairs $(H,G)$ in which $F \subset G \subset H$,
$k=\abs{H}=\abs{G}+1=\abs{F}+2$, and $G$ is arbitrary but $H$ must lie in $K$.
On the other hand, $(\partial^K_{k-1})^* (\partial^K_{k-2})^* [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 \subset H$.
\end{proof}
We immediately deduce
\begin{theorem}
\label{Kc-spectrum-theorem}
In the situation of the previous proposition, the spectra
$$
\begin{aligned}
\s'(K)&=(s_1 \geq \ldots \geq s_{\binom{n-1}{k}})\\
\s'(K^c)&=(s^c_1 \geq \ldots \geq s^c_{\binom{n-1}{k}})
\end{aligned}
$$
both end with at least $\binom{n-1}{k-2}$ zeroes.
The rest of their spectra are related by
\begin{equation}
\label{Kc-spectrum-equation}
s^c_i = n - s_{\binom{n-1}{k-1}+1-i}
\end{equation}
for each $i \leq \binom{n-1}{k-1}$.
\end{theorem}
Having already discussed the two operations $K \mapsto K^*$
and $K \mapsto K^c$ on $k$-families, it is now easy to understand the effect
on the spectra of an operation on simplicial complexes sometimes known
as the {\it canonical Alexander dual} or {\it blocker}
(see e.g.\ \cite[\S 6]{Kalai}).
\begin{definition}
For a simplicial complex $K$
on vertex set $[n]$, the canonical Alexander dual $K^{\vee}$
is defined by
$$
K^{\vee} :=\{ [n] \backslash A\colon A \not\in K \}.
$$
In other words, the $(i+1)$-family $K_i$ of $i$-simplices in $K$
and the $(n-i-1)$-family $K^{\vee}_{n-i-2}$ of $(n-i-2)$-simplices
in $K^{\vee}$ are related by
$$
K^{\vee}_{n-i-2} = (K_i)^{c*} = (K_i)^{c*}.
$$
\end{definition}
It is well-known and not hard to show (see e.g.\ \cite[\S 6]{Kalai}) that
Alexander duality implies
$$
\tilde{H}_i(K;\integers) \cong \tilde{H}^{n-i-3}(K^{\vee};\integers).
$$
and hence
$$
\tilde{H}_i(K;\reals) \cong \tilde{H}^{n-i-3}(K^{\vee};\reals) \cong
\tilde{H}_{n-i-3}(K^{\vee};\reals)^*
$$
via the Universal Coefficient Theorems \cite{Munkres}.
Consequently, the multiplicity of zero in $\stot_i(K)$
must coincide with the multiplicity of zero in $\stot_{n-i-3}(K^\vee)$.
The following corollary shows that much more is true.
\begin{corollary}
\label{spectra-Alexander-dual}
Let $K$ be a simplicial complex on vertex set $[n]$,
and $K^{\vee}$ its canonical Alexander dual. Let
$\stot_i(K)$ denote the spectrum of
$$
\partial_{i+1} \partial_{i+1}^* + \partial_i^* \partial_i\colon
C_i(K;\reals) \rightarrow C_i(K;\reals).
$$
Then for each $i=-1,0,1,2,\ldots,n-2$,
\begin{itemize}
\item
for every eigenvalue $\lambda$ strictly less than $n$,
the multiplicities of $\lambda$ in $\stot_i(K)$ and $\stot_{n-i-3}(K^{\vee})$
are the same,
\item
the difference in multiplicities of the
eigenvalue $n$ is exactly
$$
\begin{aligned}
\mult_n \stot_i(K)- \mult_n \stot_{n-i-3}(K^{\vee})
&= f_i(K) - f_{n-i-3}(K^{\vee}) \\
&= f_i(K) + f_{i+1}(K) - \binom{n}{i+2} \\
\end{aligned}
$$
where we recall that $f_i(K):=\abs{K_i}$ is
the number of $i$-dimensional simplices of $K$.
\end{itemize}
\end{corollary}
\begin{proof}
As mentioned above, Alexander duality already implies the assertion
for the multiplicity of the eigenvalue $0$.
For eigenvalues $\lambda$ not equal to $0$ or $n$, note that combining
Theorems \ref{K*-spectrum-theorem} and \ref{Kc-spectrum-theorem}
implies that for any $k$-family $L$, the multiplicities of $\lambda$
in $L$ and in $L^{*c} = L^{c*}$ are the same. This implies
in our situation that
$$
\partial_i^* \partial_i(K) \text{ and }
\partial_{n-i-2} \partial_{n-i-2}^*(K^{\vee})
$$
will have the same multiplicity of $\lambda$, and similarly
for
$$
\partial_{i+1} \partial_{i+1}^*(K) \text{ and }
\partial_{n-i-3}^* \partial_{n-i-3}(K^{\vee}).
$$
Consequently, Equation \eqref{s-union-minus} implies
that their sums
$$
\partial_{i+1} \partial_{i+1}^* (K) + \partial_i^* \partial_i (K)
\text{ and }
\partial_{n-i-3}^* \partial_{n-i-3}(K^{\vee})+
\partial_{n-i-2} \partial_{n-i-2}^*(K^{\vee})
$$
will also have the same multiplicity of $\lambda$, 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;\reals), C_{n-i-3}(K^{\vee})$ on which they act. The second
assertion of the proposition then follows immediately.
\end{proof}
The last operation we will discuss is the {\it simplicial join}.
\begin{definition}\label{join-defn}
Given a simplicial complex $K_1$ on $[m]$ and a simplicial complex
$K_2$ on $[n]$, their {\it join} $K_1 * K_2$ is the simplicial
complex on $[m+n]$ consisting of all simplices of the
form $F_1 \disun F_2$, where
$F_1 \in K_1$ so that $F_1 \subseteq [m]$,
and $F_2 \subseteq [m+1, n]:=\{m+1,m+2,\ldots,n\}$ is obtained
from some face of $K_2$ by adding $m$ to each of its elements. Here,
$\disun$ denotes disjoint union.
\end{definition}
\begin{proposition}
For any simplicial complexes $K_1, K_2$ and every $i$, the
map $\phi$ defined $\reals$-linearly by
$$
[F_1] \otimes [F_2] \mapsto [F_1 \disun F_2]
$$
identifies the vector spaces
$$
\bigoplus_{(i_1,i_2)\colon i_1+i_2+1=i}
C_{i_1}(K_1;\reals) \otimes C_{i_2}(K_2;\reals)
\cong C_i(K_1 * K_2 ; \reals)
$$
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$:
\begin{equation}
\label{join-operator-equation}
L(K_1 * K_2) = L(K_1) \otimes \id + \id \otimes L(K_2)
\end{equation}
\end{proposition}
\begin{proof}
We will temporarily use the notations
$$
\begin{aligned}
&\partial, \partial^*,L',L'',L,\\
&\partial_{K_1},\partial_{K_1}^*,L'_{K_1},L''_{K_1},L_{K_1},\\
&\partial_{K_2},\partial_{K_2}^*,L'_{K_2},L''_{K_2},L_{K_2}
\end{aligned}
$$
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 $\partial, \partial^*$
act
on a typical chain $[F_1] \otimes [F_2]$
as graded derivations, i.e.\
$$
\begin{aligned}
\partial &=
\partial_{K_1} \otimes \id +
(-1)^{\abs{F_1}} \id \otimes \partial_{K_2} \\
\partial^* &=
\partial^*_{K_1} \otimes \id +
(-1)^{\abs{F_1}} \id \otimes \partial^*_{K_2}
\end{aligned}
$$
and consequently $L', L''$ behave as follows:
$$
\begin{aligned}
L' &=
L'_{K_1} \otimes \id
+(-1)^{\abs{F_1}+1} \partial_{K_1}^* \otimes \partial_{K_2}
+(-1)^{\abs{F_1}} \partial_{K_1} \otimes \partial^*_{K_2}
+\id \otimes L'_{K_2} \\
L'' &=
L''_{K_1} \otimes \id
+(-1)^{\abs{F_1}-1} \partial_{K_1} \otimes \partial^*_{K_2}
+(-1)^{\abs{F_1}} \partial_{K_1}^* \otimes \partial_{K_2}
+\id \otimes L''_{K_2}
\end{aligned}
$$
Adding the last two equations gives the desired formula:
$$
L = L_{K_1} \otimes \id
+\id \otimes L_{K_2}.
$$
\end{proof}
We immediately deduce
\begin{theorem}\label{spectra-join}
If $K_1$ and $K_2$ are two simplicial complexes, and $*$ denotes the join, then
$$\stot_i(K_1 * K_2) =
\bigcup_{\condns{i_1+i_2+1=i}{\lambda_1 \in \stot_{i_1}(K_1),\ \lambda_2 \in \stot_{i_2}(K_2)}}
\lambda_1+\lambda_2.$$
\end{theorem}
\begin{corollary}\label{spectra-cone}
If $K$ is a simplicial complex, and $1*K$ denotes the cone over $K$, then
$$\s'_i(1*K) \circeq 1^{f_i(K)} + (\s'_{i-1}(K) \cup \s'_i(K))$$
for all $i$.
\end{corollary}
\begin{proof}
First we apply Theorem \ref{spectra-join}, with $K_1$ being the simplicial
complex on one vertex, and $K=K_2$. It is easy to check that
$\stot_{-1}(K_1)=\stot_{0}(K_1)=(1)$, and that $\stot_i(K_1)$ is the the trivial
partition for all other $i$. Then Theorem \ref{spectra-join} says
\begin{equation}\label{spectra-cone-equation}\begin{aligned}%\begin{split}
\stot_i(1*K) &= (\bigcup_{\lambda_1 \in \stot_{i-1}(K)} \lambda_1 + 1)
\cup (\bigcup_{\lambda_2 \in \stot_i(K)} 1+\lambda_2)\\
% &=(1^{\ell(\stot_{i-1}(K))}+\stot_{i-1}(K)) \cup (1^{\ell(\stot_i(K))}+\stot_i(K))\\
&=(1^{f_{i-1}(K)}+\stot_{i-1}(K)) \cup (1^{f_i(K)}+\stot_i(K)).
\end{aligned}%\end{split}
\end{equation}
Next we prove
$$\s'_i(1*K) \circeq 1^{f_i(K)} + \stot_i(K) $$
by induction on $i$; the result then follows by Equation
\eqref{s-union-minus}. For $i=-1$,
$$\s'_{-1}(1*K) = f_0(1*K) =
1+ f_0(K) = 1^{f_{-1}(K)} + \stot_{-1}(K),$$
by Equation \eqref{s-1}.
%
So let $i \geq 0$; then
\begin{align*}
\s'_i(1*K) &\circeq \stot_i(1*K) - \s'_{i-1}(1*K)
&&\text{by Equation \eqref{s-union-minus}}\\
&\circeq \stot_i(1*K) - (1^{f_{i-1}(K)} + \stot_{i-1}(K))
&&\text{by induction}\\
&= ((1^{f_i(K)}+\stot_i(K))
\cup (1^{f_{i-1}(K)} + \stot_{i-1}(K)))\\
&\quad - (1^{f_{i-1}(K)} + \stot_{i-1}(K))
&&\text{by Equation \eqref{spectra-cone-equation}}\\
&= 1^{f_i(K)} + \stot_i(K).
\end{align*}
\end{proof}
\section{The main theorem}
\label{main-theorem-section}
The goal of this section is to prove the main result
Theorem \ref{main-theorem} 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 $\circeq$-equivalence class
of the spectrum of $L'(K) = \partial_{k-1} \partial_{k-1}^T$.
Let $\dd(K)=\dd_{k-1}(K)$ denote the degree sequence of vertices
with respect to the $k$-sets in $K$.
\begin{restate-main}
For any shifted $k$-family $K$, the spectrum $\s$
of its Laplacian $L'(K)$ satisfies
$$
\s = \dd^T
$$
where here $\dd^T$ is the conjugate partition to
the degree sequence $\dd$ of vertices with respect
to the $k$-sets in $K$.
\end{restate-main}
As discussed in the introduction, in the case $k=2$,
the integrality of $\s$ is a result of Kelmans
(see \cite[Corollary 4.1]{HammerKelmans}). Kelmans' result
was independently rediscovered by Merris \cite{Merris}, 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,\ldots,n\}$ called, respectively,
the {\it link} and {\it deletion} of vertex $1$ in $K$:
$$
\begin{aligned}
\link_K 1 &:=\{A \backslash \{1\} \colon 1 \in A \in K\} \\
\del_K 1 &:=\{A \in K\colon 1 \not\in A\}.
\end{aligned}
$$
There is always a decomposition
\begin{equation}
\label{deletion-link-decomposition}
K = (1*\link_K 1) \disun \del_K 1
\end{equation}
where $1*\link_K 1$ denotes
the $k$-family $\{\{1\} \disun A\colon A \in \link_K 1\}$, i.e.\
the collection of sets of $K$ that contain $1$.
(See Definition \ref{join-family-defn} below.)
We say that $K$ is a {\it near-cone with apex $1$} if for every
set $A$ in $\del_K 1$ and every $a$ in $A$ one has that
$A \backslash \{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.
\begin{lemma}
\label{inductive-shifted-definition}
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]$.
\end{lemma}
In light of this lemma,
the following two lemmas about the behavior of $\s$ and
$\dd^T$ for near-cones and shifted complexes
immediately give a proof of Theorem \ref{main-theorem}
by induction on $n$.
\begin{lemma}
\label{near-cone-d-behavior}
If $K$ is a $k$-family which is a near-cone with
apex $1$, then
$$
\dd(K)^T \trianglerighteq
1^{\abs{\link_K 1}}+
(\dd(\link_K 1)^T \cup \dd(\del_K 1)^T).
$$
Furthermore, when $K$ is shifted, the above
majorization inequality is an equality.
\end{lemma}
\begin{proof}
By taking the conjugate partition on both sides and
using Proposition \ref{partition-transpose}, we must show that
$$
\dd(K) \maj
(\abs{\link_K 1}) \cup
( \dd(\link_K 1) + \dd(\del_K 1) ).
$$
By the definition of $\link_K 1$, the vertex $1$ of $K$
lies in exactly $\abs{\link_K 1}$ sets of $K$. So the
left and right-hand sides of the desired inequality are
both partitions that contain the part $\abs{\link_K 1}$.
We can therefore remove this part from both sides, and
instead prove
$$
\dd'(K) \maj
\dd(\link_K 1) + \dd(\del_K 1).
$$
where here $\dd'(K)$ denotes the partition obtained
from $\dd(K)$ by removing the part $\abs{\link_K 1}$ corresponding
to the vertex $1$.
Now let
$$
D'(K), D(\link_K 1), D(\del_K 1)
$$
denote the {\it unsorted} degree sequences for the ordered
vertex set $[2,n]$ that correspond after
sorting to
$$
\dd'(K), \dd(\del_K 1), \dd(\link_K 1)
$$
respectively. From the decomposition \eqref{deletion-link-decomposition}
it follows that
$$
D'(K) = D(\del_K 1) + D(\link_K 1)
$$
as vectors of nonnegative integers in $\naturals^{n-1}$.
On the other hand, it is easy to see \cite[Chapter 6, A.1]{MarshallOlkin}
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' \maj 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 \eqref{degree-ordering} guarantees
%
the ordered degree sequences $D'(K), D(\link_K 1), D(\del_K 1)$
coincide with $\dd'(K), \dd(\link_K 1), \dd(\del_K 1)$.
Hence the last inequality above becomes an equality,
which when traced backwards proves the second assertion.
\end{proof}
\begin{lemma}
\label{near-cone-s-behavior}
If $K$ is a $k$-family which is a near-cone with
apex $1$, then
$$
\s(K) \circeq
1^{\abs{\link_K 1}}+
(\s(\link_K 1) \cup \s(\del_K 1)).
$$
\end{lemma}
\begin{proof}
Let $K'$ be the $(k-1)$-dimensional simplicial complex generated by
$\link_K 1 \disun \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,
\begin{equation}\label{D-skeleton}
(K')_{k-1} = \del_K 1;
\end{equation}
the near-cone condition on $K$ further implies
\begin{equation}\label{L-skeleton}
(K')_{k-2} = \link_K 1.
\end{equation}
Now let $1*K'$ denote the simplicial complex cone over $K'$. Then
\begin{equation}\label{K-skeleton}
(1*K')_{k-1} = (1*(K')_{k-2}) \disun (K')_{k-1}
= (1 * \link_K 1) \disun \del_K 1 = K.
\end{equation}
Thus
\begin{align*}
\s(K) &\circeq \s'_{k-2}(1*K')
&&\text{by Equation \eqref{K-skeleton}}\\
&\circeq 1^{f_{k-2}(K')} + (\s'_{k-3}(K') \cup \s'_{k-2}(K'))
&&\text{by Corollary \ref{spectra-cone}}\\
&\circeq 1^{\abs{\link_K 1}} + (\s(\link_K 1) \cup \s(\del_K 1))
&&\text{by Equations \eqref{L-skeleton} (twice) and \eqref{D-skeleton}}.
\end{align*}
Here we are using, in the first and last equivalence, that $\s'_i$
depends only upon $(i+1)$-dimensional faces.
\end{proof}
The proof of Theorem \ref{main-theorem}
(specifically Lemma \ref{near-cone-s-behavior})
actually established a stronger result which applies to
families that are not necessarily shifted:
\begin{corollary}\label{integral-near-cone}
If $K$ is a near-cone and
$\s(\link_K 1)$ and $\s(\del_K 1)$ are integral, then so
is $\s(K)$. \qed
\end{corollary}
\begin{example}
We use Corollary \ref{integral-near-cone} to find a non-shifted family
$K$ with $\s(K)$ integral.
Define a $3$-family $K$ on vertex set $[6]$ by letting
\begin{align*}
\link_K 1 &= \{23, 24, 25, 26, 34, 35, 36, 45\},\\
\del_K 1 &= \{236\}.
\end{align*}
(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 \ref{main-theorem},
and thus $\s(K)$ is integral by Corollary \ref{integral-near-cone}.
But one can check that $K$ is not isomorphic to a shifted
family.
\end{example}
One can, of course, rephrase the main result in terms of
the spectra of $L_i(K)$ for a simplicial complex $K$:
\begin{corollary}\label{main-theorem-corollary}
If $K$ is a shifted simplicial complex, then
$$
\stot_i(K) \circeq \dd_i(K)^T \cup \dd_{i+1}(K)^T.
$$
\end{corollary}
\begin{proof}
Apply Equation \eqref{s-union-minus} to Theorem \ref{main-theorem}.
\end{proof}
\section{A conjecture on the spectra}
\label{conjecture-section}
The goal of this section is to recall and present evidence
for Conjecture \ref{GM-conjecture}, which generalizes a
conjecture of Grone and Merris \cite[Conjecture 2]{GroneMerris}.
We adhere to the same notation as in the previous section, that
is, for a $k$-family $K$, we let $\s=\s(K)$ denote
the $\circeq$-equivalence class
of the spectrum of $L'(K) = \partial_{k-1} \partial_{k-1}^T$,
and $\dd(K)=\dd_{k-1}(K)$ denotes the degree sequence of vertices
with respect to the $k$-sets in $K$.
\begin{restate-GM}
For any $k$-family $K$,
$$
\s \maj \dd^T
$$
with equality if and only if $K$ is isomorphic to a shifted
family.
\end{restate-GM}
We remark that half of the ``if and only if" assertion about
the case of equality is exactly Theorem \ref{main-theorem}. It will also be
shown (in Proposition \ref{half-implies-other-half}
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,\ldots)$ with $s_1 \geq s_2 \geq \cdots$,
and $\dd(K)^T=(d_1^T,d_2^T,\ldots)$ then
$$
\begin{aligned}
s_1 &\leq d_1^T \\
s_1+s_2 &\leq d_1^T+d_2^T \\
s_1+s_2+s_3 &\leq d_1^T+d_2^T+d_3^T\\
&\vdots \\
\sum_j s_j &\leq \sum_j d_j^T
\end{aligned}
$$
and so we first observe that the last inequality is
actually always an equality:
\begin{proposition}
$$
\sum_{j} s_j = \sum_j d_j^T
$$
\end{proposition}
\begin{proof}
$$
\begin{aligned}
\sum_j d_j^T &= \sum_j d_j\\
&= \sum_{i=1}^n \abs{\{A \in K\colon i \in A\}}\\
&= \sum_{B \subset [n], \abs{B}=k-1} \abs{\{A \in K\colon B \subset A\}} \\
&= \Trace \partial_K \partial_K^* \\
&= \sum_{j} s_j
\end{aligned}
$$
\end{proof}
The first inequality in the conjectured majorization
Conjecture \ref{GM-conjecture} is easy (and was already known for
graphs \cite[p.\ 226]{GroneMerris}):
\begin{proposition}
\label{first-GM-inequality}
$$
s_1 \leq d_1^T
$$
\end{proposition}
\begin{proof}
Note that $d_1^T$ is simply the number of vertices in
$[n]$ which lie in {\it some} subset of $K$, that is,
the number of {\it 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 \leq n$.
We give three proofs of this. The first uses
Theorem \ref{K*-spectrum-theorem} 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 \leq n$ for each $i$.
Similarly one can use Theorem \ref{Kc-spectrum-theorem}
relating the spectra of $K$ and $K^c$ to prove $s_i \leq 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
\cite[Chapter 20, A.1, p.\ 510]{MarshallOlkin} of $s_1$. We know that
$$
s_1(K) = \max_{ x \in \reals^{\binom{[n]}{k-1}} \backslash \{0\} }
\frac{x^T \partial_K \partial^*_K x}{x^T x}
= \max_{ x \in \reals^{\binom{[n]}{k-1}} \backslash \{0\} }
\frac{\Vert \partial^*_K x \Vert^2}{\Vert x \Vert^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 $\reals^{\binom{[n]}{k-1}}$,
$$
\Vert \partial^*_K x \Vert^2 \leq
\Vert \partial^*_{\binom{[n]}{k}} x \Vert^2.
$$
But we know $\binom{[n]}{k}$ has $s_1 = n$
by Theorem \ref{main-theorem}.
\end{proof}
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 $\dd$: we have
$0 \leq d_i^T \leq n$ since $\dd$ is a partition with $n$
parts. Therefore Conjecture \ref{GM-conjecture} has
consequences regarding the relation between
multiplicities of the values $0$ and $n$
in $\s$ and $\dd$. These consequences turn out to be true, and for the
purposes of stating them most conveniently, we regard
both $\s=(s_1,\ldots,s_{\abs{K}})$ and
$\dd=(d_1^T,\ldots,d_{\abs{K}}^T)$ as sequences of length $\abs{K}$,
thinking of $\s$ as the spectrum of the
$\abs{K} \times \abs{K}$ matrix $\partial^*_K \partial_K$. We
also recall from Section \ref{constructions} that $K^*$ is the $(n-k)$-family
defined by
$$
K^*=\{[n] \backslash A\colon A \in K\}.
$$
\begin{proposition}
\label{multiplicities-and-near-cones}
The multiplicity of $0$ \textup{(}resp.\ $n$\textup{)} in $\s$ is at
least \textup{(}resp.\ at most\textup{)} the multiplicity of $0$
\textup{(}resp.\ $n$\textup{)} in $\dd^T$, with equality if and only
if $K$ \textup{(}resp.\ $K^*$\textup{)} is a near-cone.
\end{proposition}
\begin{proof}
The assertions for the multiplicity of $n$ follow from the
same assertions for the multiplicity of $0$ using
Theorem \ref{K*-spectrum-theorem},
so we only need to prove the latter assertions.
One can check that the multiplicity of $0$ in $\dd^T$ is
exactly $\abs{K}-\delta$, where $\delta$ 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
$\delta$. Then $\abs{K}-\delta$ is exactly the
number of maximal faces of $K$ that do {\it not} contain $v$.
Thus we must show the following
%\begin{quotation}%\begin{quote}
%{\bf Claim:}
\begin{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$.
\end{claim}
%\end{quotation}%\end{quote}
%\noindent
To see this, note that the sets in $K$ which
contain $v$ generate a contractible subcomplex $S$
(the {\it 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$.
\end{proof}
We can now show that the first assertion in Conjecture \ref{GM-conjecture}
implies the second.
\begin{proposition}
\label{half-implies-other-half}
If we know that $\s \maj \dd^T$ holds for every $k$-family, then
$\s(K) = \dd^T(K)$ implies $K$ is isomorphic to a shifted family.
\end{proposition}
\begin{proof}
We use induction on $n$.
Assume $K$ is a $k$-family on $[n]$ with $\s(K) = \dd(K)^T$.
Then Proposition \ref{multiplicities-and-near-cones}
implies that $K$ is a near-cone on
some vertex, which we may assume without loss of generality
is vertex $1$. By Proposition \ref{inductive-shifted-definition},
it would suffice to show
that $\link_K 1, \del_K 1$ satisfy the same equality
$\s=\dd^T$. To see this, we exhibit a sequence of majorization
inequalities and equalities, which will be justified below:
$$
\begin{aligned}
1^{\abs{\link_K 1}} + ( \dd(\link_K 1)^T \cup \dd(\del_K 1)^T )
&\trianglerighteq^{(1)} 1^{\abs{\link_K 1}} + ( \s(\link_K 1) \cup \s(\del_K 1) ) \\
&=^{(2)} \s(K) \\
&= \dd(K)^T \\
&\trianglerighteq^{(3)} 1^{\abs{\link_K 1}} + ( \dd(\link_K 1)^T \cup \dd(\del_K 1)^T ).%\\
\end{aligned}
$$
The inequality $\trianglerighteq^{(1)}$ comes from the assumption that
$\s \maj \dd^T$ applied to both families $\link_K 1, \del_K 1$,
and uses the fact \cite[Chapter 5, A.7(i), p.\ 121]{MarshallOlkin}
that if $\alpha \maj \beta$ then
for any $\gamma$ one has
$$
\alpha \cup \gamma \maj \beta \cup \gamma.
$$
The equality $=^{(2)}$ follows from Lemma \ref{near-cone-s-behavior},
since $K$ is a near-cone.
The next equality is our hypothesis. The last inequality
$\trianglerighteq^{(3)}$ follows from Lemma \ref{near-cone-d-behavior}.
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
$\trianglerighteq^{(1)}$ is an equality,
when combined with the assumption that $\s \maj \dd^T$ applies to $\link_K
1$ and $\del_K 1$,
implies
$$
\begin{aligned}
\s(\link_K 1) &= \dd(\link_K 1)^T, \\
\s(\del_K 1) &= \dd(\del_K 1)^T.
\end{aligned}
$$
Thus, induction applies and the proof is complete.
\end{proof}
A further piece of evidence for Conjecture \ref{GM-conjecture}
is its consistency with some of the constructions of
Section \ref{constructions}.
\begin{proposition}
\label{consistent-with-constructions}
For any $k$-family $K$ on $[n]$, one has
$$
\begin{aligned}
& \s(K) \maj \dd(K)^T \\
\Leftrightarrow \quad & \s(K^*) \maj \dd(K^*)^T \\
\Leftrightarrow \quad & \s(K^c) \maj \dd(K^c)^T.
\end{aligned}
$$
\end{proposition}
\begin{proof}
For weakly decreasing sequences of nonnegative real
numbers
$$
\lambda=(\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_r)
$$
and positive integers $a$ satisfying $a \geq \lambda_1$,
define the {\it complementation of $\lambda$ within $a^r$}
to be the weakly decreasing sequence
$$
a^r\backslash \lambda=(a-\lambda_r \geq a-\lambda_{r-1}
\geq \ldots \geq a-\lambda_1).
$$
It is easy to check that this operation preserves majorization
$$
\lambda \maj \mu \,\, \Leftrightarrow \,\,
a^r \backslash \lambda \maj a^r \backslash \mu,
$$
and also that it commutes with conjugation whenever $a$ is a
nonnegative integer and $\lambda$ is a partition
$$
(a^r \backslash \lambda)^T = r^a \backslash \lambda^T.
$$
This applies to our situation since Theorems \ref{K*-spectrum-theorem}
and \ref{Kc-spectrum-theorem} imply that
$$
\begin{aligned}
\s'(K^*) &= n^{\abs{K}} \backslash \s'(K) \\
\s''(K^c) &= n^{\binom{n-1}{k-1}} \backslash \s''(K)
\end{aligned}
$$
and it is easy to check that
$$
\begin{aligned}
\dd(K^*) &= \abs{K}^n \backslash \dd(K) \\
\dd(K^c) &= \binom{n-1}{k-1}^n \backslash \dd(K)
\end{aligned}
$$
so that
$$
\begin{aligned}
\dd(K^*)^T &= n^{\abs{K}} \backslash \dd(K)^T \\
\dd(K^c)^T &= n^{\binom{n-1}{k-1}} \backslash \dd(K)^T.
\end{aligned}
$$
Since $\s$ is the $\circeq$-equivalence class of either
$\s'$ or $\s''$, the result follows.
\end{proof}
Note that the previous proposition reduces the proof
of Conjecture \ref{GM-conjecture} to the cases of $k$-families
$K$ where $\abs{K} \leq \frac{1}{2}\binom{n}{k}$ and where
also $k \leq \frac{n}{2}$. However we are not hopeful that
this reduction will be useful.
Conjecture \ref{GM-conjecture} is also consistent with the simplicial
join, which is defined for families the same way it is defined
for simplicial complexes (Definition \ref{join-defn}).
\begin{definition}\label{join-family-defn}
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 \disun F_2$, where
$F_1 \in K_1$ so that $F_1 \subseteq [m]$,
and $F_2 \subseteq [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$.
\end{definition}
\begin{proposition}\label{consistent-with-joins}
If $K_1$ and $K_2$ are families such that $\s(K_1) \maj \dd(K_1)^T$
and $\s(K_2) \maj \dd(K_2)^T$, then
$\s(K_1 * K_2) \maj \dd(K_1 * K_2)^T$.
\end{proposition}
\begin{proof}
For a partition $\blambda = (\lambda_1,\dots,\lambda_r) =
1^{l_1}2^{l_2}\cdots$ and a positive integer $c$, define new partitions
$$
c \blambda = (c \lambda_1, \dots, c \lambda_r)
$$
(multiply each part by $c$), and
$$
\blambda^c = 1^{cl_1}2^{cl_2}\cdots
$$
(repeat each part $c$ times). It is a routine calculation that
$(c \blambda)^T = (\blambda^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 \in K$ such that $v \in F_1$, all $\abs{K_2}$ of the
members $F_2$ of $K_2$ satisfy $v \in F_1 \disun F_2 \in K_1 * K_2$;
thus $\degr(K_1*K_2,v) = \abs{K_2} \degr(K_1,v)$. Similarly, if $w \in
K_2$, then $\degr(K_1*K_2,w) = \abs{K_1} \degr(K_2,w)$. It follows that
$$
\dd(K_1 * K_2) = \abs{K_2} \dd(K_1) \cup \abs{K_1} \dd(K_2).
$$
Therefore
\begin{align*}
\dd(K_1 * K_2)^T
&= (\abs{K_2} \dd(K_1) \cup \abs{K_1} \dd(K_2))^T\\
&= (\abs{K_2} \dd(K_1))^T + (\abs{K_1} \dd(K_2))^T\\
&= (\dd(K_1)^T)^{\abs{K_2}} + (\dd(K_2)^T)^{\abs{K_1}}.
\end{align*}
For an arbitrary $k$-family $K$ with corresponding $(k-1)$-dimensional
simplicial complex $\overline{K}$, we have
$\s(K) = \s''_{k-1}(\overline{K}) = \stot_{k-1}(\overline{K})$,
with the convention (to which we will adhere for the remainder of the
proof) that $\s(K)$ has $\abs{K}$ parts, by adding trailing zeroes where
necessary. Theorem \ref{spectra-join} thus implies
\begin{equation}\label{s-join-equation}
\s(K_1 * K_2) =
\bigcup_{\substack{\lambda_1 \in \s(K_1)\\ \lambda_2 \in \s(K_2)}}
\lambda_1 + \lambda_2.
\end{equation}
The components of the right-hand side of Equation
\eqref{s-join-equation} are those of the vector
$$
\s(K_1)^{\abs{K_2}} + S_2,
$$
where $S_2$ is the vector obtained by concatenating $\abs{K_1}$ copies
of $\s(K_2)$ together. Clearly the sorted partition corresponding to
$S_2$ is $\s(K_2)^{\abs{K_1}}$, and so, as in the proof of Lemma
\ref{near-cone-d-behavior}, it is easy to see
\cite[Chapter 6, A.1]{MarshallOlkin} that
$$
\s(K_1 * K_2) \maj \s(K_1)^{\abs{K_2}} + \s(K_2)^{\abs{K_1}}.
$$
We now conclude
\begin{align*}
\s(K_1 * K_2)
&\maj \s(K_1)^{\abs{K_2}} + \s(K_2)^{\abs{K_1}}\\
&\maj (\dd(K_1)^T)^{\abs{K_2}} + (\dd(K_2)^T)^{\abs{K_1}}\\
&= \dd(K_1 * K_2)^T.
\end{align*}
\end{proof}
\section{The second inequality for graphs}
\label{second-inequality-for-graphs-section}
The goal of this section is to prove
\begin{theorem}
\label{second-inequality}
For $2$-families \textup{(}graphs\textup{)}, the second inequality
$$
s_1 + s_2 \leq d_1^T + d_2^T
$$
in Conjecture \textup{\ref{GM-conjecture}} is valid.
\end{theorem}
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.
%\vskip.1in
%{\bf Step 1.}
\begin{step}\label{step1}
For any $k$-family $K$ we have
\begin{equation}
\label{measly-reduction}
s_1 + s_2 \leq d^T_1 + d^T_2 + 2(k-1).
\end{equation}
\end{step}
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
\cite[Chapter 9, G.1, p.\ 241]{MarshallOlkin},
then says that
$$
s_1(K) + s_2(K) \leq s_1(K_1) + s_2(K_1) + s_1(K_2) + s_2(K_2).
$$
Proposition \ref{first-GM-inequality} gives the trivial
upper bounds $s_1(K_1), s_2(K_1) \leq 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 \ref{main-theorem} applies. Letting
$b_1 \geq b_2 \geq \ldots \geq b_r$ denote the sizes
of these equivalence classes (so $\sum_i b_i = d_1^T(K)-d_2^T(K)$),
one obtains the inequality
$$
\begin{aligned}
s_1(K) + s_2(K) & \leq 2 d_2^T + b_1 + b_2 + 2(k-1)\\
& \leq 2 d_2^T + (d_1^T-d_2^T) + 2(k-1) \\
& = d_1^T + d_2^T + 2(k-1) \\
\end{aligned}
$$
Note that we have in fact shown something slightly stronger:
whenever we have the inequality
\begin{equation}
\label{more-precise-measly-reduction}
d_1^T-d_2^T-(b_1+b_2) = b_3+b_4+\cdots+b_r \geq 2(k-1)
\end{equation}
the second inequality of Conjecture \ref{GM-conjecture} follows.
%\vskip.1in
%{\bf Step 2.}
\begin{step}\label{step2}
We use the previous comment to
reduce Theorem \ref{second-inequality} to some special cases.
\end{step}
Note that since $k=2$ for graphs,
and $b_i \geq 1$ for each $i$, the inequality (\ref{more-precise-measly-reduction})
holds whenever $r \geq 4$, or when $r = 3$ and $b_3 \geq 2$.
Consequently Theorem \ref{second-inequality} 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$.
%\vskip.1in
%{\bf Step 3.}
\begin{step}\label{step3}
A further (independent) reduction comes from monotonicity properties of
the eigenvalues.
\end{step}
Variational characterizations
of eigenvalues \cite[Chapter 20, A.2]{MarshallOlkin}
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 \ref{second-inequality} for graphs in which the vertices of
degree at least $2$ induce a complete subgraph $G$.
Combining this with Step \ref{step2} reduces us to some very
special graphs. Given positive integers $b_1,\ldots,b_r$ and a positive
integer $a \geq 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+\ldots+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 \ref{second-inequality} holds for all
graphs $G$ assuming that it holds for
\begin{itemize}
\item
$G_{a,b_1}$ with $a \geq 1$ and
\item
$G_{a,b_1,b_2}$ with $a \geq 2$ and
$b_1,b_2 \geq 1$,
\item
$G_{a,b_1,b_2,1}$ with $a \geq 3$ and
$b_1,b_2 \geq 1$.
\end{itemize}
On the other hand, $G_{a,b_1}$ is shifted, so the theorem follows
from Theorem \ref{main-theorem} in this case. Therefore we only need
to deal with the latter two families.
%\vskip.1in
%{\bf Step 4.}
\begin{step}\label{step4}
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}$.
\end{step}
Let $x=(x_1,x_2,\ldots,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.\ \cite[proof of Theorem 5.2]{Faria} and \cite[proof of
Theorem 4]{GroneMerris})
one can easily check directly that
\begin{itemize}
\item
all vectors $x$ having
$$
x_4+x_5+\cdots+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})$,
\item
all vectors $x$ having
\begin{align*}
x_{a+1}+\cdots+x_{a+b_1}&=x_{a+b_1+1}+\cdots+x_{a+b_1+b_2}\\
&=x_{a+b_1+b_2+1}+\cdots+x_{a+b_1+b_2+b_3}=0
\end{align*}
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})$.
\end{itemize}
By choosing natural bases for the orthogonal complement of these
eigenspaces, one can write down the following expressions for their
characteristic polynomials:
$$
\begin{aligned}
\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)
\end{aligned}
$$
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 \ref{second-inequality} will follow for $G_{a,b_1,b_2}$
and $G_{a,b_1,b_2,1}$ if we can show these two assertions:
\begin{enumerate}
\item
For $a \geq 2$ and
$b_1,b_2 \geq 1$, the matrix $A$
has the sum of its largest two eigenvalues at most
$2a+b_1+b_2$,
\item
For $a \geq 3$ and
$b_1,b_2 \geq 1$,
the matrix $B$ has the sum of its largest two eigenvalues at most
$2a+b_1+b_2+1$.
\end{enumerate}
%\vskip.1in
%{\bf Step 5.}
\begin{step}\label{step5}
In this last step, a computer plays a role, and
we illustrate the argument for the matrix $A$ (the argument
for $B$ is similar).
\end{step}
The {\it second additive compound} of
a matrix $M$ \cite[Chapter 19 \S F, p.\ 505]{MarshallOlkin}
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 {\it 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
{\it 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 \geq 2$ and $b_1,b_2 \geq 1$).
To do this, we used a computer algebra package to expand
$$
\left[
\det((x-(2a+b_1+b_2))I-A^{(2)})
\right]_{\substack{a \mapsto \alpha+2\\
b_1 \mapsto \beta_1+1\\
b_2 \mapsto \beta_2+1}}.
$$
and checked a sufficient condition: that every coefficient of every
monomial in the variables $\alpha, \beta_1,\beta_2, x$ is nonnegative.
\section{Some easy spectrum bounds}
\label{easy-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 \cite[Chapter 9, B.1, p.\ 218]{MarshallOlkin}
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 \eqref{explicit-L'} that its diagonal entries are the degrees
of $(k-1)$-subsets of $[n]$ with respect to $K$, that is,
the quantities $\degr(K,A)$ as $A$ runs though $\binom{[n]}{k-1}$.
For a $k$-family $K$ on $[n]$, let
$$
\dd^{(k-1)}(K)=(d_1^{(k-1)},\ldots,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
\begin{proposition}
\label{Schur-dominance-consequence}
For any $k$-family
$$
\dd^{(k-1)} \maj \s. \qed
$$
\end{proposition}
\noindent
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)} \leq s_1$. One can
say something much stronger.
\begin{proposition}\textup{(}cf. \cite[Corollary 2]{GroneMerris}\textup{)}
For any $k$-family,
$$
d_1^{(k-1)}+k-1 \leq s_1 \leq d_1^{(k-1)}+d_2^{(k-1)}+\cdots+d_k^{(k-1)}.
$$
\end{proposition}
\begin{proof}
The lower bound on $s_1$ can be obtained using
the variational characterization
$$
s_1 = \max_{x \in \reals^{\abs{K}} \neq 0}
\frac{x^T \partial_K^* \partial_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,\ldots,A_D$ of $K$. Letting
$\epsilon(A_i,A) = (-1)^r$ when $A_i \backslash A$
is the $r^{th}$ smallest element of $A_i$, a direct
calculation shows that the
vector $x \in \reals^{\abs{K}}$ having $A_i^{th}$ coordinate
$\epsilon(A_i,A)$ and all other coordinates zero satisfies
$$
x^T \partial_K^* \partial_K x = D(D+k-1).
$$
Clearly $x^T x = D$, so we conclude that
$$
s_1 \geq \frac{x^T \partial_K^* \partial_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
\cite{Gershgorin} applied to $L''(K) = \partial_K^* \partial_K$.
Recall that Gershgorin's Theorem says a complex $N \times N$
matrix $A=(a_{ij})$ has every eigenvalue lying in at least
one of the disks $\abs{z-a_{ii}} \leq \rho_i$, where
$\rho_i = \sum_{j} \abs{a_{ij}}$. If row $i$ of $L''(K)$ corresponds
to a $k$-subset $A$ in $K$, then a glance at Equation \eqref{explicit-L''}
shows that $a_{ii}=k$. Furthermore, each non-zero entry in row $i$
is a $\pm 1$, with the number of such entries being
the sum of $\degr(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)+\cdots+(d_k^{(k-1)}-1)$,
which then gives an upper bound for $\rho_i$.
Consequently,
$$
\begin{aligned}
s_1 &\leq a_{ii} + \rho_i \\
&\leq k + (d_1^{(k-1)}-1)+\cdots+(d_k^{(k-1)}-1) \\
&= d_1^{(k-1)}+d_2^{(k-1)}+\cdots+d_k^{(k-1)}.
\end{aligned}
$$
\end{proof}
\begin{remark}
One might try to apply Gershgorin's Theorem to $L'(K)$,
but one obtains in general only the weaker inequality
$$
s_1 \leq k d_1^{(k-1)}.
$$
\end{remark}
Proposition \ref{Schur-dominance-consequence} raises
a question about its consistency with Conjecture \ref{GM-conjecture}.
The truth of Conjecture \ref{GM-conjecture} together with
Proposition \ref{Schur-dominance-consequence} would imply
$\dd^{(k-1)} \maj \s \maj \dd^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:
\begin{proposition}
\label{Dong-prop}
\begin{equation}
\label{implied-majorization}
\dd^{(k-1)} \maj \dd^T.
\end{equation}
\end{proposition}
\begin{proof}
Something yet more general follows from the half of the
Gale-Ryser Theorem \cite[Chapter 7, C.1, p.\ 176]{MarshallOlkin}
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 $\dd^{(i)}$ denote the weakly decreasing rearrangement of the
degrees $\degr(K,A)$ for $i$-subsets $A$, then we have more generally that
$$
\dd^{(i)} \maj \left( \dd^{(k-i)} \right) ^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$.
\end{proof}
For graphs, we have $k=2, i=1$ and
$$
\dd^{(i)}=\dd^{(k-i)}=\dd^{(1)}=:\dd
$$
is the degree sequence of the graph.
Here it is known that degree sequences $\dd$ are {\it characterized}
by the following set of stronger inequalities \cite{RuchGutman}
\begin{equation}
\label{RuchGutman-inequality}
\sum_{i=1}^k (d_i+1) \leq \sum_{i=1}^k d_i^T
\end{equation}
for $1 \leq k \leq f(\dd)$, where
$f(\dd)$ is the size of the {\it Durfee square} of $\dd$
when thought of as a partition, i.e.\ $f(\dd) = \abs{\{i\colon d_i \geq i\}}$.
In particular, the first inequality of \eqref{RuchGutman-inequality}
says $d_1+1 \geq d_1^T$, which motivated a conjecture
of Grone and Merris \cite[Conjecture 1]{GroneMerris} that was proven
by Grone \cite{Grone}. Grone's result strengthens
Proposition \ref{Schur-dominance-consequence} to the following
majorization inequality in the case $k=2$:
\begin{equation}
\label{Grone's-Theorem}
(d_1+1,d_2,d_3,\ldots,d_{n-2},d_{n-1},d_n-1) \maj \s.
\end{equation}
For arbitrary $k$, it is easy to see that
\begin{equation}
\label{first-combinatorial-inequality}
d^{(k-1)}_1+k-1 \leq d_1^T,
\end{equation}
so that the first inequality in Conjecture \ref{GM-conjecture}
(which we know is true by Proposition \ref{first-GM-inequality})
is consistent with
the first inequality of Proposition \ref{Schur-dominance-consequence}.
The preceding discussion motivates the following questions.
\begin{question}
Is there a set of valid inequalities generalizing
\eqref{implied-majorization}, \eqref{RuchGutman-inequality},
and \eqref{first-combinatorial-inequality}
for an arbitrary $k$-family?
\end{question}
\begin{question}
Is there a majorization inequality relating $\dd^{(k-1)}$
and $\s$ that generalizes both
Proposition \textup{\ref{Schur-dominance-consequence}} and
\eqref{Grone's-Theorem}, and that is valid for arbitrary $k$-families?
\end{question}
\section{Shifted versus degree-maximal complexes}
\label{degree-maximal-section}
The goal of this section is to explore how the relationship
between shifted graphs, degree sequences, and the majorization partial
order $\maj$ extends to higher dimensional $k$-families.
A partition is {\it graphic} if it is the degree sequence of some
graph. Ruch and Gutman proved that if $\bbeta$ is
graphic and $\balpha \maj \bbeta$, then $\balpha$ is also graphic
\cite[Theorem 1]{RuchGutman}.
We generalize graphic partitions in the obvious way, by calling
a partition {\it $k$-realizable} if it is the degree sequence of a
$k$-family. Ruch and Gutman's theorem now extends directly.
\begin{proposition}\label{realizable}
If $\bbeta$ is $k$-realizable and $\balpha \maj\bbeta$, then $\balpha$ is $k$-realizable.
\end{proposition}
\begin{proof}
Let $K$ be the $k$-family such that $\bbeta=\dd(K)$, and number the vertices
of $K$ such that $\degr(K,v)=\beta_v$. By induction, we may assume $\bbeta$
{\it covers} $\balpha$ in the majorization partial order, i.e., there is some $m$
such that
$$
\begin{aligned}
\beta_m&=\alpha_m+1\\
\beta_{m+1}&=\alpha_{m+1}-1\\
\beta_j&=\alpha_j \text{ for all other }j.
\end{aligned}
$$
Since $\balpha$ is a partition, then,
$$
\beta_m = \alpha_m+1 \geq \alpha_{m+1}+1 > \alpha_{m+1} - 1 = \beta_{m+1}.
$$
Because $\beta_m > \beta_{m+1}$, there is some set $B \in K$
containing vertex $m$ but not vertex $m+1$, such that
$A: = B \backslash \{m\} \disun \{m+1\} \not\in K$.
Then $\balpha=\dd(K \backslash \{B\} \disun \{A\})$.
\end{proof}
In the language of posets, Proposition \ref{realizable} says that the
$k$-realizable partitions form an order ideal in the poset of
partitions partially ordered by $\maj$.
%\smallskip
Merris \cite{Merris} defined a graph to be {\it degree-maximal} (or
{\it maximal}\,) if its degree sequence is majorized by no other graphic
partition.
\begin{proposition}\label{shifted-graph}
A graph is degree-maximal if and only if it is shifted.
\end{proposition}
\begin{proof}
Peled and Srinivasan \cite[Theorem 5.8]{PeledSrinivasan} proved that a
graph is degree-maximal if and only if it is {\it threshold}. But one
of several equivalent definitions of threshold graphs is easily seen
to be the definition of shifted graphs
\cite[Corollary 1A]{ChvatalHammer}.
\end{proof}
Following Merris, we will say a $k$-family is {\it degree-maximal} if
its degree sequence is majorized by no other $k$-realizable partition.
Proposition \ref{shifted-graph} extends to higher dimensions in only
one direction, as the following proposition and example show.
\begin{proposition}\label{maximal-shifted}
If a $k$-family is degree-maximal, then it is shifted.
\end{proposition}
\begin{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$ {\it covers} $B$ in
$\leq_P$, then $A \in K$ implies $B \in K$. So assume $A
\in K$ and that $A$ covers $B$, i.e., $m \in B$, $m+1 \not\in B$,
and $A=B \backslash \{m\} \disun \{m+1\}$ for some $m$.
We will show $B \in K$.
Let $\balpha=\dd(K)$, and number the vertices of $K$ such that
$\degr(K,v)=\alpha_v$.
Let $\bbeta$ be the partition defined by
$\beta_m=\alpha_m+1$, $\beta_{m+1}=\alpha_{m+1}-1$,
and $\beta_j=\alpha_j$ for all other $j$.
Thus $\dd(K) = \balpha \maj \bbeta$, and so $\bbeta$ is not $k$-realizable,
because $K$ is degree-maximal. It follows
that $B \in K$;
for otherwise $\bbeta=\dd(K \backslash \{A\} \disun \{B\})$.
Therefore $K$ is shifted.
\end{proof}
\begin{example}\label{shifted-not-maximal}
We construct, for any $k \geq 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 $\leq_P$, and
let $K_1=K_0 \disun K'_1$ and
$K_2=K_0 \disun K'_2$.
It is not hard to verify that $K_1$ and $K_2$ are shifted, but that
$\dd(K_2) \majneq \dd(K_1).$
Therefore $K_2$ is shifted, but not degree-maximal.
For $k>3$, simply append
new vertices $v_1,\dots,v_{k-3}$ to every set in both $K_1$ and $K_2$ of
the previous example, and order the vertices
$v_1 < \dots < v_{k-3} < 1 < \dots < 10$.
\end{example}
Combining Propositions \ref{shifted-graph} and \ref{maximal-shifted},
and Example \ref{shifted-not-maximal}, 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.
\section{Numerology: Spectra and $h$-triangles of shifted complexes}
\label{numerology}
In this section we compare two natural isomorphism invariants of
shifted simplicial complexes -- their $h$-triangle as defined by
Bj\"orner and Wachs \cite{BjornerWachs1, BjornerWachs2} on the one
hand, and their Laplacian spectra (or equivalently their degree
sequences, by Theorem \ref{main-theorem}) 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\"orner and Wachs for arbitrary
simplicial complexes \cite[Definition 3.1]{BjornerWachs1}, but we will
use the following formulation, valid only for shifted complexes (see
\cite[Theorem 3.4]{BjornerWachs1} and
\cite[Corollary 11.4]{BjornerWachs2}): If $K$ is a shifted simplicial
complex, then
\begin{equation}\label{h-shift}
h_{k,i}(K) = \abs{\{\text{facets}\ F \in K\colon
\abs{F} = k,\ \init(F) = k - i\}},
\end{equation}
where
$$
\init(F) = \min\{r\colon r \not\in 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 \not\in F$).
For a pure $(d-1)$-dimensional shifted complex, then clearly the only
non-zero entries of the $h$-triangle are $\{h_{d,i}\colon
i=0,\ldots,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.
\begin{example}\label{same-h-diff-spectra}
We construct, for any $k \geq 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] \cup \{k,k+3\}$ or $A_2 = [k-2] \cup \{k+1,k+2\}$ in the
componentwise partial order $\leq_P$. Let $K_1=K_0 \disun \{A_1\}$
and $K_2=K_0 \disun \{A_2\}$. Clearly, $K_1$ and $K_2$ are shifted.
It is also easy to check, by Equation \eqref{h-shift}, that $K_1$ and
$K_2$ have the same $h$-triangle, but that, by Theorem
\ref{main-theorem}, they have different spectra.
\end{example}
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
degree-maximal graph completely determines the graph up to isomorphism
\cite[p.\ 290]{RuchGutman}. By Proposition
\ref{shifted-graph} and Theorem \ref{main-theorem}, 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 {\tt posets} \cite{Stembridge}) and proposition show.
\begin{example}\label{same-spectra-diff-complex}
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
$\leq_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 $\leq_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
$\dd_2(K_1) = \dd_2(K_2)$, and thus, by Theorem
\ref{main-theorem}, that $K_1$ and $K_2$ have the same
spectra.
\end{example}
\begin{proposition}\label{spectra2-h}
The spectra of a $2$-dimensional shifted complex determine its $h$-triangle.
\end{proposition}
\begin{proof}[Proof \textup{(}Sketch\textup{)}]
A series of routine exercises show that Equation \eqref{h-shift} implies
$h_{3,0}=1$,
$h_{0,0}=h_{1,0}=h_{2,0}=0$,
$h_{3,1}= \abs{\{v\colon \degr_2(K,v) > 0\}} - 3 =
(\dd_2)^T_1 -3 = (\s'_1)_1 - 3$, and
$h_{2,1} + h_{3,1} = \abs{\{v\colon \degr_1(K,v) > 0\}} - 3 =
(\dd_1)^T_1 -3 = (\s'_0)_1 - 3$.
Combining Theorem \ref{Hodge-theorem} with \cite[Corollary
4.2]{BjornerWachs1}, we see that
$h_{j,j}$ is the multiplicity of 0 in $\stot_{j-1}$, for $j=1,2,3$.
Finally, from Equation \eqref{h-shift}, 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 $\stot_2$.
\end{proof}
Finally, the following example shows how, for $3$-dimensional shifted
simplicial complexes, the spectra do not even determine the
$h$-triangle.
\begin{example}\label{same-spectra-diff-h}
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 $\leq_P$. Let
$K_1=K_0 \disun \{F_{11}, F_{12}\}$ and
$K_2=K_0 \disun \{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 \ref{main-theorem}, that $K_1$ and
$K_2$ have the same spectra, but, by Equation \eqref{h-shift},
different $h$-triangles.
\end{example}
\bigskip
We now outline how, on the other hand, the spectra of a {\it pure}
shifted complex naturally refine its $f$-vector and $h$-vector.
\begin{definition}
For a
simplicial complex $K$, and for $\lambda$ one of its possible eigenvalues,
let $\f{\lambda}{j-1}$ denote the multiplicity of eigenvalue $\lambda$
in $\stot_{j-1}(K)$. Similarly, for $\lambda \neq 0$, let
$\fp{\lambda}{j-1}$ denote the multiplicity of $\lambda$ in
$\s'_{j-1}(K)$.
\end{definition}
Note that the $\f{\lambda}{j-1}$ are a refinement of the $f$-vector, in that
\begin{equation}\label{f-sum}
\sum_\lambda \f{\lambda}{j-1}(K)
= \dim C_{j-1}(K;\reals) = f_{j-1}(K).
\end{equation}
Also note that Equation \eqref{s-union-minus} implies
\begin{equation}\label{f-fp}
\f{\lambda}{j-1} = \fp{\lambda}{j-1} + \fp{\lambda}{j-2}
\end{equation}
for $\lambda \neq 0$.
Recall the $h$-vector of a $(d-1)$-dimensional simplicial complex is
defined from the $f$-vector by
$$
\sum_{i=0}^d h_i(x+1)^{d-i} = \sum_{j=0}^d f_{j-1} x^{d-j}.
$$
We similarly define $\h{\lambda}{i}$ from $\f{\lambda}{j-1}$ and,
for $\lambda \neq 0$, $\hp{\lambda}{i}$ from $\fp{\lambda}{j-1}$ by
$$
\sum_{i=0}^d \h{\lambda}{i}(x+1)^{d-i} = \sum_{j=0}^d \f{\lambda}{j-1} x^{d-j}
$$
and
$$
\sum_{i=0}^{d-1} \hp{\lambda}{i}(x+1)^{(d-1)-i}
= \sum_{j=0}^{d-1}\fp{\lambda}{j-1} x^{(d-1)-j}.
$$
Since $h_i$ and each $\h{\lambda}{i}$ are defined from $f_{j-1}$ and
$\f{\lambda}{j-1}$ by the exact same linear equations, the linear relations
\eqref{f-sum}
imply the corresponding relations
\begin{equation}\label{sum-h}
\sum_{\lambda} \h{\lambda}{i} = h_i.
\end{equation}
\begin{proposition}\label{add-zero}
For $\lambda \neq 0$,
$$
\h{\lambda}{i}=
\begin{cases}
\hp{\lambda}{i} & \text{if $i \leq d-1$}\\
0 & \text{if $i=d$}
\end{cases}.
$$
\end{proposition}
In other words, the refined $\h{\lambda}{ }$-vector
$(\h{\lambda}{0},\ldots,\h{\lambda}{d})$ is just the refined
$\hp{\lambda}{ }$-vector $(\hp{\lambda}{0},\ldots,\hp{\lambda}{d-1})$
with an extra zero at the end.
The proof of Proposition \ref{add-zero} consists of routine summation
manipulations using the definitions of $\h{\lambda}{i}$ and
$\hp{\lambda}{i}$, and Equation \eqref{f-fp}.
\begin{theorem}\label{hp-positive}
Let $K$ be a pure $(d-1)$-dimensional shifted simplicial complex, and
$0 \leq i \leq d-1$. Then
$\hp{\lambda}{i}(K)$
equals the cardinality of the set
$$
\calS = \{\textup{facets}\ F \in K\colon \lambda \in F,\ \lambda+1 \not\in F,\
F \backslash \{\lambda\} \cup \{\lambda+1\} \not\in K,\
\init(F \backslash \{\lambda\}) = d-i-1\}.
$$
In particular, $\hp{\lambda}{i}(K)$ is nonnegative.
\end{theorem}
\begin{proof}[Proof \textup{(}Sketch\textup{)}]
It is not hard to see that, because $K$ is shifted,
\begin{align*}
\abs{\calS} &=\abs{\{\text{facets}\ F \in K\colon
\lambda \in F,\ \lambda+1 \not\in F,\,
\init(F \backslash \{\lambda\})=d-i-1\}}\\
&\quad -\abs{\{\text{facets}\ H \in K\colon
\lambda \not\in H,\ \lambda+1 \in H,\, \init(H)=d-i-1\}}.
\end{align*}
It thus suffices to find a way to build $K$ one facet at a time, such
that when facet $F$ is added:
if either $\lambda,\lambda+1 \in F$ or $\lambda,\lambda+1 \not\in F$,
then $\hp{\lambda}{}$ is unchanged;
if $\lambda \in F$ and $\lambda+1 \not\in F$,
then $\hp{\lambda}{}$ just increases by one in the $i$th component,
where $\init(F \backslash \{\lambda\}) = d-i-1$; and
if $\lambda \not\in F$ and $\lambda+1 \in F$,
then $\hp{\lambda}{}$ just decreases by one in the $i$th 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 {\it reverse lexicographic order}
because this order is a {\it shelling order}
\cite[Corollary 11.4]{BjornerWachs2}. It is necessary to use Theorem
\ref{main-theorem} here, but in the following equivalent formulation:
For any shifted family $K$, the multiplicity of $\lambda$ in $\s(K)$
equals the number of sets $A$ of $K$ such that $\lambda \in A$,
$\lambda+1 \not\in A$, and $A \backslash \{\lambda\} \cup
\{\lambda+1\} \not\in K$.
\end{proof}
\begin{corollary}\label{h-positive}
For a pure $(d-1)$-dimensional shifted simplicial complex,
the numbers $\h{\lambda}{i}$ nonnegatively refine the usual $h$-vector; i.e.,
$\sum_\lambda \h{\lambda}{i} = h_i$ for all $i$, and $\h{\lambda}{i}
\geq 0$ for all $\lambda$ and $i$.
\end{corollary}
\begin{proof}
Combine Theorem \ref{hp-positive}, Equation \eqref{sum-h}, and Proposition
\ref{add-zero}.
\end{proof}
\section{Acknowledgements}
The authors thank Alan Edelman for Remark \ref{singular-values},
Eric Babson for Proposition \ref{consistent-with-joins},
Xun Dong for the proof of Proposition \ref{Dong-prop},
John Stembridge for help in using his MAPLE package {\tt posets}
to find Example \ref{same-spectra-diff-complex},
and the referee for suggested improvements.
\bibliographystyle{amsplain}
\begin{thebibliography}{99}
\bibitem{Adin}
R. M. Adin,
\textit{Counting colorful multi-dimensional trees},
Combinatorica \textbf{12} (1992), 247--260.
\bibitem{AndersonMorley}
W. N. Anderson and T. D. Morley,
\textit{Eigenvalues of the Laplacian of a graph},
Univ.\ of Maryland Tech.\ Report \textbf{TR-71-45} (1971);
Linear and Multilinear Algebra \textbf{18} (1985), 141-145.
\bibitem{BjornerKalai}
A. Bj\"orner and G. Kalai,
\textit{An extended Euler-Poincar\'e theorem},
Acta Math.\ \textbf{161} (1988), 279--303.
\bibitem{BjornerWachs1}
A. Bj\"orner and M. Wachs,
\textit{Shellable nonpure complexes and posets. I},
Trans.\ Amer.\ Math.\ Soc.\ \textbf{348} (1996),
1299--1327.
\bibitem{BjornerWachs2}
%A. Bj\"orner and M. Wachs,
\bysame,
\textit{Shellable nonpure complexes and posets. II},
Trans.\ Amer.\ Math.\ Soc.\ \textbf{349} (1997),
3945--3975.
\bibitem{Chung}
F. Chung,
\textit{The Laplacian of a hypergraph},
DIMACS Ser.\ in Discrete Math.\
Theoret.\ Comput.\ Sci.\ \textbf{10} (1993), 21-36.
\bibitem{Chung-book}
%F. R. K. Chung,
\bysame,
\textit{Spectral Graph Theory},
CBMS Reg.\ Conf.\ Ser.\ in Math. \textbf{92},
Amer.\ Math.\ Soc., Providence, RI, 1997.
\bibitem{ChvatalHammer}
V. Chvatal and P. L. Hammer,
\textit{Aggregation of inequalities in integer programming},
Studies in integer programming
(P. Hammer, et.\ al., eds.);
\textit{Ann.\ Discrete Math.}\ \textbf{1} (1977),
145--162.
\bibitem{CDS}
D. M. Cvetkovi\'c, M. Doob, and H. Sachs,
\textit{Spectra of Graphs. Theory and Applications}, 3rd ed.,
Johann Ambrosius Barth, Heidelberg, 1995.
\bibitem{DongWachs}
X. Dong and M. Wachs,
\textit{Combinatorial Laplacian of the matching complex},
Electron.\ J. Combin. \textbf{9} (2002), \#R17, 11 pp.
\bibitem{Eckmann}
B. Eckmann,
\textit{Harmonische Funktionen und Randwertaufgaben in einem Komplex},
Comment.\ Math.\ Helv.\ \textbf{17} (1945), 240-255.
\bibitem{Faria}
I. Faria,
\textit{Multiplicity of integer roots of polynomials of graphs},
Linear Algebra Appl.\ \textbf{229} (1995), 15--35.
\bibitem{Fiedler}
M. Fiedler,
\textit{Algebraic connectivity of graphs},
Czechoslovak Math.\ J. \textbf{23}
(1973), 298-305.
\bibitem{Forman}
R. Forman,
\textit{Combinatorial differential topology and geometry},
New perspectives in algebraic combinatorics,
Math.\ Sci.\ Res.\ Inst.\ Publ.\ \textbf{38}, 1999.
\bibitem{Friedman}
J. Friedman,
\textit{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.
\bibitem{FriedmanHanlon}
J. Friedman and P. Hanlon,
\textit{On the Betti numbers of chessboard complexes},
J. Algebraic Combin.\ \textbf{8} (1998), 193--203.
\bibitem{Gershgorin}
S. Gershgorin,
\textit{\"Uber die Abgrenzung der Eigenwerte einer Matrix},
Izv.\ Akad.\ Nauk.\ USSR Otd.\ Fiz.-Mat.\ Nauk \textbf{7} (1931),
749-754.
\bibitem{Grone}
R. Grone,
\textit{Eigenvalues and the degree sequence of graphs},
Linear and Multilinear Algebra \textbf{39} (1995), 133-136.
\bibitem{GroneMerris}
R. Grone and R. Merris,
\textit{The Laplacian spectrum of a graph II},
SIAM J. Discrete Math.\ \textbf{7} (1994), 221--229.
\bibitem{HammerKelmans}
P. L. Hammer and A. K. Kelmans,
\textit{Laplacian spectra and spanning trees of threshold graphs},
Discrete Appl.\ Math.\ \textbf{65} (1996), 255--273.
\bibitem{Kalai}
G. Kalai,
\textit{Enumeration of ${Q}$-acyclic simplicial complexes},
Israel J. Math.\ \textbf{45} (1983), 337--351.
\bibitem{Kirchhoff}
G. Kirchhoff,
\textit{\"Uber de Aufl\"osung der Gleichungen auf welche man bei der Untersuchen der
linearn Vertheilung galvanischer Str\"ome gef\"uht wird},
Ann.\ Der Phys.\ und Chem.\ \textbf{72} (1847), 495-508.
\bibitem{KookReinerStanton}
W. Kook, V. Reiner, and D. Stanton,
\textit{Combinatorial Laplacians of matroid complexes},
J. Amer.\ Math.\ Soc.\ \textbf{13} (2000), 129--148.
\bibitem{Macdonald}
I. G. Macdonald,
\textit{Symmetric Functions and Hall Polynomials}, 2nd ed.,
Oxford University Press, New York, 1995.
\bibitem{MarshallOlkin}
A. W. Marshall and I. Olkin,
\textit{Inequalities: Theory of Majorization and its Applications},
Academic Press, New York, 1979.
\bibitem{Merris}
R. Merris,
\textit{Degree maximal graphs are Laplacian integral},
Linear Algebra Appl.\ \textbf{199} (1994), 381--389.
\bibitem{Merris-survey}
%R. Merris,
\bysame,
\textit{Laplacian matrices of graphs: a survey}
Linear Algebra Appl.\ \textbf{197/198} (1994), 143--176.
\bibitem{Munkres}
J. R. Munkres,
\textit{Elements of Algebraic Topology},
Addison-Wesley, Menlo Park CA, 1984.
\bibitem{PeledSrinivasan}
U. Peled and M. Srinivasan,
\textit{The polytope of degree sequences},
Linear Algebra Appl.\ \textbf{114/115} (1989), 349--377.
\bibitem{RuchGutman}
E. Ruch and I. Gutman,
\textit{The branching extent of graphs},
J. Combin.\ Inform.\ System Sci.\
\textbf{4} (1979), 285--295.
\bibitem{Stembridge}
J. Stembridge, The MAPLE package {\tt posets},
available at \\
%{\tt http://www.math.lsa.umich.edu/\verb+~+jrs/maple.html\#posets}.
{\tt http://www.math.lsa.umich.edu/\textasciitilde jrs/maple.html\#posets}.
\end{thebibliography}
\end{document}