%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{88}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{example}[thm]{Example}
\newtheorem{question}[thm]{Question}
\newtheorem{prob}[thm]{Problem}
%\usepackage{lipsum}

\newcommand\st{\operatorname{\text{star}_{\mathcal M}}}
\newcommand\lk{\operatorname{\text{$\ell$k}}}   %Macro for link
\newcommand\lkc{\operatorname{\lk_{\Delta}}}
\newcommand\stc{\operatorname{\text{star}_{\Delta}}}
\newcommand\delc{\operatorname{\text{del}_{\Delta}}}


\newcommand\del{\operatorname{\text{del}}}



\newcommand\delci{\operatorname{\text{del}_{\Delta_i}}} 
\newcommand\lkcp{\operatorname{\lk_{\Delta^\prime}}}
\newcommand\lkci{\operatorname{\text{\lk_{\Delta_i}}}}
\newcommand\stcp{\operatorname{\text{star}_{\Delta^\prime}}}
\newcommand\delcp{\operatorname{\text{del}_{\Delta^\prime}}} 
\newcommand{\F}{\mathcal{F}}
\newcommand{\M}{\mathcal{M}}


%% define your title in the usual way
\title{Completing and extending shellings
of vertex decomposable complexes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Michaela Coleman\addressmark{1}, Anton Dochtermann\addressmark{2}, Nathan Geist\thanks{\href{mailto:nathan.geist@duke.edu}{nathan.geist@duke.edu}. The authors were supported by NSF-REU grant DMS-1757233.}\addressmark{3}, \and Suho Oh\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Tulsa, Tulsa, OK \\ \addressmark{2}Department of Mathematics, Texas State University, San Marcos, TX \\
\addressmark{3}Department of Mathematics, Duke University, Durham, NC}
%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We say that a pure $d$-dimensional simplicial complex $\Delta$ on $n$ vertices is \emph{shelling completable} if $\Delta$ can be realized as the initial sequence of some shelling of $\Delta_{n-1}^{(d)}$, the $d$-skeleton of the $(n-1)$-dimensional simplex. A well-known conjecture of Simon posits that any shellable complex is shelling completable. We prove that vertex decomposable complexes are shelling completable.  In fact we show that if $\Delta$ is a vertex decomposable complex then there exists an ordering of its ground set $V$ such that adding the revlex smallest missing $(d+1)$-subset of $V$ results in a complex that is again vertex decomposable. We explore applications to matroids, shifted complexes, as well as $k$-vertex decomposable complexes.  We also show that if $\Delta$ is a $d$-dimensional complex on at most $d+3$ vertices then the notions of shellable, vertex decomposable, shelling completable, and extendably shellable are all equivalent.}

