\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P15}{20(3)}{2013}
\usepackage{amssymb,amsthm,amsmath}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=black]{hyperref}
\usepackage{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{discussion}[theorem]{Discussion}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Balanced vertex decomposable simplicial complexes and their
$h$-vectors}
\author{Jennifer Biermann\\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small Mt. Holyoke College\\[-0.8ex]
\small South Hadley, MA, USA\\
\small \tt jbierman@mtholyoke.edu\\
\and
Adam Van Tuyl\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Lakehead University\\[-0.8ex]
\small Thunder Bay, ON, Canada\\
\small \tt avantuyl@lakeheadu.ca\\
\date{\dateline{July 14, 2012}{Jul 27, 2013}{Aug 9, 2013}\\
\small Mathematics Subject Classifications: 05E45, 05A15, 13F55}
}
\begin{document}
\maketitle
\begin{abstract}
Given any finite simplicial complex $\Delta$, we show how to construct
from a colouring $\chi$ of $\Delta$
a new simplicial complex $\Delta_{\chi}$ that is balanced
and vertex decomposable. In addition,
the $h$-vector of $\Delta_{\chi}$ is precisely
the $f$-vector of $\Delta$.
Our construction generalizes the ``whiskering'' construction
of Villarreal, and Cook and Nagel. We also
reverse this construction to prove a special case of a conjecture
of Cook and Nagel, and Constantinescu and Varbaro on the
$h$-vectors of flag complexes.
\bigskip\noindent \textbf{Keywords:} simplicial complex, vertex decomposable, flag complex, $h$-vector
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
The work of this paper was inspired by the ``whiskering'' construction
of finite simple graphs found in work of
Villarreal \cite{V} and Cook and Nagel \cite{CN}. Given a finite
graph $G = (V_G,E_G)$ on the vertex set $V_G = \{x_1,\ldots,x_n\}$,
Villarreal constructed a new graph, denoted $G^W$, on the vertex set
$\{x_1,\ldots,x_n,y_1,\ldots,y_n\}$ by adjoining the edges $\{x_i,y_i\}$
for every $i$ to the graph $G$. The new graph has a ``whisker'' at every
vertex of the original graph. As discovered by Villarreal,
the edge ideal of the new graph $G^W$, that is,
\[I(G^W) =
\langle w_iw_j ~~|~ \{w_i,w_j\} \in E_{G^W} \rangle \subseteq R =
k[x_1,\ldots,x_n,y_1,\ldots,y_n]\]
has the property that $R/I(G^W)$ is Cohen-Macaulay. It was later observed by
Dochtermann and Engstr\"om \cite{DE} and Woodroofe \cite{W}, and generalized by
Cook and Nagel \cite{CN}, that one could deduce this result
by studying the topological properties of the
simplicial complex associated to $I(G^W)$ via the Stanley-Reisner
correspondence. In particular, Villarreal's construction can be viewed
as creating a new independence complex $\Delta'$
(sometimes called a flag complex)
from the independence complex $\Delta$ of $G$. This new complex
$\Delta'$ is vertex decomposable (as defined by Provan and Billera \cite{BP}),
and it is this topological property that implies that $R/I(G^W)$
is Cohen-Macaulay.
Our entry point is to ask whether there is a more general
theory that can be applied to all simplicial complexes. Moreover, we want
this general theory to specialize to known cases for flag complexes.
In Section 3 we will show that a general construction exists using the notion
of a colouring $\chi$ of a simplicial complex $\Delta$.
From the colouring $\chi$ and complex $\Delta$, we make a new complex,
denoted $\Delta_{\chi}$. Regardless
of how one colours $\Delta$, the construction of $\Delta_{\chi}$ always results
in a balanced vertex decomposable simplicial complex
(see Theorem \ref{vertex decomposable}).
It should be noted that
this construction has appeared in several guises over the years (see
Remark \ref{otherconstructions} and Discussion \ref{discussion}).
The consequences of our results are explored in Section 4.
In particular, it is shown that the $f$-vector of a simplicial
complex is also the $h$-vector of a balanced vertex decomposable simplicial complex.
Although this result is implicit in work
of Bj\"orner, Frankl, and Stanley \cite{BFS}, to the best of our knowledge, this fact
has not explicitly appeared in the literature (although the case of flag complexes
occurs in \cite{CN}).
We also show that the graded Betti
numbers of the Stanley-Reisner ideal of the Alexander dual of $\Delta_{\chi}$
can be expressed directly in terms
of the $f$-vector of $\Delta$ (see Theorem \ref{bettinumbers}).
Section 5 describes when our construction can be reversed, i.e.,
starting with a balanced vertex decomposable simplicial complex $\Delta$, we
construct another simplicial complex $\Delta'$ such that $f$-vector
of $\Delta'$ is the same as the $h$-vector of $\Delta$. We use this procedure to prove that
the set of $f$-vectors of independence complexes of chordal graphs is precisely
the set of $h$-vectors of balanaced vertex decomposable independence complexes
of chordal graphs.
Our result is a special case of a conjecture of Cook and Nagel \cite{CN} and
Constantinescu and Varbaro \cite{CV} that the set of $f$-vectors of flag
complexes is precisely the set of $h$-vectors of balanced vertex
decomposable flag complexes.
As a final comment, we do not discuss the ``whiskering'' procedure
found in \cite{FH} in which
whiskers are added to only some of the vertices. This idea is explored
in \cite{BFHVT}.
\bigskip
\noindent
{\bf Acknowledgements.}
We thank Uwe Nagel and the referees for their invaluable comments.
The authors made use of the computer
programs {\tt CoCoA} \cite{C} and {\em Macaulay 2} \cite{Mt}, including the {\em Macaulay 2}
package \cite{Ct}.
The second author acknowledges the support of NSERC.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Background}
We work over the polynomial rings
$S = k[x_1, \dots, x_n]$ and $R= k[x_1, \dots, x_n, y_1, \dots, y_s]$
where $k$ is any field. Let $\Delta$ be a finite simplicial complex on vertex set $\{x_1, \dots, x_n\}$ of dimension $d$. We say $\Delta$ is {\it pure} if all its facets (maximal elements)
have the same cardinality.
An important combinatorial invariant of $\Delta$ is its
\emph{$f$-vector}, that is, the vector $f(\Delta) = (f_{-1}, f_0, \dots, f_d)$ where $f_i$ denotes the number of faces of $\Delta$ of dimension $i$.
If $\sigma \in \Delta$, then the
{\it deletion} of $\sigma$ is the simplicial complex $\Delta \setminus \sigma = \{ \tau \in \Delta ~|~ \sigma \not \subseteq \tau\}$, and the {\it link} of $\sigma$
is $\rm{link}_{\Delta}(\sigma) = \{ \tau \in \Delta ~|~ \sigma \cap \tau =
\emptyset, \sigma \cup \tau \in \Delta\}$. When $\sigma = \{v\}$, we shall abuse notation and
write $\Delta \setminus v$ (respectively ${\rm link}_{\Delta}(v)$).
With this notation,
we introduce a family of
complexes due to Provan and Billera \cite{BP}.
\begin{definition} A pure simplicial complex $\Delta$
is called \emph{vertex decomposable} if
$(i)$
$\Delta$ is a simplex, or
$(ii)$ there exits $v \in V$ such that $\Delta \setminus v$ and
${\rm link}_\Delta(v)$ are vertex decomposable.
\end{definition}
Key to the main construction studied in this paper is the notion
of a colouring.
\begin{definition} Let $\Delta$ be a simplicial complex on the vertex set $V$
with facets $F_1, \dots, F_t$.
An {\it s-colouring} of $\Delta$ is a partition of the vertices
$V = V_1\cup \dots \cup V_s$ (where the sets $V_i$ are allowed to be empty) such that
$|F_i \cap V_j| \leq 1$
for all
$1 \leq i \leq t, 1 \leq j \leq s$.
We will sometimes write $\chi$ is an $s$-colouring of $\Delta$
to mean $\chi$ is a specific partition of $V$ that gives an $s$-colouring of $\Delta$.
If there exists an $s$-colouring, we say that
$\Delta$ is \emph{s-colourable}.
If $\Delta$ has dimension $d-1$, then we say that
$\Delta$ is \emph{balanced} if it is $d$-colourable.
\end{definition}
We will be interested in how our results specialize
to independence complexes of graphs, sometimes called {\it flag complexes}.
Recall that if $G = (V_G,E_G)$ is a finite simple graph
with vertex set $V_G = \{x_1,\ldots,x_n\}$ and edge set $E_G$,
then a subset $W \subseteq V_G$ is an {\it independent set} of a graph
$G$ if for every edge $e \in E_G$, we have $e \not\subseteq W$.
The {\it independence complex} of $G$, denoted ${\rm Ind}(G)$, is the
simplicial complex defined by
\[{\rm Ind}(G) = \{W \subseteq V_G ~|~ \mbox{$W$ is an independent set of $G$}\}.\]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A construction and its properties}
Starting with a simplicial complex $\Delta$ and an $s$-colouring $\chi$, we
introduce a procedure to construct a new simplicial complex that is
pure of dimension $s-1$, balanced,
and vertex decomposable.
\begin{construction}\label{DeltaChi} Let $\Delta$ be a simplicial complex on the
vertex set $\{x_1, \dots, x_n\}$. Given an $s$-colouring $\chi$ of $\Delta$
given by $V= V_1 \cup \dots \cup V_s$, we define $\Delta_\chi$ on vertex set \\
$\{x_1, \dots, x_n, y_1, \dots, y_s\}$ to be the simplicial complex with
faces $\sigma \cup \tau$ where $\sigma$ is a face of $\Delta$ and $\tau$ is
any subset of $\{y_1,\dots, y_s\}$ such that for all $y_j \in \tau$ we have
$\sigma \cap V_j = \emptyset$.
\end{construction}
\begin{remark}\label{otherconstructions}
Construction \ref{DeltaChi} was introduced independently by
Frohmader \cite[Construction 7.1]{F}. However, the construction appears implicitly
in earlier work \cite[Section 5]{BFS}, although it is only applied
to compressed multicomplexes.
Another variation appears in work of Hetyei (see \cite[Definition 4.2]{H}).
The whiskering constructions found in \cite{CN,V}
for flag complexes become special cases of Construction \ref{DeltaChi}.
For example, Villarreal's construction in \cite{V}
of adding whiskers to every vertex of a graph $G$, and
studying the resulting independence complex
corresonds to the colouring $V =\{x_1\} \cup \{x_2\} \cup \cdots \cup \{x_n\}$
and applying Construction \ref{DeltaChi} to ${\rm Ind}(G)$.
We point the reader to \cite{F} which makes the connection to Cook and Nagel's
clique whiskering
more explicit.
\end{remark}
Observe that each $s$-colouring $\chi$ of $\Delta$ creates a new
simplicial complex $\Delta_{\chi}$. Even though these simplicial
complexes $\Delta_{\chi}$ may be different, they all share some interesting properties.
\begin{theorem} \label{correspondence}
The facets of $\Delta_\chi$ are in one-to-one
correspondence with the faces of the original simplicial complex $\Delta$.
In addition, $\Delta_\chi$ is pure of dimension $s-1$ and balanced.
\end{theorem}
\begin{proof}
Let $V = V_1\cup \cdots \cup V_s$ be the colouring of $\Delta$ given by $\chi$.
From the definition of $\Delta_\chi$, the maximal faces are those of the
form $\sigma \cup \{y_j ~|~ V_j \cap \sigma = \emptyset\}$ where $\sigma$ is a
face of $\Delta$. This establishes the one-to-one correspondence.
If we partition the vertices of
$\Delta_\chi$ as
$
\{x_1, \dots, x_n, y_1, \dots, y_s\} = V_1' \cup V_2' \cup \dots \cup V_s'
$
where $V_j' = V_j \cup \{y_j\}$, then this partition gives
an $s$-colouring of $\Delta_{\chi}$. We can see from the characterization of the
facets of $\Delta_\chi$ that each
facet contains exactly one vertex from each
of the sets $V_1', \dots, V_s'$, and hence $\Delta_\chi$ is pure of dimension $s-1$ as well as balanced.\end{proof}
\begin{example}
Let $\Delta = \langle x_1x_2x_3, x_2x_4, x_3x_4\rangle$ and let $\chi$ be the colouring given by $\{x_1, x_4\} \cup \{x_2\} \cup \{x_3\}$.
The faces of $\Delta$ are
$\{\emptyset, x_1, x_2, x_3, x_4, x_1x_2, x_2x_3, x_1x_3, x_2x_4, x_3x_4, x_1x_2x_3\}.
$
These are in one-to-one correspondence with the facets of $\Delta_\chi$:
\begin{align*}
\Delta_\chi = &\langle y_1y_2y_3, x_1y_2y_3, x_2y_1y_3, x_3y_1y_2, x_4y_2y_3, x_1x_2y_3, x_2x_3y_1, x_1x_3y_2, x_2x_4y_3, x_3x_4y_2, x_1x_2x_3\rangle.
\end{align*}
\end{example}
We come to the main result of this section.
\begin{theorem} \label{vertex decomposable}
For any simplicial complex $\Delta$, and any $s$-colouring $\chi$ of $\Delta$,
the simplicial complex $\Delta_\chi$ is vertex decomposable.
\end{theorem}
\begin{proof}
We proceed by induction on the number of vertices of $\Delta$.
If $\Delta$ is the simplicial complex consisting of a
single vertex $x_1$, then the only possible colourings of the
vertices of $\Delta$ are of the form $V = V_1\cup \dots \cup V_s$ where $V_1 = \{x_1\}$ and $V_2, \dots, V_s$ are empty. In this case $\Delta_\chi = \langle x_1y_2\dots y_s, y_1y_2\dots y_s\rangle$. This complex is vertex decomposable because $\Delta_\chi \setminus x_1 = \langle y_1y_2\dots y_s\rangle$ and ${\rm link}_{\Delta_\chi}(x_1) = \langle y_2\dots y_s\rangle$ are both simplices.
Now suppose that $\Delta$ is a simplicial complex
on the vertex set $V = \{x_1, \dots, x_n\}$, and let $\chi$ be
the $s$-colouring of $\Delta$ given by $V = V_1 \cup \cdots \cup V_s$.
We will show that we can decompose $\Delta_\chi$ by decomposing at any
vertex $x_i$. Let $g_1,\dots, g_t$ be the faces of $\Delta$ and define
$g_i' = \{y_j ~|~ V_j \cap g_i = \emptyset\}$.
So $g_1 \cup g_1', \dots, g_t \cup g_t'$ are the facets of $\Delta_\chi$.
We must show that both $\Delta_\chi \setminus x_i$ and ${\rm link}_{\Delta_\chi}(x_i)$ are
vertex decomposable. First consider $\Delta_\chi \setminus x$. We assume that the facets of
$\Delta_\chi$ are ordered so that the facets $g_1 \cup g'_1, \dots, g_r \cup g'_r$ do not
contain the vertex $x_i$ and the facets $g_{r+1}\cup g'_{r+1}, \dots, g_t \cup g'_t$ do
contain $x_i$. So
\[
\Delta \setminus x_i
= \{\mbox{faces of } \Delta \mbox{ which do not contain } x_i\} = \{g_1, \dots, g_r\}.
\]
Note that we are using the fact that $g_1,\ldots,g_r,g_{r+1},
\ldots,g_t$ is a complete list of the faces of $\Delta$ by Theorem \ref{correspondence}.
Without loss of generality we may assume that $x_i \in V_1$. Then
$V \setminus \{x_i\} = (V_1 \setminus \{x_i\})
\cup V_2 \cup \dots \cup V_s$ is an $s$-colouring of $\Delta \setminus x_i$. Call this $s$-colouring $\chi'$.
Then
$(\Delta \setminus x_i)_{\chi'} = \langle (g_1 \cup g'_1),
\ldots, (g_r \cup g'_r)\rangle = \Delta_\chi \setminus x_i$.
Since $\Delta \setminus x_i$ is a simplicial complex on
fewer than $n$ vertices, $(\Delta \setminus x_i)_{\chi'}$ is vertex decomposable.
Now consider the link. Since $(g_{r+1} \cup g'_{r+1}), \dots, (g_t \cup g'_t)$
are the facets of $\Delta_\chi$ which contain $x_i$,
\begin{align*}
{\rm link}_{\Delta_\chi}(x_i) &= \langle (g_{r+1}\cup g'_{r+1}) \setminus \{x_i\}, \dots, (g_t \cup g'_t) \setminus \{x_i\} \rangle\\
&= \langle ((g_{r+1}\setminus \{x_i\}) \cup g'_{r+1}), \dots, ((g_t \setminus \{x_i\}) \cup g'_t) \rangle \, .
\end{align*}
For each $1 \leq j \leq s$, set
$W_j = \{x_\ell \in V_j ~|~ x_\ell \in {\rm link}_\Delta (x_i)\}$. Note that some of these sets
may be empty. Then $W = W_1\cup \dots \cup W_s$ is an $s$-colouring of
${\rm link}_{\Delta}(x_i)$. We call this $s$-colouring $\chi''$. Then
\[
({\rm link}_{\Delta}(x_i))_{\chi''} = {\rm link}_{\Delta_\chi}(x_i)
\]
and by induction $({\rm link}_{\Delta}(x_i))_{\chi''}$ is vertex decomposable.
\end{proof}
The fact that $\Delta_{\chi}$ is vertex decomposable has the following consequence.
\begin{definition} A pure simplicial complex $\Delta$ is \emph{shellable} if there is an ordering $F_1,\ldots,F_s$ on the facets of $\Delta$
such that for all $1 \leq i < j \leq s$ there exists some $v \in F_j \setminus F_i$ and some $\ell \in \{1, \dots, j-1\}$ with $F_j \setminus F_\ell = \{v\}$. Such an ordering on the facets is called a \emph{shelling order}.
\end{definition}
\begin{corollary}\label{shellingOrder}
For any simplicial complex $\Delta$, and any $s$-colouring $\chi$ of $\Delta$,
the complex $\Delta_\chi$ is shellable (and Cohen-Macaulay).
Also, any order of the facets of $\Delta_\chi$ which refines the
order given by ordering the faces of $\Delta$ by increasing dimension is a shelling order.
\end{corollary}
\begin{proof}
By Theorem \ref{vertex decomposable}, $\Delta_\chi$ is vertex decomposable, so by \cite[Corollary 2.9]{BP} it is also shellable, and consequently, Cohen-Macaulay
(e.g, see \cite[Theorem 8.2.6]{HH}).
For the rest, let $F_1, \dots F_s$ be the facets of $\Delta_\chi$.
By Theorem \ref{correspondence}, each $F_i = g_i \cup g'_i$
where $g_i$ is a face of $\Delta$ and
$g'_i = \{y_j ~|~ V_j \cap g_i = \emptyset\}$.
We order the facets $F_1, \dots F_s$ so that $\dim g_i \leq \dim g_j$ if $i