%% put your French abstract here, or comment this out if you don't have one
%%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{extendable shellability, vertex decomposability, Simon's Conjecture}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{88Geist.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above


\section{Introduction}\label{sec:intro}
A pure simplicial complex $\Delta$ is \emph{shellable} if there exists an ordering of its facets $F_1, F_2, \dots, F_s$ such that each $F_i$ intersects the previous facets in a pure codimension one complex (see Definition \ref{defn:shellable}). Shellability is an important combinatorial tool that has consequences for the topology of $\Delta$ as well as algebraic properties of its Stanley--Reisner ring.  Examples of shellable simplicial complexes include the independence complexes of matroids \cite{ProBil}, boundary complexes of simplicial polytopes \cite{BruMan}, as well as the skeleta of shellable complexes \cite{BjoWac}.  In particular for any $k = 1, 2, \dots, n-1$ the $k$-skeleton of a simplex on vertex set $[n]$, which we denote $\Delta_{n-1}^{(k)}$, is shellable.   



Given a shellable complex a natural question to ask is whether one can get `stuck' in the process of building a shelling order.  A shellable complex $\Delta$ is said to be \emph{extendably shellable} if any shelling of a subcomplex of $\Delta$ can be extended to a shelling of $\Delta$.  Here a subcomplex of $\Delta$ is a simplicial complex on the same vertex set as $\Delta$, whose set of facets is a subset of the facets of $\Delta$.  

Although shellable complexes arise naturally in many contexts, it seems that extendably shellable complexes are harder to come by. Results of Danaraj and Klee \cite{DanKle} imply that any $2$-dimensional triangulated sphere (which is necessarily polytopal) is extendably shellable, and Kleinschmidt \cite{Kle} has shown that any $d$-dimensional sphere with $d+3$ vertices is extendably shellable. Bj\"orner and Eriksson \cite{BjoEri} proved that independence complexes of rank 3 matroids are extendably shellable. On the other hand Ziegler \cite{Zie} has shown that there exist simplicial 4-polytopes that are not extendably shellable. The motivation for much of our work will be the following question posed by Simon \cite{Sim}.


\begin{conj}[Simon's Conjecture] \cite{Sim}
The complex $\Delta_{n-1}^{(k)}$ is extendably shellable. 
\end{conj}

The $k=2$ case of Simon's Conjecture follows from \cite{BjoEri} by considering the uniform matroid of rank $3$, and Bigdeli, Yazdan Pour, and Zaare-Nahandi \cite{BPZDec} have established the $k \geq n-3$ cases (a simpler proof was provided independently by the second author \cite{Doc} based on results of Culbertson, Guralnik, and Stiller \cite{CulGurSti}). In \cite{CDGS} it is shown that if $\Delta$ is a $d$-dimensional simplicial complex on at most  $d+3$ vertices, then in fact the notions of shellable and extendably shellable are equivalent. This implies the $k = n-3$ case of Simon's conjecture and also provides a generalization of Kleinschmidt's results.  This result is also best possible in the sense that there are 2-dimensional complexes on 6 vertices that are not extendably shellable (\cite{MorTak}, \cite{Bjo}).  

Inspired by these results and observations, in this paper we consider a related notion. 

\begin{defn}
A pure $d$-dimensional simplicial complex $\Delta$ on $n$ vertices is said to be \emph{shelling completable} if there exists a shelling $F_1, F_2, \dots, F_s$ of $\Delta$ that can be taken as the initial sequence of some shelling of $\Delta_{n-1}^{(d)}$.
\end{defn}


In particular, a shelling completable complex is shellable.  Note that if $\Delta$ is shelling completable then any shelling of $\Delta$ can be completed to a shelling of $\Delta_{n-1}^{(d)}$.  Also note that Simon's conjecture is equivalent to the statement that any pure shellable complex is shelling completable.  From this perspective it is of interest to find a large class of shellable complexes that are shelling completable.


Our first examples of shelling completable complexes come from the class of shifted complexes. Recall that a simplicial complex is \emph{shifted} if there exists an ordering of its vertex set $V = \{1, 2, \dots, n\}$ such that for any face $\{v_1, v_2, \dots, v_k\}$ replacing any $v_i$ with a smaller vertex results in a $k$-set that is also a face.  Note that if $\Delta$ is a $d$-dimensional shifted complex according to some ordering on its vertex set then adding the reverse-lexicographically (revlex) smallest missing $(d+1)$-subset $F$ again results in a shifted complex (see Proposition \ref{prop:shift} below).  Since shifted complexes are known to be shellable \cite{BjoWac2}, this implies that shifted complexes are shelling completable.


%We can also phrase this condition using poset terminology.   Let $P_k$ denote the poset of length $k$ strings of increasing integers where $(x_1 < x_2 < \cdots < x_k)$ is less than $(y_1 < y_2 < \cdots < y_k)$ if $x_i \leq y_i$ for all $i$.  Then a pure simplicial complex $\Delta$ is shifted if its collection of facets form an order ideal in $P_{d-1}$. 

Shifted complexes are examples of the more general class of \emph{vertex decomposable complexes} (see Definition \ref{def:vd}), and our first result says that in fact all such complexes admit an ordering of its vertex set with this property. 

\newtheorem*{thm:vdextend}{Theorem \ref{thm:vdextend}}
\begin{thm:vdextend}
Suppose $\Delta$ is a $d$-dimensional vertex decomposable simplicial complex on ground set $V$. Then either $\Delta$ is full over $V$ or there exists a linear order on $V$ such that if $F$ is the revlex smallest $(d+1)$-subset of $V$ not contained in $\Delta$ then the simplicial complex generated by $\Delta \cup \{F\}$ is vertex decomposable.
\end{thm:vdextend}

As a corollary we obtain a large class of shelling completable complexes, providing a positive answer to a weakened version of Simon's Conjecture.

\newtheorem*{cor:VDcomplete}{Corollary \ref{cor:VDcomplete}}
\begin{cor:VDcomplete}
Vertex decomposable complexes are shelling completable.
\end{cor:VDcomplete}

Vertex decomposable complexes include pure shifted complexes and (independence complexes of) matroids. Theorem \ref{thm:vdextend} implies that there exists an ordering of the ground set of these complexes with the property that adding the revlex smallest missing $k$-subset results in a vertex decomposable complex. In the context of shifted complexes we have seen that the natural ordering of the ground set satisfies this property. For the case of matroids we prove that such \emph{decomposing orders} (see Definition \ref{defn:decomporder}) are easy to come by.

\newtheorem*{prop:matroids}{Proposition \ref{prop:matroids}}
\begin{prop:matroids}
Let $\M$ be a rank $d$ matroid on ground set $V$. Then any ordering $v_1, v_2, \dots, v_n$ of $V$ with the property that $\{v_1, v_2, \dots,v_d\} \in \M$ is a decomposing order.
\end{prop:matroids}

\noindent
In particular for a rank $d$ matroid $\M$ it is `easy' to find a $d$-subset $F$ of the ground set with the property that $\M \cup \{F\}$, while no longer a matroid, is still vertex decomposable.  

In the last part of the paper we consider shelling completable complexes with few vertices (relative to dimension).  We exploit a connection between chordal graphs and certain shellable complexes to prove the following.


\newtheorem*{thm:shellableVD}{Theorem \ref{thm:shellableVD}}
\begin{thm:shellableVD}
Suppose $\Delta$ is a shellable $d$-dimensional simplicial complex on $d+3$ vertices.  Then $\Delta$ is vertex decomposable (and hence shelling completable).
\end{thm:shellableVD}

This theorem, along with results from \cite{CDGS}, imply that for these complexes the notions of vertex decomposable, shellable, shelling completable, and extendably shellable are all equivalent.  



The rest of this extended abstract is organized as follows. In Section \ref{sec:VD} we recall some necessary definitions.  In Section \ref{sec:complete} we discuss the ideas behind Theorem \ref{thm:vdextend} along with relevant corollaries. In Section \ref{sec:matroids} we discuss the notion of decomposing orders in the context of matroids and Theorem \ref{prop:matroids}. In Section \ref{sec:few} we consider $d$-dimensional complexes on at most $d+3$ vertices and sketch the proof of Proposition \ref{thm:shellableVD}. We end in Section \ref{sec:further} with some discussion and open questions.  Throughout the paper we provide only the main ideas involved in our arguments, we refer to \cite{CDGO} for complete proofs.


\section{Vertex decomposable complexes}\label{sec:VD}

A \emph{simplicial complex} $\Delta$ on a finite ground set $V$ is a collection of subsets of $V$ that is closed under taking subsets, so that if $\sigma \in \Delta$ and $\tau \subset \sigma$ then $\tau \in \Delta$.  The elements of $\Delta$ are called \emph{faces}. Note that we do not require $\{v\} \in \Delta$ for all $v\in V$. The elements $v \in V$ such that $\{v\} \in \Delta$ will be called the \emph{vertices} of $\Delta$, whereas elements $w \in V$ that are not vertices will be called \emph{loops}. In particular the vertex set of $\Delta$ can be a proper subset of its ground set. As in \cite{Jon} we adopt the convention that the \emph{void complex} $\emptyset$ is a simplicial complex, distinct from the \emph{empty complex} $\{\emptyset\}$.  We will sometimes refer to the simplicial complex \emph{generated by} a collection of subsets $S \subset {\mathcal P}(V)$, by which we mean the smallest simplicial complex containing $S$.

 A \emph{facet} of $\Delta$ is an element that is maximal under inclusion. The \emph{dimension} of $\Delta$ is the largest cardinality (minus 1) of any facet. A simplicial complex $\Delta$ is \emph{pure} if all facets have the same cardinality.  For $W \subset V$ with $|W| = d+1$, we let $2^W$ denote the set of all subsets of $W$ and refer to it as a \emph{$d$-simplex} (on $W)$.  With these notions we can state the definition of a shellable complex.
 
\begin{defn}\label{defn:shellable}
 A pure $d$-dimensional simplicial complex $\Delta$ is said to be \emph{shellable} if there exists an ordering of its facets $F_1, F_2, \dots, F_s$ such that for all $k = 2,3, \dots, n$ the simplicial complex generated by
\[\big(\bigcup_{i=1}^{k-1} F_i  \big ) \cap F_ k\]
\noindent
is pure of dimension $d-1$.  By convention the void complex $\emptyset$ and the empty complex $\{\emptyset\}$ are both shellable.  
\end{defn}


Note that a shellable complex is connected as long as $d \geq 1$, and a $1$-dimensional simplicial complex (a graph) is shellable if and only if it is connected. We next recall the notion of link, star, and deletion of a face in a simplicial complex.


\begin{defn}
Suppose $\Delta$ is a simplicial complex on ground set $V$ and let $F \in \Delta$ be a face.  The  \emph{link},  \emph{star} and the \emph{deletion} of $F$ are defined as 
$$\lkc(F) := \{G \in \Delta : G \cap F = \emptyset, G \cup F \in \Delta\},$$
$$\stc(F) := \{G \in \Delta : F \subset G\},$$
$$\delc(F) := \{G \in \Delta: F \nsubseteq G\}.$$
The ground set of $\stc(F)$ is $V$, and the ground sets of $\lkc(F)$ and $\delc(F)$ are given by $V \backslash F$.  
\end{defn}

We note that shellability is preserved by taking links, a fact that will be useful later.

\begin{lem}[\cite{ZieLec}, Lemma 8.7]
\label{lem:linkshell}
If $\Delta$ is a shellable simplicial complex and $F \in \Delta$ is any face, then the link $\lkc(F)$ is shellable.
\end{lem}


We next define the class of vertex decomposable simplicial complexes recursively as follows.

\begin{defn}
\label{def:vd}
A simplicial complex $\Delta$ is \emph{vertex decomposable} if $\Delta$ is a simplex (including $\emptyset$ and $\{\emptyset\}$), or $\Delta$ contains a vertex $v$ such that
\begin{enumerate}
    \item both $\delc(v)$ and $\lkc(v)$ are vertex decomposable, and
    \item any facet of $\delc(v)$ is a facet of $\Delta$.
\end{enumerate}
A vertex $v$ that satisfies the second condition is called a \emph{shedding vertex} of $\Delta$. We will call a vertex $v$ that satisfies both conditions a \emph{decomposing vertex}.
\end{defn}


 Vertex decomposable complexes were introduced in the pure setting by Provan and Billera \cite{ProBil} and extended to non-pure complexes by Bj\"orner and Wachs \cite{BjoWac}.  It is known that any vertex decomposable complex is shellable, a fact implied by the following result of Wachs \cite{Wac}.

\begin{lem}[\cite{Wac}, Lemma 6]
Suppose $\Delta$ is a simplicial complex with shedding vertex $v$.  If both $\delc(v)$ and $\lkc(v)$ are shellable then $\Delta$ is shellable.
\end{lem}


%In what follows we will restrict ourselves to pure simplicial complexes.  Given two facets $F$ and $G$ of a pure $d$-dimensional simplicial complex $\Delta$ we say that $F$ and $G$ are \emph{adjacent} if they differ by one vertex, i.e. $|F \cap G| = d$.

%\begin{lem}
%\label{lem:shedd}
%Suppose $\Delta$ is a pure simplicial complex and let $v \in V$ be a vertex.  Then $v$ is a shedding vertex if and only if any facet of $\stc(v)$ is adjacent to some facet of $\delc(v)$.
%\end{lem}
%\begin{proof}
%For one direction suppose $v$ is a shedding vertex of $\Delta$ and let $F$ be a facet of $\stc(v)$. We have that $F \backslash \{v\}$ is a face of $\delc(v)$. Let $F'$ be a facet of $\delc(v)$ containing $F \backslash \{v\}$. Since $\Delta$ is pure and $v$ is a shedding vertex we have that $F'$ is a facet of $\Delta$, and hence has the same cardinality as $F$. We conclude that $F'$ is a facet of $\delc(v)$ adjacent to $F$.  

%For the other direction suppose $v$ is not a shedding vertex, so that some facet $F$ of $\delc(v)$ is not a facet of $\Delta$.  Let $F^\prime$ be a facet of $\Delta$ that contains $F$, so that $v \in F^\prime$. Since $\Delta$ is pure this implies that $F^\prime$ is a facet of $\stc(v)$.  But $F^\prime$ cannot be adjacent to any facet in $\delc(v)$ since $F$ was a facet of $\delc(v)$.
%\end{proof}


\section{Shelling completions}\label{sec:complete}

We next turn to the question of shelling completions for vertex decomposable complexes.  For this we will need the following concepts. Suppose $\Delta$ is a $d$-dimensional simplicial complex on ground set $V$.  We say that $\Delta$ is \emph{full (over $V$)} if it is the $d$-skeleton of the simplex over the vertex set $V$, i.e. it consists of all $d+1$-subsets of $V$.  Note that a $d$-simplex is full if and only if $|V| = d+1$.

We will also need the notion of reverse lexicographic (revlex) order on $k$-subsets of an ordered ground set. For this recall that if $V = \{1,2, \dots, n\}$ is a linearly ordered set, then $\{v_1 < v_2 < \cdots < v_k\}$ is \emph{revlex smaller} than $\{w_1 < w_2 < \cdots < w_k\}$ if for the largest $j$ with $v_j \neq w_j$ we have $v_j < w_j$.  Note that if one adds a new element $n+1$ to the set $V$ then any $k$-subset that contains $n+1$ will be revlex larger than any $k$-subset that does not contain $n+1$. 
%This implies the following observation.

%\begin{lem}\label{lem:revlex}
%Suppose $V$ is a finite linearly ordered set with largest element $v$, and suppose ${\mathcal F}$ is a collection $d$-subsets of $V$. Let ${\mathcal G} \subset {\mathcal F}$ denote the collection of those $d$-subsets $F \in {\mathcal F}$ such that $v \notin F$.  Then assuming ${\mathcal G} \neq \emptyset$, the revlex smallest element of ${\mathcal G}$ is also the revlex smallest element of ${\mathcal F}$. 
%\end{lem}

As mentioned in Section \ref{sec:intro} , we can use revlex orders to build new shifted complexes from existing ones. More precisely we have the following.

\begin{prop}\label{prop:shift}
Suppose $\Delta$ is a pure shifted $d$-dimensional simplicial complex with respect to some linear order on its ground set $V$, and assume that $\Delta$ is not full on $V$. Let $F$ be the revlex smallest $(d+1)$-subset of $V$ satisfying $F \notin \Delta$. Then the complex generated by $\Delta \cup \{F\}$ is again a shifted simplicial complex.
\end{prop}

\begin{proof}
One can see that replacing any element $x \in F$ with some $y \in V$ satisfying $y < x$ results in a $(d+1)$-subset $F^\prime = (F \backslash \{x\}) \cup \{y\}$ that is revlex smaller than $F$.  Hence $F^\prime$ is a facet of $\Delta \cup \{F\}$, implying that $\Delta \cup \{F\}$ is shifted.
\end{proof}

Our main result generalizes this observation for the class of vertex decomposable complexes.



\begin{thm}
\label{thm:vdextend}
Suppose $\Delta$ is a $d$-dimensional vertex decomposable simplicial complex on ground set $V$. Then either $\Delta$ is full over $V$ or there exists a linear order on $V$ such that if $F$ is the revlex smallest $(d+1)$-subset of $V$ not contained in $\Delta$ then the simplicial complex generated by $\Delta \cup \{F\}$ is vertex decomposable.
\end{thm}

\begin{proof}
(Sketch) We use induction on $d$, then on $n = |V|$. The base cases can be checked by hand so we assume $d \geq 1$ and  $n \geq d+2$.  First if $\Delta$ is full over its vertex set $W$ we pick any ordering on the ground set  $V$ so that all elements in $W$ are smaller than all elements in $V \backslash W$.   One can check that adding the revlex smallest missing $(d+1)$-subsets results in a vertex decomposable complex. If $\Delta$ is not full on its vertex set we can continue the induction by either picking $v$ to be a loop or a decomposing vertex.  If $v$ is a loop we consider the complex $\Delta$ on ground set $V \backslash \{v\}$ and use induction.   If $v$ is a decomposing vertex we have two subcases to consider.

If $\delc(v)$ is not full on its vertex set $V \backslash \{v\}$ then we consider the complex $\delc(v)$, and use induction on $n$ to extend the given ordering $V \backslash \{v\}$.  If $F$ is the  revlex smallest missing $(d+1)$-subset $F \subset V \backslash \{v\}$ can be added added to $\delc(v)$ to obtain another vertex decomposable complex, one can check that $F$ is revlex smallest among the missing facets of $\Delta$, and that the complex generated by $\Delta \cup \{F\}$ is also vertex decomposable (with decomposing vertex $v$).  If $\delc(v)$ is full on $V \backslash \{v\}$ then we consider the complex $\lkc(v)$ and use induction on $d$. We let $G$ denote the revlex smallest missing $d$-set of $\lkc(V)$.  One can show that $\{G \cup \{v\}\}$ is the revlex smallest missing $(d+1)$-subset of $\Delta$ and also that the complex generated by $\Delta \cup \{G \cup \{v\}\}$ is vertex decomposable. The result follows.
\end{proof}

For an illustration of the various steps in the above proof, we refer to Example~\ref{ex:decompose}. To establish our desired corollary we will next need the following observation.

\begin{lem}
\label{lem:bruno}
Suppose $\Delta$ is a shellable $d$-dimensional simplicial complex on ground set $V$ and suppose $F$ is a  $(d+1)$-subset of $V$ with the property that the complex $\Delta^\prime$ generated by $\Delta \cup \{F\}$ is again shellable.  Then any shelling of $\Delta$ can be extended to a shelling of $\Delta^\prime$ by adding $F$ as the last facet.
\end{lem}

%\begin{proof}
%Suppose $\Delta$, $F$, and $\Delta^\prime$ are as above and let $\Gamma$ denote the complex generated by the intersection of $F$ and $\Delta$. First note that it is enough to prove that $\Gamma$ is pure of dimension $d-1$, since then adding $F$ to any shelling of $\Delta$ satisfies the conditions of Definition \ref{defn:shellable}.  For the sake of contradiction suppose that $\Gamma$ has an inclusion-wise maximal face $G$ of dimension less than $d-1$.  Then the link $\lkcp(G)$ is disconnected since any facet of $\Delta$ containing $G$ cannot be adjacent to $F$. Since $G$ has dimension less than $d-1$ we also have that $\lkcp(G)$ has dimension at least one, which implies that $\lkcp(G)$ is not shellable. But since $\Delta^\prime$ is shellable, this provides a contradiction according to Lemma \ref{lem:linkshell}.
%\end{proof}



As a corollary we get a large class of complexes that are shelling completable, and hence we obtain a weakened form of Simon's conjecture.
\begin{cor}\label{cor:VDcomplete}
Vertex decomposable complexes are shelling completable.
\end{cor}

\begin{proof}
Suppose $\Delta$ is a pure $d$-dimensional vertex decomposable complex on ground set $V$, where $|V| = n$. Let $m$ be the number of $(d+1)$-subsets of $V$ that are missing as facets in $\Delta$. If $m=0$ then $\Delta = \Delta^{(d)}_{n-1}$ is full and we are done.  Otherwise by Theorem \ref{thm:vdextend} we have some $(d+1)$-subset $F \subset V$ such that $F \notin \Delta$ with $\Delta \cup \{F\}$ vertex decomposable, and hence shellable. From Lemma \ref{lem:bruno} we know that any shelling order of $\Delta$ can be extended to a shelling of $\Delta \cup \{F\}$. The result follows by induction on $m$.
\end{proof}


%\begin{rem} Our results also connect to notions of high-dimensional \emph{chordality} for simplicial complexes. For a pure $d$-dimensional simplicial complex $\Delta$ on vertex set $V$, a \emph{clique} is a subset $K \subset V$ such that either $|K| < d+1$ or else all $(d+1)$-subsets of $K$ appear among the facets of $\Delta$. We let $Cl(\Delta)$ denote the \emph{clique complex} of $\Delta$, by definition the simplicial complex whose faces are the cliques of $\Delta$.  In \cite{Nik} it is shown that if the Alexander dual of $Cl(\Delta)$ is vertex-decomposable, then $\Delta$ is \emph{ridge-chordal} in the sense of \cite{BPZSta}. This implies that if $\Delta$ is vertex-decomposable and not full, then there exists a $(d+1)$-subset $F$ such that $F \notin \Delta$ and such that $\Delta \cup \{F\}$ is shellable.  In other words the shelling can be continued for one more step. Our Corollary \ref{cor:VDcomplete} says that in fact the shelling can be completed to the full $d$-skeleton.
%\end{rem}

\section{Decomposing orders and matroid complexes}\label{sec:matroids}

Recall that a simplicial complex $\M$ is a \emph{matroid} if it is pure and its set of facets satisfy the following exchange property: If $F$ and $G$ are facets of $\M$ then for any $x \in F \backslash G$ there exists  some $y \in G \backslash F$ such that $(F \backslash \{x\}) \cup \{y\}$ is a facet of $\M$. The facets of $\M$ are usually called \emph{bases} in this theory. Also note that in some contexts this simplicial complex is called the \emph{independence complex} of $\M$ but we will simply refer it to as the matroid itself. It is well known that matroids are vertex decomposable \cite{ProBil} and hence Corollary \ref{cor:VDcomplete} implies the following.

\begin{cor}
Independence complexes of matroids are shelling completable.
\end{cor}

Given that any shelling of a rank $d$ matroid can be completed to a shelling of the full skeleton $\Delta_n^{(d-1)}$, a natural question to ask is whether one can control which facet can be added in the next step of the completion. In the context of matroids, one expects some flexibility since matroids themselves admit many shelling orders.   In particular recall that if $V = \{v_1, v_2, \dots, v_n\}$ is any ordering of the ground set of a rank $d$ matroid $\M$, then both lexicographic (\cite{Bjo} Theorem 7.3.4) and reverse lexicographic (\cite{GuoSheWu} Proposition 6.3) orderings of the facets (bases) of $\M$ give rise to a shelling of the complex $\M$. In fact matroids can be characterized by the property that any ordering of the ground set gives rise to such a shelling. For our purposes we will need the following notion.


\begin{defn}\label{defn:decomporder}
Suppose $\Delta$ is a a pure $d$-dimensional vertex decomposable simplicial complex.  An ordering $v_1, v_2, \dots, v_n$ of its ground set is a \emph{decomposing order} for $\Delta$ if the complex generated by $\Delta \cup \{F\}$ is again vertex decomposable, where $F$ is the revlex smallest $(d+1)$-subset of $V$ that is missing from $\Delta$.
\end{defn}



%From the inductive proof of that theorem we get the following recursive method for detecting whether a given ordering of the ground set is a decomposing order.

%\begin{cor}
%\label{cor:DO}
%Suppose $\Delta$ is a pure $d$-dimensional simplicial complex. A linear ordering $v_1,\ldots,v_n$ of its ground set is a decomposing order for $\Delta$ if one of the following is true:
%\begin{itemize}
%    \item $v_n$ is a loop and $v_1,\ldots,v_{n-1}$ is a decomposing order for $\Delta$ (on ground set $v_1, \ldots, v_{n-1}$),
%    \item $v_n$ is a decomposing vertex for $\Delta$, $\del_{\Delta}(v_n)$ is not full, and $v_1,\ldots,v_{n-1}$ is a decomposing order for $\del_{\Delta}(v_n)$,
%    \item $v_n$ is a decomposing vertex for $\Delta$, $\del_{\Delta}(v_n)$ is full, and $v_1,\ldots,v_{n-1}$ is a decomposing order for $\lk_{\Delta}(v_n)$,
%    \item $\Delta$ is full over its vertex set and any loop is bigger than any non-loop in this ordering.
%    \end{itemize}
%\end{cor}


Note that Theorem \ref{thm:vdextend} says that any vertex decomposable complex admits a decomposing order.  Also note that in the proof of Theorem \ref{thm:vdextend} at each step in the induction we must choose a vertex $v$ where we employ the inductive hypothesis on either the deletion $\delc(v)$ (in the first case) or the link $\lkc(v)$ (in the latter). In this way we can obtain a sequence of subcomplexes
\[\Delta = \Delta_n, \Delta_{n-1}, \dots, \Delta_s,\]
\noindent
where $n$ is the size of the ground set of $\Delta$, and $\Delta_s$ is a simplex over some (possibly smaller) ground set. We illustrate this process below with a worked example.  


\begin{example}
\label{ex:decompose}
Suppose $\Delta$ is the $3$-dimensional complex on ground set $\{1,2,\dots, 7\}$ with facets
\[\{1234, 1235,1245,1345,2345,1236,1246,1256,2356,1237, 2347\}.\]
Here we abuse notation and for example let $1245$ denote the $4$-subset $\{1,2,4,5\}$. We use the natural ordering on the ground set and verify that it is a decomposing order.

First we define $\Delta_7 = \Delta$ and note that
\[\text{del}_{\Delta_7}(7) = \{ 1234, 1235,1245,1345,2345,1236,1246,1256,2356\}\]
\noindent
is not full (e.g.\ $1346$ is missing).  Hence at this step we consider the deletion of vertex $7$ and define $\Delta_6 = \del_{\Delta_7}(7)$. Next we note that $\text{del}_{\Delta_6}(6)$ is full so we now consider the link of $6$ and define
\[\Delta_5 = \lk_{\Delta_6}(6) = \{123,124,125,235\}.\]

Continuing in this fashion we have that $\text{del}_{\Delta_5}(5)$ is not full so we define
\[\Delta_4 = \del_{\Delta_5}(5) = \{123,124\}.\]

Next we see that $\text{del}_{\Delta_4}(4) = \{123\}$ is full and so we consider the link of $4$ and have
\[\Delta_3 = \lk_{\Delta_4}(4) = \{12\}.\]

At this point we see that $\Delta_3$ is a simplex (on ground set $\{1,2,3\}$) and hence we have reached a base case.

Reversing this process, we see that at each step the addition of a new facet $F$ leads to a vertex decomposable complex. We begin with $\Delta_3$ since it is full over its vertex set, and hence a base case of Theorem \ref{thm:vdextend}. We extend $\Delta_3$ to $\Delta_3'$ by noting that $3$ is the smallest loop, and $2$ is the largest vertex.  Hence we add the facet $(12 \backslash \{2 \}) \cup \{3\} = 13$. Now in $\Delta_4$ we replace $\lk_{\Delta_4}(4) = \Delta_3$ with $\Delta_3'$, which results in adding the facet $134$ to obtain $\Delta_4'$. In $\Delta_5$ we replace $\del_{\Delta_5}(5) = \Delta_4$ with $\Delta_4'$ which results in adding the facet $134$ to obtain $\Delta_5'$. Next in $\Delta_6$ we replace $\lk_{\Delta_6}(6) = \Delta_5$ with $\Delta_5'$, adding facet $1346$ to obtain $\Delta_6'$.  Finally in $\Delta_7$ we replace $\del_{\Delta_7}(7) = \Delta_6$ with $\Delta_6'$, adding the facet $1346$. We note that $1346$ is indeed the smallest element missing from $\Delta = \Delta_7$ among the revlex ordered $4$-subsets of $\{1,\ldots,7\}$
\end{example}



We will use the above observations to show that many orderings of the ground set of a matroid give rise to decomposing orders.  



%For this we will need the following result.

%\begin{lem}\label{lem:matroid}
%Let $\M$ be a rank $d$ matroid on ground set $V$ and suppose that $\M$ is full on $V \backslash \{v\}$ for some nonloop $v \in V$. Suppose $F$ is a $d$-subset of $V$ with $v \in F$ such that $F$ is not a facet (basis) of $\M$. Then the complex generated by $M \cup \{F\}$ is again a matroid.
%\end{lem}

%\begin{proof}
%We first observe that for any $d$-subset $A$ of $V \backslash \{v\}$ there exists a $(d-1)$-subset $B \subset A$ with the property that $B \cup \{v\}$ is a facet of $\M$.  This follows from applying the exchange property with $A$ and any facet $F$ that contains $v$ (which must exist since $v$ is not a loop).

%Now let $F = \{x_1, x_2, \dots, x_{d-1},v\}$ be a $d$-subset that is missing from $\M$. Let $G$ be any facet of $\M$.  We will verify the exchange properties between $F$ and $G$. We first claim that for any $f \in F$ there exists some $g_i$ such that $(G \backslash \{g_i\}) \cup \{f\}$ is a facet of $\M$. If $f \neq v$ then this is clear since $\M$ is full on $V \backslash \{v\}$. If $f = v$ we use the above observation with $A = G$ to obtain $B = G \backslash \{g_i\}$.

%Next we claim that for any $g \in G$ with $g \neq v$ there exists some $x_i \in F$ such that $(F \backslash \{x_i\}) \cup \{g\}$ is a facet of $\M$. For this we again use the above observation with $A = \{g, x_1,...,x_{d-1}\}$. Note that the resulting $B$ must contain $g$ since otherwise $F$ would be a facet of $\M$. We take $x_i = A \backslash B$ and the result follows.
%\end{proof}

\begin{prop}
\label{prop:matroids}
Let $\M$ be a rank $d$ matroid and suppose $v_1, v_2, \dots, v_n$ is any linear ordering of its ground set $V$ with the property that $\{v_1, v_2, \dots,v_d\} \in \M$. Then $v_1, v_2, \dots, v_n$ is a decomposing order for $\M$.
\end{prop}


\begin{proof} (Sketch) 
Suppose that $v_1, v_2, \dots, v_n$ is such an ordering of $V$ and let $F$ be the revlex smallest $(d+1)$-subset of $V$ that is missing from $\Delta$. Let $q$ be the smallest $i \geq 2$ such that $v_i \in F$ and $v_{i-1} \notin F$. Since $\M$ is a matroid we have that any element $v$ is a loop or a decomposing vertex.  From the proof of Theorem \ref{thm:vdextend}, we get that $v_1, v_2, \dots,v_n$ is decomposing order for $\M$ if $v_1,v_2, \dots,v_q$ is a decomposing order for
\[\Gamma := \lk_{\Delta}(F \cap \{v_{q+1},\ldots,v_n\})|_{\{v_1,\ldots,v_q\}}.\]

We see that $\Gamma$ is a matroid with the property that $\del_{\Gamma}(v_q)$ is full, which follows from the fact that $F$ was the revlex smallest $d$-subset missing from $\Delta$.  One can check that any ordering of the ground set of $\Gamma$ is a decomposing ordering, and the result follows.
\end{proof}

As a consequence of Proposition \ref{prop:matroids} we get the following.

\begin{cor}\label{cor:matroidorder}
Let $\M$ be a rank $d$ matroid and suppose $v_1, v_2, \dots, v_n$ is any linear ordering of its ground set $V$ with the property that $\{v_1, v_2, \dots,v_d\} \in \M$, and let $F$ be the revlex smallest $d$-subset missing from $\M$.  Then the complex generated by $\M \cup \{F\}$ is vertex decomposable.
\end{cor}


\begin{rem}
Given a rank $d$ matroid $\M$ on ground set $V$, a related question to ask is whether there exists a $d$-subset $F \subset V$ such that $\M \cup \{F\}$ is again a \emph{matroid}.  Truemper \cite{Tru} has shown that if $\M$ is connected then this is the case if and only if $F$ is a \emph{circuit hyperplane} (that is, a circuit in $\M$ such that $V \backslash F$ is a circuit of the dual matroid $\M^*$).
%As for a nonexample we thank Jay Schweig for the following explicit construction: Consider the rank $3$ matroid $\M$ with ground set $\{x,a,b,c,d\}$ generated by the facets (bases) $\{xab, xac, xad, xbc, xbd, xcd\}$ (so that $M$ is the cone over the rank 2 uniform matroid on 4 elements). Note that if $F$ is any missing $3$-subset of $M$ then $x \notin F$. Hence we do not have the exchange property with for instance $xab$, since we cannot replace $x$ with anything to obtain a basis of $M \cup \{F\}$.
\end{rem}


%\begin{rem}
%A \emph{shedding order} for a vertex decomposable complex $\Delta$ is an ordering $v_1, v_2, \dots, v_n$ of its vertices with the property that $v_{i}$ is a decomposing vertex of $\Sigma_i$, where we define $\Sigma_n = \Sigma$ and $\Sigma_{i-1} = \del_{\Sigma_{i}}(v_i)$ (so that $\Sigma_{i-1}$ is necessarily vertex decomposable). In [\cite{ProBil} Proposition 3.2.3] it is shown that any ordering of the vertices of a matroid $\M$ is a shedding order for $\M$. We note that there exist shedding orders that are not decomposing orders, see \cite{CDGO}.


%We note that there exist shedding orders that are not decomposing orders. For instance consider the simplicial complex $\Gamma$ with facets
%\[\{1234,1235,1245,1345,2345,1346,1456,2456,3456\},\]
%which is the complex obtained from $\Delta_6$ of Example~\ref{ex:decompose} by reversing $\{1,2,3,4,5\}$.  Since $\del_\Sigma(6)$ is full, we have that $1,2,\dots,6$ is a shedding order. But in $\lk_\Sigma(6) = \{134,145,245,345\}$ we cannot use $5$ as a decomposing vertex, so that $1,2,\dots,6$ is not a decomposing order. On the other hand $5,4,3,2,1,6$ gives a decomposing order, as discussed above.
%\end{rem}

In light of Corollary \ref{cor:matroidorder} a natural question to ask is whether there exists an ordering of the ground set such that \emph{all} missing facets can be added in reverse lexicographic order.  The next example shows that an arbitrary ordering will not work.


\begin{example}
    Let $\M$ be the matroid on ground set $[6]$ generated by the facets \[\{1234, 1345,2346, 3456\}.\]  We note that adding the revlex smallest missing $4$-subset $1235$ results in a shelling move but the shelling fails when we continue to add the next revlex smallest subsets
\[1235, 1245, 1236, 1246, 1256.\]
To see this let $\Delta$ denote the complex obtained by adding these $4$-subsets and consider $F = 56$, a face of $\Delta$.  We note that $\lkc(F) = \{34, 12\}$, which is $1$-dimensional and disconnected and hence not shellable. By Lemma \ref{lem:linkshell} we conclude that $\Delta$ is not shellable.
 \end{example}



\section{Complexes with few vertices}\label{sec:few}


In \cite{CDGS} it is shown that a $d$-dimensional complex $\Delta$ on $d+3$ vertices is extendably shellable if and only if $\Delta$ is shellable. In this section we show that these conditions are also equivalent to $\Delta$ being vertex decomposable.  In what follows we will assume that our complexes have no loops, so that vertex set of $\Delta$ coincides with its ground set.


For our result we will exploit a connection between shellable complexes and the notion of a chordal graph.  Recall that a simple graph $G$ is \emph{chordal} if it has no induced cycles of length 4 or more (so that all cycles of length 4 or more have a `chord').   It is well known that any chordal graph admits a \emph{simplicial vertex}, a vertex $v \in V(G)$ such that its neighborhood (the subgraph induced on the set of vertices adjacent to $v$) is a complete graph.  From \cite{Doc} we have the following result, adapted for our purposes.

\begin{lem} \label{lem:exposed}
Let $K_n$ denote the complete graph on vertex set $[n] = \{1, 2, \dots, n\}$.  Suppose $\{e_1, e_2, \dots, e_k\} \subset E(K_n)$ is a collection of edges and for each $j = 1,2, \dots, k$ let $F_j = [n] \backslash e_j$ denote the complementary $(n-2)$-subset. Then $K_n \backslash \{e_1, e_2, \dots, e_k\}$ is a chordal graph if and only if the simplicial complex induced by $F_1, F_2, \dots F_k$ is shellable.
\end{lem}

%\begin{lem}\label{lem:graphVD}
%Any shellable 1-dimensional simplicial complex (graph) $G$ is vertex decomposable. 
%\end{lem}

%\begin{proof}
%Recall that a graph $G$ is shellable if and only if its finite and connected. Let $G$ be a connected graph on vertex $[n]$. If $n=1$ then $G$ is a simplex and hence vertex decomposable.  Suppose $n \geq 2$ and let $T$ be a spanning tree of $G$.  Choose $v \in G$ to be a leaf vertex of $T$.  Then $G \backslash v$ is connected and $\text{lk}_G(v)$ is nonempty. The result follows by induction on $n$.
%\end{proof}


%\begin{lem}\label{lem:smallVD}
%Suppose $\Delta$ is a shellable $d$-dimensional complex on at most $d+2$ vertices. Then $\Delta$ is vertex decomposable.
%\end{lem}

%\begin{proof}
%We see that the statement is true for $d=1$ by Lemma \ref{lem:graphVD}.  For $d \geq 2$ consider any facet $F$ in $\Delta$.  If $F$ contains all vertices of $\Delta$ then we're done since $\Delta$ is a simplex.  Otherwise choose $v \notin F$ and delete it, so that  $\delc(v)$ is a simplex and hence vertex decomposable.  Next note that $\lkc(v)$ is a $d-1$ dimensional complex on at most $d+1$ vertices, which is vertex decomposable by induction on $d$.
%\end{proof}

\begin{thm}\label{thm:shellableVD}
Suppose $\Delta$ is a shellable $d$-dimensional simplicial complex on $d+3$ vertices.  Then $\Delta$ is vertex decomposable.
\end{thm}

\begin{proof}
(Sketch) 
We prove the statement by induction on $d$. If $d=1$ the claim follows since a graph is connected if and only if it is vertex decomposable. Suppose $d \geq 1$ and let $\Delta$ be a $d$-dimensional complex with shelling order $F_1, F_2, \dots, F_j$.  Let $G$ be the graph consisting of edges $\{V \backslash F_i: F_i \in \Delta\}$. From Lemma \ref{lem:exposed} we have that $G$ is chordal and hence admits a simplicial vertex $v \in G$. We then have that $G \backslash \{v\}$ is chordal and hence $\delc(v)$ is a shellable $d$-dimensional complex on at most $d+2$ vertices.  It follows that $N(v)$ is vertex decomposable. We see that $\lkc(v)$ is a  shellable $(d-1)$-dimensional complex on at most $d+2$ vertices, which by induction is vertex decomposable.  The fact that $v$ is simplicial implies that $v$ is a shedding vertex, and the result follows.\end{proof}

Hence for a $d$-dimensional simplicial complex on at most $d+3$ vertices the concepts of shellable, extendably shellable, shelling completable, and vertex decomposable are all equivalent.  We note that there exist $2$-dimensional complexes on 6 vertices that are shellable but not vertex decomposable \cite{MorTak}.


\section{Completing $k$-decomposable complexes}\label{sec:further}

Recall that Simon's Conjecture posits that all shellable complexes are shelling completable, and here we have shown the conjecture holds for the particular class of vertex decomposable complexes.  We can ask the same question for complexes that properly sit in between these two classes. We first recall the relevant definition.

\begin{defn}
A pure $d$-dimensional simplicial complex $\Delta$ is said to be \emph{$k$-vertex decomposable} if $\Delta$ is a simplex, or $\Delta$ contains a face $F$ such that
\begin{enumerate}
    \item $\dim(F) \leq k$
    \item both $\delc(F)$ and $\lkc(F)$ are $k$-vertex decomposable, and
    \item $\delc(F)$ is pure (and the dimensions stays same as that of $\Delta$).
\end{enumerate}
%A face $F$ which satisfies the third condition is called a \emph{shedding face} of $\Delta$.
\end{defn}

The notion of $k$-vertex decomposable interpolates between the notion of vertex decomposable (which is equivalent to $0$-vertex decomposable in this language) and shellable (which can be seen to coincide with $d$-vertex decomposable).


\begin{example}[Example V6F10-6 from \cite{MorTak}]
Let $\Delta$ be the $2$-dimensional complex with facets
\[\{123,124,125,134,136,245,256,346,356,456\}.\]
In \cite{MorTak} it is shown that $\Delta$ is not vertex decomposable, but one can check that it is $1$-decomposable using $15$ as a shedding face.
\end{example}

Our results imply that a $0$-vertex decomposable complex is shelling completable, and Simon's conjecture posits that a $d$-vertex decomposable complex is shelling completable.  As far we know it is an open question whether a $1$-vertex decomposable complex is shelling completable.


\acknowledgements{ Much of this work was conducted under NSF-REU grant DMS-1757233 during the Summer 2020 Mathematics REU at Texas State University. The authors gratefully acknowledge the financial support of NSF and thank Texas State for providing a great (virtual) working environment. We thank Bruno Benedetti, Dylan Douthitt,  Jos\'e Samper, Jay Schweig, and Michelle Wachs for useful discussions and references, as well as two anonymous referees for useful comments.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
