# ProSAS: An O-RAN Approach
to Spectrum Sharing between NR and LTE

Sneihil Gopal‡†, David Griffith⋆, Richard A. Rouil⋆ and Chunmei Liu⋆
‡PREP Associate, National Institute of Standards and Technology (NIST), USA
†Department of Physics, Georgetown University, USA
⋆National Institute of Standards and Technology (NIST), USA
Emails: {sneihil.gopal, david.griffith, richard.rouil<EMAIL_ADDRESS>
## Abstract

The Open Radio Access Network (O-RAN), an industry-driven initiative, utilizes
intelligent Radio Access Network (RAN) controllers and open interfaces to
facilitate efficient spectrum sharing between LTE and NR RANs. In this paper,
we introduce the Proactive Spectrum Adaptation Scheme (ProSAS), a data-driven,
O-RAN-compatible spectrum sharing solution. ProSAS is an intelligent radio
resource demand prediction and management scheme for intent-driven spectrum
management that minimizes surplus or deficit experienced by both RANs. We
illustrate the effectiveness of this solution using real-world LTE resource
usage data and synthetically generated NR data. Lastly, we discuss a high-
level O-RAN-compatible architecture of the proposed solution.

##  I Introduction

The surge in multimedia applications and the rapid digitization of many
industries have led to increased mobile data usage in recent years [1]. To
address this growing need for data connectivity, the 3rd Generation
Partnership Project (3GPP) is deploying the fifth generation (5G) radio
interface known as New Radio (NR) [2]. NR is expected to meet the rising
demand for data traffic and enhance wireless connectivity for various emerging
applications such as automotive, healthcare, public safety, and smart cities.
It is engineered to deliver high data rates, low latency, and extensive
coverage and will operate within two frequency bands: Frequency Range 1 (FR1),
from 410 MHz to 7.125 GHz (also known as the sub-6 GHz band), and Frequency
Range 2 (FR2), from 24.25 GHz to 52.6 GHz (also called the mmWave band). As
most low-frequency bands are already allocated to 4G Long Term Evolution (LTE)
networks, network operators face the challenge of either acquiring new
spectrum or repurposing existing LTE spectrum for NR. Both options entail
substantial costs. Moreover, since LTE will continue to handle most data
traffic in the near term, reallocating low-frequency bands from LTE to NR
without a concurrent expansion of NR-capable devices will congest LTE bands
and degrade network performance. Hence, operators need to strategically
utilize their existing 4G infrastructure during the transition to NR while
providing services for legacy devices. This is necessary as LTE and NR
networks are expected to coexist for the foreseeable future.

To ensure a smooth transition from LTE to NR networks while supporting legacy
devices and maintaining network performance, 3GPP has proposed a comprehensive
set of solutions [3]. These include LTE-compatible NR numerology with a 15 kHz
subcarrier spacing for unified time/frequency resource grids. Also, solutions
include resource reservation, and downlink (DL) subcarrier puncturing to
support enhanced Machine-Type Communication (eMTC) (Technical Report (TR)
37.823), and mechanisms for resource allocation within NR carriers for
Narrowband-Internet of Things (NB-IoT) (TR 37.824). Lastly, to help mitigate
and manage interference for applications like V2X (TR 37.985), 3GPP has
introduced guard bands, dynamic and static power sharing mechanisms, and
requirement-based access technology prioritization.

While these solutions lay a strong foundation for LTE and NR network
coexistence, real-world scenarios, diverse network environments, regulations,
and evolving technological demands necessitate additional adaptations. The
Open Radio Access Network (O-RAN) initiative, with its open interfaces,
virtualization, and intelligence, supports innovation within networks.
Equipped with Artificial Intelligence/Machine Learning (AI/ML)-capable RAN
Intelligent Controller (RIC), O-RAN enables advanced spectrum sharing. Within
this framework, we propose Proactive Spectrum Adaptation Scheme (ProSAS), a
data-driven, O-RAN-compatible resource-sharing solution. ProSAS capitalizes on
O-RAN’s capabilities, focusing on intelligent demand prediction and resource
allocation to minimize resource surpluses or deficits experienced by networks.

We utilize statistical models and deep learning techniques to analyze and
predict radio resource demand patterns. This analysis uses real-world LTE
resource usage data collected using BladeRF Software Defined Radio (SDR)
111Certain commercial equipment, instruments, or materials are identified in
this paper in order to specify the experimental procedure adequately. Such
identification is not intended to imply recommendation or endorsement by
National Institute of Standards and Technology (NIST), nor is it intended to
imply that the materials or equipment identified are necessarily the best
available for the purpose. and Online Watcher of LTE (OWL), an open-source LTE
sniffer [4], as well as NR data generated synthetically using Time-Series
Generative Adversarial Network (TimeGAN) [5]. The proposed scheme is O-RAN-
compatible and can be implemented within the O-RAN architecture as follows:
the modeling and training processes corresponding to demand prediction can
occur within the non-real-time (non-RT) RIC, leveraging data gathered from
Radio Access Network (RAN). The optimal model can be selected and subsequently
deployed to the near-real-time (near-RT) RIC for inference. During the
inference phase, the near-RT RIC can allocate resource blocks to minimize any
surplus or deficit for both RAN s. To demonstrate ProSAS’s compatibility with
O-RAN requirements, we discuss a high-level architectural overview of the
modules and the deployment scenario alongwith a summary of the end-to-end
workflow involved. To the best of our knowledge, this paper is the first
attempt to propose an O-RAN-compatible scheme that manages radio resources
proactively and intelligently to balance the demands of LTE and NR networks.
Our use of real-world data and alignment with industry standards makes this
proposal practical and pertinent for network operators. Furthermore, we
provide a valuable set of LTE resource usage data for researchers, and we
demonstrate the utility of a GAN in generating synthetic radio resource usage
data [6].

The structure of the paper is as follows: Section II delves into related work.
Section III provides an overview of O-RAN, the ProSAS framework, and the high-
level architecture of the O-RAN-compatible deployment scenario. The
effectiveness of ProSAS is demonstrated in Section IV. Finally, Section V
concludes the paper.

##  II Related Work

In addition to 3GPP’s work, the research community has also studied LTE-NR
coexistence [7, 8, 9, 10, 11, 12, 13]. In [7], the authors addressed co-
channel interference, and proposed a low-complexity interference mitigation
method for NR devices. In [8], the authors presented experimental results for
LTE-NR coexistence in the 700 MHz band, demonstrating peaceful DL coexistence.
In [9], the authors introduced a spectrum exploitation mechanism balancing
transmission efficiency, coverage, and latency. In [10], the authors discussed
LTE-NR uplink (UL) coexistence, revealing that LTE needs a single resource
block as a guard band, while NR remains unaffected by LTE. In [11], the
authors explored LTE Frequency Domain Duplex (FDD) and NR FDD coexistence in
the 2.1 GHz band and showed that LTE FDD DL causes harmful interference to NR
FDD DL. Conversely, [12] analyzed NR FDD and LTE Time Domain Duplex (TDD)
coexistence in the 1.8 GHz band, showing their compatibility in adjacent
bands. [13] explored NR UL/DL coexistence with LTE UL/DL, highlighting the
role of UL sharing in balancing spectrum efficiency, latency, coverage, and
channel bandwidth. Additionally, LTE-NR coexistence has been examined for
specific applications like eMTC [14], NB-IoT [15], and V2X [16].

While the existing work on LTE-NR coexistence has made significant strides,
several aspects can be improved with the integration of O-RAN principles. One
missing element is adaptability and intelligent management of resources to
proactively balance the demands of LTE and NR networks, which is our focus. We
will show how this element can support spectrum sharing, which has recently
gained the attention of the O-RAN Alliance Working Group 1 (WG1) [17] and has
been explored in several studies [18, 19, 20, 21]. In [18], the authors
propose spectrum sharing between government Low Earth Orbit satellites and 5G
UL using O-RAN intelligence and open interfaces. In [19], a Reinforcement
Learning (RL)-based radio resource management solution is developed,
leveraging the O-RAN platform. [20] introduced O-RAN-compliant frameworks for
enabling spectrum sharing. Specifically, [20] demonstrated the framework’s
performance in LTE-WiFi coexistence in unlicensed bands, using srsRAN for
prototype development and the Colosseum channel emulator for data collection.
[21] explored contextual user density data for spectrum management in O-RAN-
based networks, offering numerical validation of the proposed concept. While
these works make valuable contributions, ProSAS features a data-driven,
intelligent, and intent-driven approach to spectrum sharing and resource
management. Its use of real-world data and compatibility with O-RAN makes it a
potential tool for supporting LTE-NR coexistence.

##  III The ProSAS Framework

O-RAN represents a transformative approach to modernizing the traditional RAN.
Unlike traditional RAN s, which often rely on proprietary, monolithic hardware
and software solutions, O-RAN promotes open interfaces and virtualization
technologies and introduces near-RT RIC s and non-RT RIC s to coordinate and
manage network resources. These RIC s play pivotal roles in the O-RAN
architecture by optimizing radio resource allocation, enhancing network
performance, and ensuring quality of service (QoS). Furthermore, O-RAN
promotes innovation by facilitating the development of RAN applications
(rApps) and external applications (xApps) that can seamlessly interface with
the RIC s and the RAN infrastructure, providing advanced functionalities,
intelligence, and adaptability. We have designed ProSAS such that it can use
rApps, xApps, and open interfaces, and therefore harness the capabilities of
the O-RAN architecture.

In this paper, we propose an intelligent radio resource demand prediction and
management scheme for intent-driven (priority-based) spectrum management. We
employ a high-level model for LTE and NR that makes few assumptions about the
underlying technology. We assume that NR employs an LTE-compatible numerology
with 15 kHz subcarrier spacing, resulting in identical time/frequency resource
grids for both networks and we assume that both networks use a shared pool of
time-frequency resources, referred to as Physical Resource Blocks (PRBs). Note
that we define resource demand as the number of PRBs required by a network for
data transmission. Our approach learns the resource usage patterns of each
network by analyzing their individual resource usage time-series datasets,
using a variety of statistical models and deep learning architectures to
predict future demand. We choose the method with the lowest root-mean-square
error (RMSE) as the most suitable predictor. Based on the predicted demand
from the selected prediction model, we allocate resources to minimize any
surplus or deficit experienced by both networks, where a surplus indicates
resource over-provisioning and a deficit represents under-provisioning,
leading to packet loss or buffering. Next, we discuss the proposed framework
and its high-level integration into the O-RAN architecture.

####  III-1 Radio Resource Demand Prediction

Understanding radio resource usage patterns is crucial for effective resource
management because network operators can then mitigate the costs of unexpected
spikes in data traffic. We use a toolkit of time-series predictive models that
incorporates statistical methods and deep learning architectures. It includes
the Autoregressive Integrated Moving Average (ARIMA) [22] model, which
combines autoregressive (AR) and moving average (MA) components with
differencing to handle linear dependencies in the time series data. We also
use the toolkit’s Exponential Smoothing (ETS) model [22] to capture data
patterns, including trends and seasonality.

In addition to statistical models, our toolkit includes three deep learning
models tailored for time series forecasting. The Multilayer Perceptron (MLP)
Model [23] is a neural network with interconnected layers of neurons, well-
suited for uncovering intricate data patterns in sequential data. The
Convolutional Neural Network (CNN) Model [23], originally designed for image
data, can also be applied to time series data, using convolutional layers to
learn relevant features, and is useful for tasks emphasizing local patterns.
Lastly, the Long Short-Term Memory (LSTM) Model [23], a category of Recurrent
Neural Network (RNN), engineered to capture long-term dependencies in
sequential data. Its ability to retain information over extended time
intervals makes it effective for time series forecasting tasks. Our toolkit
also encompasses variations of the LSTM model [23], namely, CNN-LSTM
(combining the convolutional layers of CNN with the sequential modeling
capability of LSTM), and Convolutional LSTM (ConvLSTM) (integrating
convolutional operations within LSTM units).

To establish a performance baseline for these models, we incorporate simpler
models, including the Persistence or Naive model, Moving Average (MA) model,
and Moving Median (MM) model. The Persistence model sets the forecast for the
next time step as the previous time step, providing a benchmark for more
complex models. The MA model calculates the forecast as the average of the
previous $n$ observations, which captures short-term trends or fluctuations.
Similarly, the MM model calculates the forecast as the median of the previous
$n$ observations, offering robustness against outliers and generating a
smoother forecast. This set of models equips us to tackle diverse aspects of
radio resource usage pattern analysis, capturing simple trends and complex
dependencies in time series data.

While several metrics, such as computational time and Mean Absolute Error
(MAE), are used to assess prediction model performance, we rely on the widely
adopted RMSE metric [23]. RMSE quantifies the standard deviation of prediction
errors and is defined as:
$\text{\lx@glossaries@gls@link{acronym}{rmse}{\leavevmode
RMSE}}=\bigl{[}(1/n)\sum\nolimits_{i=1}^{n}(|(f_{i}-\hat{f_{i}}|)^{2}\bigr{]}^{1/2}$,
where $n$ is the number of time steps in a data set and $f_{i}$ and
$\hat{f_{i}}$ are respectively the observed and predicted resource usage at
the $i$th time step.

####  III-2 Optimal Resource Allocation

We now describe how resources from a shared pool of PRBs are distributed
between coexisting LTE and NR networks. We assume that the controller
allocates PRBs to meet each network’s resource demands at regular intervals.
These intervals can represent time slots in an LTE system, $1$ ms subframes,
periods of several seconds, minutes, or hours, depending on the scenario.

Let $N_{R}$ represent the size of the PRBs resource pool used by the
controller to distribute resources ($N_{A}$ for LTE and $N_{B}$ for NR). The
primary goal is to minimize resource surplus or deficit for both networks. Our
scheme determines the optimal allocation by evaluating a performance metric
that addresses the networks’ varying demands. Although the scheme can support
static allocation (performed once during network setup) or dynamic allocation
(repeated at granularities as small as 1 ms), we focus on quasi-static
resource allocation. Since resource allocation follows demand prediction, we
assume that the controller has knowledge of the networks’ future resource
demands for a defined period (e.g., the next hour or minute) and allocates
resources accordingly.

Next, we define the optimization problem (OPT) as follows:

OPT:
$\displaystyle\min_{N_{A},N_{B}}J(N_{A},N_{B}|\gamma,x_{D_{A}},x_{D_{B}}),$
s.t. $\displaystyle\quad N_{A}+N_{B}\leq N_{R},$ $\displaystyle\quad 0\leq
N_{A}\leq N_{R},$ $\displaystyle\quad 0\leq N_{B}\leq N_{R},$ (1)

where,

$J=\gamma\left(\frac{N_{A}-x_{D_{A}}}{x_{D_{A}}}\right)^{2}+(1-\gamma)\left(\frac{N_{B}-x_{D_{B}}}{x_{D_{B}}}\right)^{2},$
(2)

is the weighted sum of squared fractional surpluses/deficits, i.e.,
$(N_{A}-x_{A})/x_{A}$ and $(N_{B}-x_{B})/x_{B}$, experienced by LTE and NR,
respectively. $(N_{A},N_{B})$ is the ordered pair of allocation and
$(x_{D_{A}},x_{D_{B}})$ is the ordered pair containing statistics associated
with the distributions of LTE’s and NR’s respective demands, i.e.,
($D_{A,i},D_{B,i}$), for $i\in[1,n]$, where $i$ is the time in a length-$n$
period. $\gamma\in(0,1)$ is the weighting factor that enables intent-driven
spectrum management by allowing the controller to prioritize one network over
the other. Specifically, $\gamma\rightarrow 1$ assigns a higher priority to
LTE, whereas, $\gamma\rightarrow 0$ assigns a higher priority to NR.

We consider two variations of OPT: (a) $\text{OPT}_{\text{max}}$ which uses
the maximum network demand ($M_{D_{A}},M_{D_{B}}$), as the network statistics
($x_{D_{A}},x_{D_{B}}$) in Eq. (2), further substituted in Eq. (1), and (b)
$\text{OPT}_{\text{avg}}$ which uses the mean of the objective function, i.e.,
$E[J]$, and therefore considers the mean and variance of each network’s
demand.

For $\text{OPT}_{\text{avg}}$, the objective function is:

$\displaystyle J_{avg}$
$\displaystyle=E\left[\gamma\left(\frac{N_{A}-D_{A}}{D_{A}}\right)^{2}+(1-\gamma)\left(\frac{N_{B}-D_{B}}{D_{B}}\right)^{2}\right],$
$\displaystyle=1+\gamma N_{A}\,C_{A}+(1-\gamma)N_{B}\,C_{B},$ (3)

where, by linearity of the expectation $E[\cdot]$, for $X\in\\{A,B\\}$,

$C_{X}=N_{X}\left(\frac{1}{\mu_{D_{X}}^{2}}+\frac{3\sigma_{D_{X}}^{2}}{\mu_{D_{X}}^{4}}\right)-2\left(\frac{1}{\mu_{D_{X}}}+\frac{\sigma_{D_{X}}^{2}}{\mu_{D_{X}}^{3}}\right),$
(4)

$\mu_{D_{A}}$ and $\mu_{D_{B}}$ are the mean, and $\sigma_{D_{A}}^{2}$ and
$\sigma_{D_{B}}^{2}$ are the variance of LTE and NR’s demand, respectively. As
with $\text{OPT}_{\text{max}}$, $\text{OPT}_{\text{avg}}$ can be obtained by
substituting Eq. (3) in Eq. (1). $\text{OPT}_{\text{max}}$ and
$\text{OPT}_{\text{avg}}$ are both convex-optimization problems and each has a
global minimum.

For the optimal resource pool partition $(N_{A}^{*},N_{B}^{*})$, we compute
the average normalized surplus or deficit, denoted by $S_{A}$ and $S_{B}$ for
LTE and NR, respectively:

$\small
S_{A}=\frac{1}{n}\sum\limits_{i=1}^{n}\left(\frac{N_{A}^{*}-D_{A,i}}{D_{A,i}}\right),\enspace
S_{B}=\frac{1}{n}\sum\limits_{i=1}^{n}\left(\frac{N_{B}^{*}-D_{B,i}}{D_{B,i}}\right)\,.\normalsize$
(5)

Lastly, we compute the fairness of the allocations for
$\text{OPT}_{\text{max}}$ and $\text{OPT}_{\text{avg}}$ using Jain’s Fairness
Index defined as:

$\small
F=\frac{(N_{A}^{*}+N_{B}^{*})^{2}}{2\bigl{(}(N_{A}^{*})^{2}+(N_{B}^{*})^{2}\bigr{)}}.\normalsize$
(6)

####  III-3 Deployment Architecture

Figure 1: High-level structure illustrating the deployment of ProSAS within
the O-RAN architecture [17].

Next, we describe how ProSAS could be implemented in the O-RAN architecture,
with the structure and end-to-end flow illustrated in Fig. 1. The design and
deployment scenarios are based on the guidelines outlined in the TR [24] by
the O-RAN Alliance.

  1. 1

Data collected from the RAN components (O-CU and O-DU), including the Downlink
Control Information (DCI), is transmitted to the data collector in the Service
and Management Orchestration (SMO) entity through the O1 interface. This data
is input for the Demand Prediction rApp within the non-RT RIC.

  2. 2

Using a data-sharing entity such as DMaaP or Kafka, the gathered data is
routed to the non-RT RIC in the SMO.

  3. 3

The relevant AI/ML models, including statistical models and deep learning
architectures, in the AI server (e.g., AcumosAI) in the SMO, are queried by
the non-RT RIC. Once these models have been trained on the AI server, the non-
RT RIC is notified of the inference.

  4. 4

The results of the inference and associated policies are forwarded to the
Resource Allocation xApp in the near-RT RIC via the A1 interface.

  5. 5

The Resource Allocation xApp configures the resource allocation solution,
which is derived by solving $\text{OPT}_{\text{max}}$ and
$\text{OPT}_{\text{avg}}$, and selected based on Jain’s fairness index. This
solution is conveyed to the RAN components using the E2 interface.

##  IV Numerical Results for ProSAS

Figure 2: Average PRB usage vs. time for LTE, NR and LTE +NR, i.e., aggregate,
corresponding to time granularity of 1-hour and 1-minute.

For our study, we compiled an extensive dataset of LTE scheduling information,
collected at the NIST Gaithersburg campus between January and February 2023
[6]. This dataset is from downlink traffic at 2115 MHz (Band 4) and was
collected using OWL [4], an online decoder of the LTE control channel. We
employed a BladeRF SDR board to transmit the collected real-world LTE signals
to a laptop running Ubuntu 20.04 and executing OWL to decode the signals. OWL
captured the LTE DCI broadcast by the base station at the 1 ms subframe level.
The dataset includes information such as the system frame number (SFN),
subframe index, radio network temporary identifiers (RNTIs), the number of
PRBs allocated to devices, modulation and coding scheme (MCS), and DCI message
type. We extracted the number of PRBs corresponding to data transmissions,
specifically DCI format 2B. We also included timestamps reflecting when this
data was collected, resulting in a time series dataset detailing PRB
allocations for the LTE network. Importantly, this data contains no user-
specific information, ensuring complete anonymity.

Due to the lack of availability of tools that can capture NR resource usage
data, using the compiled real-world LTE dataset, we generated a synthetic PRB
allocation dataset corresponding to the NR network. To create this synthetic
NR dataset, we leveraged TimeGAN [5], a tool that generates synthetic time-
series data by capturing temporal dependencies through RNN. We used TimeGAN
and the collected real-world LTE time-series data to produce synthetic time-
series NR data that closely mirrors the statistical properties and patterns
observed in the LTE data. This approach is valid due to our assumption that NR
employs an LTE-compatible numerology with 15 KHz subcarrier spacing, and
shares an identical time-frequency resource grid. We also assumed that NR
systems would serve LTE devices.

For our analysis, we performed a resampling of the time-series data,
transitioning from PRB allocation per millisecond to PRB allocation per hour
and per minute by using the mean function. Consequently, we obtained datasets
representing the average PRB allocation for both LTE and NR per hour and
minute. The former dataset comprises approximately 860 samples, while the
latter encompasses approximately 49 554 samples. We defer the analysis for
time granularities less than 1 minute for future research. Fig. 2 displays the
average PRB usage/demand over time for LTE, NR, and the combined (LTE +NR)
datasets, both at 1-hour and 1-minute granularities.

(a) Granularity = 1 hour

(b) Granularity = 1 minute

Figure 3: CDF of average PRB demand for LTE and synthetically generated NR
dataset for time granularity 1-hour and 1-minute.

Additionally, Fig. 3 shows the cumulative distribution function (CDF) of PRB
demands from both networks at different granularities. This graph highlights
the similarity in demand distribution between the compiled LTE dataset and the
synthetically generated NR dataset, thereby confirming the effectiveness of
TimeGAN. Next, we delve into the outcomes of the various resource demand
prediction models, in addition to those pertaining to the resource allocation
schemes.

Model |  Training Hyperparameters |  LTE (1-hour) |  NR (1-hour) |  LTE (1-minute) |  NR (1-minute)
---|---|---|---|---|---
Naive |  (length of historical data, offset) |  (1, 1) |  (1, 1) |  (1, 1) |  (1, 1)
MA |  (length of historical data, offset) |  (2, 1) |  (2, 1) |  (2, 1) |  (2, 1)
MM |  (length of historical data, offset) |  (2, 1) |  (2, 1) |  (2, 1) |  (2, 1)
ARIMA |  ((no. of lag observations (p), degree of differencing (d), order of MA (q)), trend) |  ((1, 3, 2), ‘c’) |  ((3, 0, 3), ‘c’) |  ((0, 1, 3), ‘c’) |  ((2, 1, 0), ‘c’)
ETS |  (trend, damped trend, seasonal) |  (‘mul’, False, None) |  (’add’, True, None) |  (None, False, None) |  (’add’, True, None)
MLP |  (inputs, nodes, epochs, batch size) |  (1, 150, 100, 150) |  (1, 150, 500, 100) |  (10, 100, 100, 150) |  (1, 150, 500, 100)
CNN |  (inputs, filters, kernels, epochs, batch size) |  (2, 256, 1, 100, 150) |  (2, 256, 1, 500, 150) |  (2, 256, 1, 500, 150) |  (2, 256, 1, 500, 150)
LSTM |  (inputs, nodes, epochs, batch size) |  (1, 150, 100, 100) |  (1, 150, 500, 150) |  (1, 100, 500, 100) |  (1, 150, 500, 150)
LSTM-I |  (sequences, steps, filters, kernels, nodes, epochs, batch size) |  (1, 2, 256, 1, 100, 100, 150) |  (1, 2, 256, 1, 100, 100, 150) |  (1, 2, 256, 1, 100, 500, 150) |  (1, 2, 256, 1, 100, 100, 150)
LSTM-II |  (sequences, steps, filters, kernels, nodes, epochs, batch size) |  (2, 1, 256, 1, 100, 500, 150) |  (2, 1, 256, 1, 100, 500, 150) |  (2, 1, 256, 1, 150, 500, 100) |  (2, 1, 256, 1, 100, 500, 150)

TABLE I: List of training hyperparameters chosen for each prediction model
using the grid search framework [23].

As mentioned earlier, our comprehensive demand prediction toolkit comprises
various models, combining both statistical approaches and deep learning
architectures. We perform a comparative analysis, evaluating the performance
of these models against alternatives like the Persistence or Naive model, MA
model, and MM model. The implementation of these prediction models is carried
out in Python, with Keras serving as the backend for deep learning
architectures. For each model, we have designed a framework for grid-searching
model hyperparameters, employing RMSE as our guiding metric through one-step
walk-forward validation. The selected hyperparameters for each model are
listed in Table I for transparency and reproducibility. For training and
validating the model architecture, we use 66 % for training at each
granularity, i.e., 1-hour and 1-minute [22]. Lastly, for the deep learning
architectures, we use the Adam optimization algorithm [22] and employ
Rectified Linear Unit (ReLU) as the activation function. In Fig. 4, we compare
the prediction models based on RMSE for both networks and granularities.
Notably, ARIMA outperforms other models for LTE data, whereas the ConvLSTM
model has the lowest RMSE for NR data. This highlights the need for tailored
models rather than a one-size-fits-all approach. Also, our results indicate
that while complex deep-learning architectures can be effective, simpler
statistical models can also yield strong performance.

Figure 4: Evaluation of prediction models in terms of RMSE. LSTM-I and LSTM-II
refer to CNN-LSTM and ConvLSTM, respectively.

(a) Optimal Allocation

(b) Surplus/Deficit

(c) Jain’s Fairness Index

Figure 5: Results for $\text{OPT}_{\text{max}}$ versus
$\text{OPT}_{\text{avg}}$ for resource pool size $N_{r}=10$ resources.

Next, we assess the effectiveness of our resource allocation scheme. We
conducted a comprehensive analysis encompassing three distinct resource pool
sizes, $N_{r}\in\\{10,40,50\\}$ corresponding to limited, moderate, and
adequate resource availability. We varied the parameter $\gamma$ within each
pool size configuration between $0$ and $1$. For each value of $\gamma$, we
leveraged statistical insights derived from the predicted demand profiles of
LTE and NR to determine the optimal partition sizes, $N_{A}^{*}$ and
$N_{B}^{*}$, under two distinct allocation strategies:
$\text{OPT}_{\text{avg}}$ (utilizing demand statistics like means and
variances) and $\text{OPT}_{\text{max}}$ (relying on demand maxima). Our
evaluation aimed to capture the average surplus or deficit (see Eq. (5)) under
each scenario, as well as Jain’s fairness index (see Eq. (6)), for different
$\gamma$ values and across various resource pool sizes ($N_{r}$). In the
interest of brevity, we present results corresponding to the predicted data
for LTE and NR obtained through ARIMA and ConvLSTM, respectively, at a
granularity of 1 hour when $N_{r}=10$ resources, as depicted in Fig. 5. It is
important to note that our insights hold consistently across different
granularities. Key statistics characterizing the demand profiles of LTE and NR
include the following metrics: the mean demand, $\mu_{D_{A}}=21.52$ and
$\mu_{D_{B}}=22.80$; the variances, $\sigma_{D_{A}}^{2}=12.37$ and
$\sigma_{D_{B}}^{2}=8.33$; and the maxima, $M_{D_{A}}=26.31$ and
$M_{D_{B}}=25.80$. Consequently, the expected total demand approximates 45
resources per hour, while the maximum total demand approaches 53 resources per
hour.

In scenarios with $N_{r}=10$ resources, where resources are scarce and lag
behind demand, both networks face starvation. Total starvation, which occurs
when the networks receive no resources, corresponds to a fractional deficit of
$-1$. Our findings (Fig. 5(b)) indicate that $\text{OPT}_{\text{avg}}$
mitigates starvation over a wider range of $\gamma$ values compared to
$\text{OPT}_{\text{max}}$. Furthermore, $\text{OPT}_{\text{avg}}$ achieves
fairer allocation across a broader spectrum of $\gamma$ values (Fig. 5(c)).
For $N_{r}=40$ resources, with a moderate pool size that can accommodate mean
and maximum demands but falls short of the aggregate demand,
$\text{OPT}_{\text{avg}}$ achieves a perfectly fair allocation ($F=1$) within
a specific range of $\gamma$ values ($\gamma\in[0.76,0.87]$), surpassing the
fairness achieved by $\text{OPT}_{\text{max}}$ ($\gamma\in[0.47,0.49]$).
However, $\text{OPT}_{\text{avg}}$ may result in deficits across all $\gamma$
values, while $\text{OPT}_{\text{max}}$ may result in surpluses, especially
when one network has significantly higher priority (near $\gamma$ values of 0
or 1), making $\text{OPT}_{\text{max}}$ advantageous in such cases. Finally,
for $N_{r}=50$ resources, where the pool comfortably accommodates both mean
and maximum demands, $\text{OPT}_{\text{max}}$ outperforms
$\text{OPT}_{\text{avg}}$ for both networks, leading to surpluses. As the
resource pool size approaches the maximum total demand,
$\text{OPT}_{\text{avg}}$ tends to allocate resources equal to the mean
demand, resulting in deficits, whereas $\text{OPT}_{\text{max}}$ results in
over-provisioning.

In essence, our results underline the significance of $\gamma$ in resource
allocation decisions and demonstrate that the choice between
$\text{OPT}_{\text{avg}}$ and $\text{OPT}_{\text{max}}$ depends on the
resource pool size relative to network demands. $\text{OPT}_{\text{avg}}$
excels in fairness but may cause deficits in limited resource scenarios.
Conversely, $\text{OPT}_{\text{max}}$ is preferable when resources are more
abundant as it yields surpluses. These findings provide valuable insights to
the controller, enabling it to fine-tune resource allocation strategies to
suit diverse network conditions, thereby enhancing overall performance and
user satisfaction.

##  V Conclusions

In this work, we introduced ProSAS, an O-RAN-compatible solution for
intelligent spectrum sharing between LTE and NR networks. ProSAS focuses on
proactive, intent-driven spectrum management while minimizing resource surplus
or deficit experienced by both networks. We demonstrated its effectiveness
using real-world LTE resource usage data and synthetically generated NR data.
Using these datasets, we developed an optimization scheme and outlined a
deployment scenario aligning with O-RAN requirements. Our emphasis on real-
world data and alignment with industry standards makes ProSAS both practical
and pertinent for network operators.

## References

  * [1] “Ericsson mobility report,” June, 2023. [Online]. Available: https://www.ericsson.com/en/reports-and-papers/mobility-report/reports
  * [2] S. Parkvall, E. Dahlman, A. Furuskar, and M. Frenne, “NR: The New 5G Radio Access Technology,” _IEEE Communications Standards Magazine_ , vol. 1, no. 4, pp. 24–30, 2017.
  * [3] S. Gopal, D. Griffith, R. A. Rouil, and C. Liu, “5G NR-LTE coexistence: opportunities, challenges, and solutions,” _arXiv preprint arXiv:2210.03906_ , 2022.
  * [4] N. Bui and J. Widmer, “OWL: A reliable online watcher for LTE control channel measurements,” _Proceedings of the 5th Workshop on All Things Cellular: Operations, Applications and Challenges_ , pp. 25–30, 2016.
  * [5] J. Yoon, D. Jarrett, and M. Van der Schaar, “Time-series Generative Adversarial Networks,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [6] S. Gopal, D. Griffith, R. Rouil, and C. Liu, “ProSAS: An O-RAN Approach to Spectrum Sharing between NR and LTE,” https://doi.org/10.18434/mds2-3178, accessed: 2024-03-08.
  * [7] S. Xu, J. Xin, S. Xiong, and Z. Sun, “Performance Analysis of CRS Interference Mitigation Algorithm in LTE and NR Coexistence Scenario,” _2nd Information Communication Technologies Conference (ICTC)_ , pp. 184–188, 2021.
  * [8] L. Alexandre and S. A. Cerqueira, “Contribution for the Coexistence Analysis between 5G and 4G in the sub-1 GHz Band,” _SBMO/IEEE MTT-S International Microwave and Optoelectronics Conference (IMOC)_ , pp. 1–3, 2019\.
  * [9] L. Wan, Z. Guo, Y. Wu, W. Bi, J. Yuan, M. Elkashlan, and L. Hanzo, “4G/5G Spectrum Sharing: Efficient 5G Deployment to Serve enhanced Mobile Broadband and Internet of Things Applications,” _IEEE Vehicular Technology Magazine_ , vol. 13, no. 4, pp. 28–39, 2018.
  * [10] T. Levanen, K. Ranta-Aho, J. Kaikkonen, S. Nielsen, K. Pajukoski, M. Renfors, and M. Valkama, “5G New Radio and LTE Uplink Coexistence,” _IEEE Wireless Communications and Networking Conference (WCNC)_ , pp. 1–6, 2018.
  * [11] N. An, C. Wang, and W. Wang, “Interference Coexistence of 5G NR and LTE System Based on 2.1 GHz,” _12th International Conference on Communication Software and Networks (ICCSN)_ , pp. 90–94, 2020.
  * [12] D. Li, D. Zhou, and L. Zhong, “Coexistence Analysis Between 5G NR and LTE Network at 1.8 GHz,” _International Conference of Modern Trends in Information and Communication Technology Industry (MTICTI)_ , pp. 1–6, 2021.
  * [13] L. Wan, Z. Guo, and X. Chen, “Enabling Efficient 5G NR and 4G LTE Coexistence,” _IEEE Wireless Communications_ , vol. 26, no. 1, pp. 6–8, 2019.
  * [14] R. Ratasuk, D. Zhou, and R. Sinha, “LTE-M Coexistence Within 5G New Radio Carrier,” _IEEE 3rd 5G World Forum (5GWF)_ , pp. 224–228, 2020.
  * [15] M. Mozaffari, Y.-P. E. Wang, O. Liberg, and J. Bergman, “Flexible and Efficient Deployment of NB-IoT and LTE-MTC in Coexistence with 5G New Radio,” _IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , pp. 391–396, 2019.
  * [16] M. H. C. Garcia, A. Molina-Galan, M. Boban, J. Gozalvez, B. Coll-Perales, T. Şahin, and A. Kousaridas, “A Tutorial on 5G NR V2X Communications,” _IEEE Communications Surveys & Tutorials_, pp. 1–1, 2021.
  * [17] O-RAN Alliance, “O-RAN Working Group 1 Use Cases Analysis Report,” _O-RAN.WG1.Use-Cases-Analysis-Report-R003_ , vol. 10.00, 2023.
  * [18] R. Smith, C. Freeberg, T. Machacek, and V. Ramaswamy, “An O-RAN Approach to Spectrum Sharing Between Commercial 5G and Government Satellite Systems,” _MILCOM 2021-2021 IEEE Military Communications Conference (MILCOM)_ , pp. 739–744, 2021.
  * [19] F. Mungari, “An RL Approach for Radio Resource Management in the O-RAN Architecture,” _18th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)_ , pp. 1–2, 2021.
  * [20] L. Baldesi, F. Restuccia, and T. Melodia, “ChARM: NextG Spectrum Sharing Through Data-Driven Real-Time O-RAN Dynamic Control,” _IEEE INFOCOM 2022-IEEE Conference on Computer Communications_ , pp. 240–249, 2022.
  * [21] Ł. Kułacz and A. Kliks, “Dynamic Spectrum Allocation Using Multi-Source Context Information in OpenRAN Networks,” _Sensors_ , vol. 22, no. 9, p. 3515, 2022.
  * [22] A. Nielsen, _Practical Time Series Analysis: Prediction with Statistics and Machine Learning_. O’Reilly Media, 2019.
  * [23] J. Brownlee, _Deep Learning for Time Series Forecasting: Predict the Future with MLPs, CNNs and LSTMs in Python_. Machine Learning Mastery, 2018.
  * [24] O-RAN Alliance, “O-RAN Working Group 2 AI/ML Workflow Description and Requirements,” _O-RAN.WG2.AIML_ , vol. 1, 2021.

###  -A Proof of Convexity for $\text{OPT}_{\text{max}}$

In this section, we show that $\text{OPT}_{\text{max}}$ is a convex-
optimization problem and hence has a global minimum. Mathematically,
$\text{OPT}_{\text{max}}$ is defined as:

$\displaystyle\footnotesize\text{OPT}_{\text{max}}:$
$\displaystyle\min_{N_{A},N_{B}}J_{max}(N_{A},N_{B}|\gamma,M_{D_{A}},M_{D_{B}}),$
s.t. $\displaystyle\quad N_{A}+N_{B}\leq N_{R},$ $\displaystyle\quad 0\leq
N_{A}\leq N_{R},$ $\displaystyle\quad 0\leq N_{B}\leq N_{R},$ (7)

where, $M_{D_{A}}$ and $M_{D_{B}}$ denote the maximum demand observed by the
controller for each network and the objective function $J_{max}$ is defined
as:

$\displaystyle\small
J_{max}=\gamma\left(\frac{N_{A}-M_{D_{A}}}{M_{D_{A}}}\right)^{2}+(1-\gamma)\left(\frac{N_{B}-M_{D_{B}}}{M_{D_{B}}}\right)^{2}.$

To show that (7) is a convex-optimization problem, we first compute the
Hessian of its objective function and show that it is positive semidefinite.
The Hessian of the objective function $J_{max}$ is:

$\displaystyle H=\begin{bmatrix}\dfrac{\partial^{2}J_{max}}{\partial
N_{A}^{2}}&\dfrac{\partial^{2}J_{max}}{\partial N_{A}\partial
N_{B}}\cr\dfrac{\partial^{2}J_{max}}{\partial N_{B}\partial
N_{A}}&\dfrac{\partial^{2}J_{max}}{\partial
N_{B}^{2}}\end{bmatrix}=\begin{bmatrix}\dfrac{2\gamma}{{M_{D_{A}}}^{2}}&0\cr
0&\dfrac{2(1-\gamma)}{{M_{D_{B}}}^{2}}\end{bmatrix}.$

For a Hessian of the bivariate function $F(x,y)$ to be positive semidefinite,
as per Sylvester’s criterion, the following two conditions must be satisfied:

  1. (a)

$\dfrac{\partial^{2}F}{\partial x^{2}}\geq 0$, and

  2. (b)

$\dfrac{\partial^{2}F}{\partial x^{2}}\dfrac{\partial^{2}F}{\partial
y^{2}}-\left(\dfrac{\partial^{2}F}{\partial x\partial y}\right)^{2}\geq 0$.

Since, both (a) and (b) are satisfied for the objective function $J_{max}$,
its Hessian is positive semidefinite, and hence it is convex. Also, the
inequality constraints are convex, which makes the optimization problem,
$\text{OPT}_{\text{max}}$, a convex optimization problem.

###  -B Proof of Convexity for $\text{OPT}_{\text{avg}}$

In this section, we show that $\text{OPT}_{\text{avg}}$ is a convex-
optimization problem and hence has a global minimum. Mathematically,
$\text{OPT}_{\text{avg}}$ is defined as:

$\displaystyle\footnotesize\text{OPT}_{\text{avg}}:$
$\displaystyle\min_{N_{A},N_{B}}J_{max}(N_{A},N_{B}|\gamma,\mu_{D_{A}},\sigma_{D_{A}}^{2},\mu_{D_{B}},\sigma_{D_{B}}^{2}),$
s.t. $\displaystyle\quad N_{A}+N_{B}\leq N_{R},$ $\displaystyle\quad 0\leq
N_{A}\leq N_{R},$ $\displaystyle\quad 0\leq N_{B}\leq N_{R},$ (8)

where, $\mu_{D_{A}}$ and $\mu_{D_{B}}$ correspond to the mean and
$\sigma_{D_{A}}^{2}$ and $\sigma_{D_{B}}^{2}$ correspond to the variance of
LTE and NR’s demand, respectively, and the objective function $J_{avg}$ is
defined as:

$\displaystyle J_{avg}=$ $\displaystyle
E\left[\gamma\left(\frac{N_{A}-D_{A}}{D_{A}}\right)^{2}+(1-\gamma)\left(\frac{N_{B}-D_{B}}{D_{B}}\right)^{2}\right].$

On solving the expectation we get:

$\displaystyle J_{avg}=$ $\displaystyle
E\left[\gamma\left(\frac{N_{A}^{2}}{D_{A}^{2}}+1-\frac{2N_{A}}{D_{A}}\right)+(1-\gamma)\left(\frac{N_{B}^{2}}{D_{B}^{2}}+1-\frac{2N_{B}}{D_{B}}\right)\right],$
$\displaystyle=$ $\displaystyle 1+\gamma
N_{A}\left(N_{A}E\left[\frac{1}{D_{A}^{2}}\right]-2E\left[\frac{1}{D_{A}}\right]\right)$
$\displaystyle+(1-\gamma)N_{B}\left(N_{B}E\left[\frac{1}{D_{B}^{2}}\right]-2E\left[\frac{1}{D_{B}}\right]\right).$

The second order Taylor series approximation of the expectation of $1/D_{A}$,
$1/D_{A}^{2}$, $1/D_{B}$ and $1/D_{B}^{2}$ are as follows:

$\displaystyle E\left[\frac{1}{D_{A}}\right]$ $\displaystyle=$
$\displaystyle\frac{1}{\mu_{D_{A}}}+\frac{\sigma_{D_{A}}^{2}}{\mu_{D_{A}}^{3}},\quad
E\left[\frac{1}{D_{A}^{2}}\right]=\frac{1}{\mu_{D_{A}}^{2}}+\frac{3\sigma_{D_{A}}^{2}}{\mu_{D_{A}}^{4}},$
$\displaystyle E\left[\frac{1}{D_{B}}\right]$ $\displaystyle=$
$\displaystyle\frac{1}{\mu_{D_{B}}}+\frac{\sigma_{D_{B}}^{2}}{\mu_{D_{B}}^{3}},\quad
E\left[\frac{1}{D_{B}^{2}}\right]=\frac{1}{\mu_{D_{B}}^{2}}+\frac{3\sigma_{D_{B}}^{2}}{\mu_{D_{B}}^{4}}.$

On substituting the above expectation values in the objective function, we
get:

$\displaystyle J_{avg}$ $\displaystyle=1+\gamma
N_{A}\left(N_{A}\left(\frac{1}{\mu_{D_{A}}^{2}}+\frac{3\sigma_{D_{A}}^{2}}{\mu_{D_{A}}^{4}}\right)-2\left(\frac{1}{\mu_{D_{A}}}+\frac{\sigma_{D_{A}}^{2}}{\mu_{D_{A}}^{3}}\right)\right)$
$\displaystyle+(1-\gamma)N_{B}\left(N_{B}\left(\frac{1}{\mu_{D_{B}}^{2}}+\frac{3\sigma_{D_{B}}^{2}}{\mu_{D_{B}}^{4}}\right)-2\left(\frac{1}{\mu_{D_{B}}}+\frac{\sigma_{D_{B}}^{2}}{\mu_{D_{B}}^{3}}\right)\right).$

To show that (8) is a convex optimization problem and hence has a global
minimum, we first compute the Hessian of the objective function and show that
it is positive semidefinite. The Hessian of the objective function, $J_{avg}$
is:

$\displaystyle H$
$\displaystyle=\begin{bmatrix}2\gamma\left(\dfrac{1}{\mu_{D_{A}}^{2}}+\dfrac{3\sigma_{D_{A}}^{2}}{\mu_{D_{A}}^{4}}\right)&0\cr
0&2(1-\gamma)\left(\dfrac{1}{\mu_{D_{B}}^{2}}+\dfrac{3\sigma_{D_{B}}^{2}}{\mu_{D_{B}}^{4}}\right)\end{bmatrix}.$

Since both conditions of Sylvester’s criterion are met for the objective
function $J_{avg}$, its Hessian is positive semidefinite. Therefore, it is a
convex function. Additionally, the inequality constraints are also convex,
making the optimization problem, $\text{OPT}_{\text{avg}}$, a convex
optimization problem.


# Simplicial complexes with many facets are vertex decomposable

Anton Dochtermann  Department of Mathematics, Texas State University, San
Marcos, TX 78666, USA<EMAIL_ADDRESS>https://dochtermann.wp.txstate.edu/ ,  Ritika Nair  Department of Mathematics,
University of Kansas, Lawrence, KS 66045-7523, USA<EMAIL_ADDRESS>,  Jay
Schweig  Department of Mathematics, Oklahoma State University, Stillwater, OK
74078, USA<EMAIL_ADDRESS>,  Adam Van Tuyl  Department of
Mathematics and Statistics
McMaster University, Hamilton, ON, L8S 4L8, Canada<EMAIL_ADDRESS>https://ms.mcmaster.ca/~vantuyl/ and  Russ Woodroofe  FAMNIT, University of
Primorska, 6000 Koper, Slovenia<EMAIL_ADDRESS>https://osebje.famnit.upr.si/~russ.woodroofe/

###### Abstract.

Let $\Delta$ be a pure simplicial complex on $n$ vertices having dimension $d$
and codimension $c=n-d-1$ in the simplex. Terai and Yoshida proved that if the
number of facets of $\Delta$ is at least $\binom{n}{c}-2c+1$, then $\Delta$ is
Cohen-Macaulay. We improve this result by showing that these hypotheses imply
the stronger condition that $\Delta$ is vertex decomposable. We give examples
to show that this bound is optimal, and that the conclusion cannot be
strengthened to the class of matroids or shifted complexes. We explore an
application to Simon’s Conjecture and discuss connections to other results
from the literature.

###### Key words and phrases:

simplicial complex, vertex decomposable

###### 2000 Mathematics Subject Classification:

05E40,05E45,13F55

##  1\. Introduction

Suppose $\Delta$ is a simplicial complex on vertex set $[n]=\\{1,\ldots,n\\}$.
Recall that $\Delta$ is pure if all the facets of $\Delta$ (the maximal
elements of $\Delta$ under inclusion) have the same cardinality. As first
shown by Terai and Yoshida [11, Theorem 3.1], if the number of facets of a
pure simplicial complex $\Delta$ is “large enough,” then $\Delta$ is Cohen-
Macaulay. In other words, the simplicial complex $\Delta$ enjoys additional
topological properties that can be detected by simply counting the number of
facets.

In this short note we strengthen Terai and Yoshida’s results. As in their
paper, we express our theorem in terms of the codimension of $\Delta$ relative
to the simplex on the same vertex set. Recall that the dimension of $\Delta$
is given by $\dim(\Delta)=\max\\{\dim(F)\leavevmode\nobreak\
|\leavevmode\nobreak\ F\in\Delta\\}$, where $\dim(F)=|F|-1$. If $\Delta$ has
$n$ vertices, then the _codimension_ of $\Delta$, denoted
$\operatorname{{codim}}{\Delta}$, is given by $c=n-\dim(\Delta)-1$ (the number
of vertices in the complement of a facet). Our main result can now be stated
as follows.

######  Theorem 1.1.

Let $\Delta$ be a pure simplicial complex on vertex set $[n]$ of codimension
$c$. If $\Delta$ has at least $\binom{n}{c}-2c+1$ facets, then $\Delta$ is
vertex decomposable.

Vertex decomposable simplicial complexes, which were introduced by Provan and
Billera in [9], are a recursively defined family of simplicial complexes (see
Section 2 for the formal definition). Terai and Yoshida [11, Theorem 3.1]
showed that, under the same hypotheses as Theorem 1.1, the simplicial complex
$\Delta$ is Cohen-Macaulay. Their result was stated in terms of the
multiplicity of the Stanley-Reisner ring, which agrees with the number of
facets of $\Delta$ when $\Delta$ is pure. Since being vertex decomposable
implies being Cohen-Macaulay, our main theorem strengthens their result. To
prove [11, Theorem 3.1], Terai and Yoshida used an algebraic approach,
employing the Stanley-Reisner correspondence between simplicial complexes and
square-free monomials. Our proof, in contrast, requires only simple tools from
topological combinatorics.

The bound in Theorem 1.1 is tight. In Example 4.1 we describe a family of
simplicial complexes on $n$ vertices of codimension $c$ and with
$\binom{n}{c}-2c$ facets, each of which fails to be vertex decomposable. In
Remark 4.3 we also show that Theorem 1.1 cannot be strengthened to conclude
that $\Delta$ is a matroid complex or shifted complex (both of which classes
are known to be vertex decomposable), even if we delete only two facets.

It is not hard to see that a simplicial complex $\Delta$ on vertex set $[n]$
with dimension $d$ and codimension $c$ can have more than $\binom{n}{c}-2c$
faces of dimension $d$, but fail to be pure. For instance, consider the
1-dimensional complex consisting of a triangle and an isolated vertex.
However, we observe in Lemma 4.4 that if we require at least $\binom{n}{c}-c$
facets of this top dimension, then purity is guaranteed. This leads to
Corollary 4.5 for arbitrary simplicial complexes, which strengthens [11,
Theorem 2.1].

We also interpret our results in terms of square-free monomial ideals (the
language used by Terai and Yoshida). In Corollary 4.6 we describe a sufficient
condition for a square-free monomial ideal to have a linear resolution, which
may be useful for researchers working in combinatorial commutative algebra.

Our main result also has connections to other work involving decompositions of
simplicial complexes. Simon’s Conjecture is a well-known open question
regarding the structure of shellable complexes (see Conjecture 4.9). Combining
our results with those from [3], we see that any counterexample to Simon’s
Conjecture cannot have “too many” facets. On the other hand, a result of Lasoń
from [7] provides a sufficient condition for a complex $\Delta$ to be vertex
decomposable in terms of extremal properties of the $f$-vector of $\Delta$. In
Example 4.11 we discuss how Theorem 1.1 relates to the results of Lasoń.

Our paper is organized as follows. In Section 2 we recall the necessary
definitions and background, in particular relevant properties of vertex
decomposable simplicial complexes. In Section 3 we prove Theorem 1.1. In
Section 4, we address the optimality of Theorem 1.1, interpret our result in
the language of square-free monomial ideals, and discuss the connection to
Simon’s Conjecture and Lasoń’s result.

##  2\. Background

In this section, we recall additional relevant background needed to prove our
main result. We refer to [6] or [12] for additional background on
combinatorial commutative algebra, and to [1] for topological combinatorics.
We continue to use the notation and definitions from the introduction.

Let $\Delta$ be a simplicial complex on vertex set $V$, which we typically
take as $V=[n]:=\\{1,2,\dots,n\\}$. An element $F\in\Delta$ is called a face,
and a face not properly contained in any other face is called a facet. For
each $i\in[n]$ we always assume that $\\{i\\}$ is a face of $\Delta$, which we
call a vertex and denote simply as $i$. If $F_{1},\ldots,F_{s}$ is a complete
list of the facets of $\Delta$, then we use the notation $\Delta=\langle
F_{1},\ldots,F_{s}\rangle$. After fixing a vertex $x\in[n]$, we can define two
other simplicial complexes from $\Delta$. Namely, the link of $\\{x\\}$ is the
simplicial complex

${\rm link}_{\Delta}(\\{x\\})=\\{G\in\Delta\leavevmode\nobreak\
|\leavevmode\nobreak\ x\notin G,\leavevmode\nobreak\ \leavevmode\nobreak\
G\cup\\{x\\}\in\Delta\\},$

and the deletion of $\\{x\\}$ is the complex

${\rm del}_{\Delta}(\\{x\\})=\\{G\in\Delta\leavevmode\nobreak\
|\leavevmode\nobreak\ x\notin G\\}.$

As above we will abuse notation and write ${\rm link}_{\Delta}(x)$
(respectively, ${\rm del}_{\Delta}(x)$) instead of ${\rm
link}_{\Delta}(\\{x\\})$ (respectively, ${\rm del}_{\Delta}(\\{x\\})$). A
vertex $x$ is a shedding vertex if for any facet $F\in\Delta$ with $x\in F$,
there exists a vertex $y\not\in F$ such that $(F\setminus\\{x\\})\cup\\{y\\}$
is also a face of $\Delta$. Equivalently, $x$ is a shedding vertex if every
facet of ${\rm del}_{\Delta}(x)$ is a facet of $\Delta$.

Vertex decomposable simplicial complexes are then defined recursively as
follows.

######  Definition 2.1.

A simplicial complex $\Delta$ is vertex decomposable if either

  1. (1)

$\Delta=\\{\emptyset\\}$, or $\Delta$ is a simplex, i.e., $\Delta=\langle
F\rangle$ for some $F\subseteq[n]$, or

  2. (2)

there exists a shedding vertex $x\in[n]$ such that
$\operatorname{link}_{\Delta}(x)$ and $\operatorname{del}_{\Delta}(x)$ are
vertex decomposable.

######  Remark 2.2.

We take this definition from Björner and Wachs [2]. All the complexes we
consider will be pure, and in this case our definition recovers the notion of
vertex decomposability introduced by Provan and Billera in [9].

We next collect some results regarding vertex decomposable complexes that will
be useful for our study. Recall that a simplicial complex $\Delta$ is a cone
if there exists a vertex $v\in V$ such that $v\in F$ for every facet
$F\in\Delta$. In this case there exists a simplicial complex $\Gamma$ on
vertex set $V\backslash\\{v\\}$ such that every face of $\Delta$ is either a
face of $\Gamma$, or else of the form $F\cup\\{v\\}$ for some face
$F\in\Gamma$. In this case we write $\Delta=\Gamma\ast v$. In the statement
below, for $k\leq\dim(\Delta)$ the $k$-skeleton of a pure simplicial complex
$\Delta$ is the simplicial complex whose facets are the faces of $\Delta$
having dimension $k$.

######  Lemma 2.3.

The following properties regarding vertex decomposability hold.

  1. (1)

[9, Proposition 3.1.1] All 0-dimensional complexes are vertex decomposable.

  2. (2)

[9, Proposition 3.1.2] A pure $1$-dimensional complex $\Delta$ is vertex
decomposable if and only if $\Delta$ is connected.

  3. (3)

[13, Lemma 3.10] Any $k$-skeleton of a vertex decomposable complex $\Delta$ is
vertex decomposable.

  4. (4)

[9, Proposition 2.4] A cone $\Delta=\Gamma\ast v$ is vertex decomposable if
and only if $\Gamma$ is vertex decomposable.

We also record the following observation.

######  Lemma 2.4.

Suppose $\Delta$ is a pure simplicial complex on $[n]$ with $n\geq 3$ obtained
by removing a single facet from the boundary of a simplex. Then $\Delta$ is
vertex decomposable.

###### Proof.

Suppose $\Delta$ has vertex set $[n]$, and without loss of generality suppose
the facet removed to obtain $\Delta$ is $\\{1,2,\dots,n-1\\}$. Then the facets
of $\Delta$ consist of all subsets of $[n]$ of the form $\\{n\\}\cup F$, where
$F$ is any $(n-2)$-subset of $[n-1]$. Hence $\Delta=\partial\Delta_{n-1}\ast
n$. Here $\partial\Delta_{n-1}$ denotes the boundary of the simplex on
$[n-1]$, which can be recovered as the $(n-3)$-skeleton of $\Delta_{n-1}$.
From Lemma 2.3 we conclude that $\Delta$ is vertex decomposable. ∎

The following lemma is immediate from the recursive definition of vertex-
decomposability, and we will use it without comment.

######  Lemma 2.5.

If $\mathcal{F}$ is a family of simplicial complexes, so that every
$\Delta\in\mathcal{F}$ is either a simplex or has a shedding vertex v with the
property that both $\operatorname{link}_{\Delta}(v)$ and
$\operatorname{del}_{\Delta}(v)$ are in $\mathcal{F}$, then every complex in
$\mathcal{F}$ is vertex-decomposable.

##  3\. Proof of Main Result

In this section we provide the proof of Theorem 1.1. In what follows, we let
$\Delta$ be a pure simplicial complex on $n$ vertices with codimension
$c=n-\dim\Delta-1$. If $F$ is a set of $\dim(\Delta)+1$ vertices that is not a
face of $\Delta$, we say that $F$ is an antifacet. Write $e(\Delta)$ for the
number of facets of $\Delta$ and $\bar{e}(\Delta)$ for the number of
antifacets of $\Delta$. Note that $\bar{e}(\Delta)=\binom{n}{c}-e(\Delta)$.

We start with a technical lemma.

######  Lemma 3.1.

If $n\geq c+2>3$ and $\bar{e}(\Delta)\leq 2c-1$, then $\Delta$ has at least
two vertices that each avoids at most $2c-3$ antifacets.

###### Proof.

We proceed by double counting on the set

$\mathcal{P}=\left\\{(v,F):v\text{ a vertex of }\Delta,F\text{ an antifacet of
$\Delta,v\notin F$}\right\\}.$

Counting by antifacets, we see that $\left|\mathcal{P}\right|\leq
c\cdot(2c-1)=2c^{2}-c$.

Suppose for contradiction that every vertex except for some vertex $w$ avoids
more than $2c-3$ antifacets. Then

(3.1)
$\left|\mathcal{P}\right|\geq(n-1)\cdot(2c-2)\geq(c+1)\cdot(2c-2)=2c^{2}-2.$

As $2c^{2}-c\geq 2c^{2}-2$ holds only if $c\leq 2$, we have reduced to the
case $c=2$. But in this case, the left-most inequality of (3.1) gives us that
$2\cdot 3\geq(n-1)\cdot 2$, so we are left with the case $n=4$.

Hence we are left with the case that $\Delta$ is a one-dimensional complex on
$4$ vertices. In this case, we have $\bar{e}(\Delta)\leq 3$ and $c=2$, and so
we need to show there must be at least two vertices that each avoids at most
$2c-3=1$ antifacets. Viewing the antifacets as edges in a graph on four
vertices, the antifacets give a graph on four vertices where every vertex has
degree at most two (since $\Delta$ cannot have an isolated vertex). We finish
the proof with the following easily-verified observation: For any graph on
four vertices with three or fewer edges, where the degree of each vertex is
$\leq 2$, there are at least two vertices that are each disjoint from at most
one edge. ∎

######  Remark 3.2.

Note that if $\Delta$ has the property that all vertices are shedding, then
for any $v$ we have that $\operatorname{\text{del}}_{\Delta}(v)$ is pure of
the same dimension as $\Delta$. Thus, in this situation Lemma 3.1 implies that
$\Delta$ has at least two vertices satisfying
$\overline{e}(\operatorname{\text{del}}_{\Delta}(v))\leq 2c-3$.

We make some other easy observations. Recall that a _minimal nonface_ of
$\Delta$ is a nonface of $\Delta$ that is minimal under inclusion with respect
to this property. Note that if $\\{v,w\\}$ is a minimal nonface of $\Delta$ of
cardinality two, then $w$ is _not_ a vertex of
$\operatorname{link}_{\Delta}(v)$.

The following lemma says that minimal nonfaces of cardinality two are rare
when $\dim(\Delta)\neq 1$ and the number of antifacets is small enough
(equivalently, if the number of facets is large enough relative to $n$).

######  Lemma 3.3.

If $\bar{e}(\Delta)\leq 2c-1$, then no minimal nonface of $\Delta$ has fewer
than $\dim(\Delta)$ vertices, and at most one minimal nonface has
$\dim(\Delta)$ vertices.

###### Proof.

A nonface of size $\dim(\Delta)-1$ is contained in $\binom{c+2}{2}$
antifacets. But $(c+2)(c+1)/2$ is greater than $2c-1$ for all $c$.

Each minimal nonface with $\dim(\Delta)$ vertices is contained in $c+1$
antifacets, and a pair of such minimal nonfaces is contained in at most one
common antifacet. But $2(c+1)-1$ is greater than $2c-1$, contradicting our
assumptions. The result follows. ∎

######  Corollary 3.4.

Suppose $\dim(\Delta)\geq 1$, and let $v$ be a vertex of $\Delta$. If
$\bar{e}(\Delta)\leq 2c-1$ and $b$ is the codimension of
$\operatorname{link}_{\Delta}(v)$, then
$\bar{e}(\operatorname{link}_{\Delta}(v))\leq 2b-1$.

###### Proof.

Note that since $\Delta$ is pure, we have that
$\dim(\operatorname{link}_{\Delta}(v))=\dim(\Delta)-1$. Also note that the
statement is trivial if $\dim(\Delta)\leq 1$, since in this case
$\bar{e}(\operatorname{link}_{\Delta}(v))=0$. If $\dim(\Delta)>2$, then by
Lemma 3.3 we have that $\Delta$ has no missing edge, so that
$b=(n-1)-(\dim(\Delta)-1)-1=c$. The result then follows by noting that if $F$
is an antifacet of $\operatorname{link}_{\Delta}(v)$, then $F\cup\\{v\\}$ is
an antifacet of $\Delta$. If $\dim(\Delta)=2$, then again by Lemma 3.3 we have
that $b=c-1$ (so also that $c\geq 1$), and there is a unique minimal nonfacet
$\\{v,w\\}$ having two vertices. Now, as before there are
$\bar{e}(\operatorname{link}_{\Delta}(v))$ antifacets of $\Delta$ containing
$v$ but not $w$, and an additional $n-2$ antifacets of $\Delta$ containing
$\\{v,w\\}$. We obtain that
$\bar{e}(\operatorname{link}_{\Delta}(v))\leq\bar{e}(\Delta)-(n-2)\leq(2c-1)-(c+1)=2b-c$,
which yields the desired. ∎

We restate the definition of a shedding vertex in the language of antifacets.

######  Lemma 3.5.

A vertex $w$ of $\Delta$ is a shedding vertex unless $w$ is contained in some
facet $F$ with the property that, for each vertex $u\notin F$, the set
$(F\setminus\\{w\\})\cup\\{u\\}$ is an antifacet.

We collect one more preliminary result.

######  Lemma 3.6.

If $\bar{e}(\Delta)\leq 2c-1$, then:

  1. (1)

Any vertex that is contained in at least $c$ antifacets is a shedding vertex;

  2. (2)

If $w$ is not a shedding vertex, and $F$ is a facet as in Lemma 3.5, then any
vertex $v\in F\setminus\\{w\\}$ is contained in $c$ antifacets, and in
particular is a shedding vertex.

###### Proof.

If $w$ is not a shedding vertex, then $w$ is contained in some facet $F$ so
that $(F\setminus\\{w\\})\cup\\{u\\}$ is an antifacet for each $u\notin F$. In
particular, there are $c$ antifacets that do not contain $w$, hence at most
$c-1$ that do contain $w$.

Moreover, since the set $F\setminus\\{w\\}$ is contained in $c$ antifacets,
the same holds for every $v\in F\setminus\\{w\\}$. ∎

We are now ready to prove our main result.

###### Proof of Theorem 1.1.

Recall that $\Delta$ is assumed to be a pure $d$-dimensional simplicial
complex on vertex set $[n]$ and codimension $c$, with at least
$\binom{n}{c}-2c+1$ facets, so that $\bar{e}(\Delta)\leq 2c-1$. The statement
can be checked directly for all simplicial complexes on $n\leq 3$ vertices. If
$c=0$ or $1$, then $\Delta$ is a simplex, or a simplex boundary with at most
one face removed, and the result follows by Lemma 2.4. On the other hand, if
$c=n-1$, then $\dim(\Delta)=0$, and the result is immediate.

It is also convenient to handle the case where $\dim(\Delta)=1$ separately. By
Lemma 2.3, a pure $1$-dimensional complex is vertex decomposable if and only
if it is connected. Supppose $\Delta$ is disconnected, where the smallest
connected component $\Gamma$ has $k$ vertices. As $\Delta$ is pure, we have
$k\geq 2$. Now there is no edge between $\Gamma$ and its vertex complement, so
$\Delta$ has at least $k\cdot(n-k)\geq 2\cdot(n-2)=2c$ antifacets, and we see
that $\Delta$ fails the hypotheses of the theorem.

Moving forward, we can assume $\dim(\Delta)\geq 2$ and that $3<c+2\leq n$. To
prove the theorem we wish to find a shedding vertex $v$ so that
$\operatorname{link}_{\Delta}(v)$ and $\operatorname{del}_{\Delta}(v)$ also
satisfy the hypotheses of the theorem. Note that we are using Lemma 2.5. First
observe that for any vertex $v$, ${\rm link}_{\Delta}(v)$ satisfies the
hypotheses by Corollary 3.4.

We next turn to the deletion. For this note that if $v$ is a shedding vertex,
then by definition $\dim(\operatorname{del}_{\Delta}(v))=\dim(\Delta)$. Since
the number of vertices of $\operatorname{del}_{\Delta}(v)$ is $n-1$, we have
that the codimension of $\operatorname{del}_{\Delta}(v)$ is $c-1$. Hence to
complete the proof we need to find a shedding vertex $v$ satisfying
$\bar{e}(\operatorname{del}_{\Delta}(v))\leq 2c-3$.

If every (or even all but one) vertex of $\Delta$ is a shedding vertex, then
we are done by Lemma 3.1. Otherwise, Lemma 3.6 yields a shedding vertex $v$
that is contained in at least $c$ antifacets, so that
$\bar{e}(\operatorname{del}_{\Delta}(v))\leq 2c-1-c$. In either case, we have
produced the desired shedding vertex. ∎

##  4\. Consequences and Concluding Remarks

We end with some additional comments and examples connected to our main
result. We first give an example to show that the bound in Theorem 1.1 is
optimal.

######  Example 4.1.

We construct, for any $2\leq c\leq n-2$, a pure simplicial complex $\Delta$ on
$n$ vertices that has codimension $c$ and $\binom{n}{c}-2c$ facets, and that
is not Cohen–Macaulay. Since any vertex decomposable complex is also
Cohen–Macaulay, this shows that the bound in Theorem 1.1 is optimal.

We start with the complete $(n-c-1)$-skeleton of the simplex on $n$ vertices,
and obtain $\Delta$ by removing the facets containing the following vertices:
all of $\\{1,\ldots,n-c-2\\},$ exactly one of $\\{n-c-1,n-c\\}$, and exactly
one of $\\{n-c+1,\ldots,n\\}$. Then we have removed exactly $2c$ facets, and
${\rm link}_{\Delta}(\\{1,\ldots,n-c-2\\})$ is disconnected, so not
Cohen–Macaulay. Since every link in a Cohen–Macaulay complex is also
Cohen–Macaulay, $\Delta$ is not Cohen–Macaulay.

######  Remark 4.2.

In the situation where $\dim(\Delta)=1$, so that $c=n-2$, we may view $\Delta$
as a graph on vertex set $[n]$ and our main result has a graph theoretic
interpretation. Since $\Delta$ is assumed to be pure, we consider graphs with
no isolated vertex. In this context, example 4.1 yields the union of a
complete graph with an isolated edge. Indeed, from Lemma 2.3 we know that a
pure 1-dimensional complex is vertex-decomposable if and only if it is
connected. Hence in this case Theorem 1.1 is equivalent to the following
statement in graph theory: an edge-cut of the complete graph $K_{n}$ into
nontrivial parts has size at least $2c=2n-4$. We refer to [4] for definitions
from graph theory.

######  Remark 4.3.

One can also ask whether the conclusion of Theorem 1.1 can be strengthened,
that is whether there is some property stronger than vertex decomposable that
is implied by $\Delta$ having “enough facets”. Two well-studied classes of
vertex decomposable simplicial complexes are independence complexes of
matroids and shifted complexes.

Recall that a pure simplicial complex $\Delta$ is the independence complex of
a matroid if it satisfies the following exchange property: if $F$ and $G$ are
facets of $\Delta$ such that $v\in F\backslash G$, then there exists a $w\in
G\backslash F$ such that $(F\backslash\\{v\\})\cup\\{w\\}$ is again a facet of
$\Delta$. A pure simplicial complex $\Delta$ is shifted if there exists a
(re)labeling of the vertex set $V=[n]=\\{1,\dots,n\\}$ such that whenever
$\\{v_{1},v_{2},\dots,v_{k}\\}$ is a face of $\Delta$, replacing any $v_{i}$
by a vertex with a smaller label again results in a face of $\Delta$.

We show that neither of these properties are implied by the assumptions in
Theorem 1.1. As an example, consider the complete graph $K_{4}$ as a
1-dimensional simplex on $n=4$ vertices (so that $c=2$). Theorem 1.1 implies
that if we remove 3 or fewer facets (edges) and are left with no isolated
vertices, we end up with a vertex decomposable complex. It turns out that we
can remove just two facets from $K_{4}$ to destroy these stronger properties.

On the one hand, we can delete the facets $\\{1,2\\}$ and $\\{1,3\\}$,
resulting in a complex that is easily seen not to be a matroid complex. On the
other hand, if we start with $K_{4}$ and delete the facets $\\{1,2\\}$ and
$\\{3,4\\}$ we are left with a 4-cycle, which is not shifted. Indeed the class
of shifted 1-dimensional complexes coincide with the class of threshold
graphs, which are known to be chordal.

We can also recover a result similar to [11, Theorem 2.1]. In particular, if
we assume $\Delta$ has “even more” facets, then $\Delta$ is automatically
pure, so it must be vertex decomposable.

######  Lemma 4.4.

Let $\Delta$ be a simplicial complex on vertex set $[n]$ of codimension $c$.
Suppose $\Delta$ has at least $\binom{n}{c}-c$ facets of dimension
$\dim(\Delta)=n-c-1$. Then $\Delta$ is pure.

###### Proof.

If $\Delta$ has a facet $F$ of dimension smaller than $\dim(\Delta)$, then $F$
can be extended to a set $S$ containing $\dim(\Delta)$ vertices. Namely, if
$G$ is a facet of dimension $\dim(\Delta)$, then $F\not\subset G$, giving
$|G\backslash F|\geq\dim(\Delta)-\dim(F)+1$. We obtain the set $S$ by adding
$\dim(\Delta)-\dim(F)$ vertices from $G\backslash F$ to $F$. Now, $S$ is
contained in $c+1$ sets of size $n-c$, none of which are facets of $\Delta$
(as $S$ properly contains the facet $F$). This is a contradiction to the
assumption that there are at least $\binom{n}{c}-c$ facets of dimension
$\dim(\Delta)=n-c-1$.

∎

We now derive a strengthening of [11, Theorem 2.1]:

######  Corollary 4.5.

Let $\Delta$ be a simplicial complex on vertex set $[n]$ of codimension $c$.
If $\Delta$ has at least $\binom{n}{c}-c$ facets of dimension
$\dim(\Delta)=n-c-1$, then $\Delta$ is vertex decomposable.

###### Proof.

By Lemma 4.4, $\Delta$ is a pure simplicial complex of codimension $c$ with at
least $\binom{n}{c}-c\geq\binom{n}{c}-2c+1$ facets. Now apply Theorem 1.1. ∎

Terai and Yoshida showed that Stanley-Reisner rings having large
multiplicities are Cohen-Macaulay [11, Theorem 3.1] by proving that the dual
ideal of the Stanley-Reisner ideal of $\Delta$ has a linear resolution [11,
Theorem 3.3]. We can also recover this dual version as a direct consequence of
our main result by employing Stanley-Reisner theory and the properties of
Alexander duality, in particular, Eagon and Reiner’s classification of square-
free monomial ideals with a linear resolution. The following corollary may be
of interest for those researchers interested in monomial ideals. We assume
that the reader is familiar with the Stanley-Reisner correspondence; for
undefined terminology, see [8]. The following result originally appeared as
[11, Theorem 3.3].

######  Corollary 4.6.

Let $I$ be a square-free monomial ideal of $R=\mathbb{K}[x_{1},\ldots,x_{n}]$
such that every generator has degree $c$. If $I$ has at least
$\binom{n}{c}-2c+1$ generators, then $I$ has a linear resolution.

###### Proof.

Given a square-free monomial $m=x_{i_{1}}\cdots x_{i_{c}}$ of degree $c$, set
$F_{m}=[n]\setminus\\{i_{1},\ldots,i_{c}\\}$. So, if $I=\langle
m_{1},\ldots,m_{t}\rangle$ is a square-free monomial ideal where each
generator has degree $c$, then $\Delta=\langle
F_{m_{1}},\ldots,F_{m_{c}}\rangle$ is a pure simplicial complex of codimension
$c$ with at least $\binom{n}{c}-2c+1$ facets. By Theorem 1.1, $\Delta$ is a
vertex decomposable simplicial complex, and consequently, $\Delta$ is Cohen-
Macaulay.

The ideal $I$ is the Alexander dual of $I_{\Delta}$, the Stanley-Reisner ideal
of $\Delta$. Since $\Delta$ is Cohen-Macaulay, the Eagon-Reiner Theorem [5]
implies that $I$ has a linear resolution. ∎

Our results also have applications to the study of Simon’s Conjecture [10], a
statement involving the structure of shellable complexes. To explain this
connection we first review some relevant concepts.

######  Definition 4.7.

A pure $d$-dimensional simplicial complex $\Delta$ is shellable if there
exists an ordering of its facets $F_{1},F_{2},\dots,F_{s}$ such that for all
$k=2,3,\dots,s$ the simplicial complex

$\left(\bigcup_{i=1}^{k-1}\langle F_{i}\rangle\right)\cap\langle F_{k}\rangle$

is pure of dimension $d-1$.

By convention the void complex $\emptyset$ and the empty complex
$\\{\emptyset\\}$ are both shellable. Note that any pure $d$-dimensional
complex $\Delta$ on vertex set $[n]$ is a subcomplex of $\Delta_{n}^{(d)}$,
the $d$-dimensional skeleton of the simplex on $[n]$. It is known that
$\Delta_{n}^{(d)}$ is shellable, and one can ask if it is possible to produce
a shelling of $\Delta_{n}^{(d)}$ that begins with a shelling of $\Delta$.

######  Definition 4.8.

A pure $d$-dimensional simplicial complex $\Delta$ on vertex set $[n]$ is
shelling completable if there exists a shelling of $\Delta$ that is the
initial sequence of a shelling of $\Delta_{n}^{(d)}$.

With these notions, we can formulate Simon’s Conjecture as follows.

######  Conjecture 4.9.

Every shellable complex is shelling completable.

In [3] it is shown that every pure vertex decomposable complex is shelling
completable. Hence our Theorem 1.1 implies that any counterexample to Simon’s
Conjecture (a pure shellable complex that is not shelling completable) must
have “not too many facets”. In particular if $\Delta$ has codimension $c$,
then any counterexample can have at most $\binom{n}{c}-2c$ facets.

There are other ways to detect the vertex decomposability of a simplicial
complex $\Delta$ in terms of combinatorial data. In [7] Lasoń provides a
sufficient condition for vertex decomposability in terms of the $f$-vector of
$\Delta$ (more specifically the number of facets and ridges). To describe
these results, suppose $\Delta$ is a pure simplicial complex on vertex set
$[n]$, with dimension $\dim(\Delta)=d$ and codimension
$\operatorname{{codim}}(\Delta)=c=n-d-1$. Recall that the $f$-vector of
$\Delta$ is $f(\Delta)=(f_{0},f_{1},\ldots,f_{d})$ where $f_{i}$ is the number
of faces of $\Delta$ of dimension $i$. Theorem 1.1 implies that if
$f_{d}\geq\binom{n}{c}-2c+1$, then $\Delta$ is vertex decomposable.

We say that a simplicial complex $\Delta$ is extremal if $\Delta$ is pure of
dimension $t$ with $r$ facets such that it has the minimum number of faces of
dimension $(t-1)$ among all simplicial complexes of dimension $t$ and
$r$-faces.

As shown by [7, Corollary 1], an extremal simplicial complex can be determined
from its $f$-vector. The main result from [7] is the following.

######  Theorem 4.10.

[7, Theorem 5] An extremal simplicial complex is vertex decomposable.

######  Example 4.11.

To see that our result does not follow from Lasoń’s work, let $n=6$ and
consider the pure two-dimensional simplicial complex with facets

$\\{1,2,3\\},\leavevmode\nobreak\ \\{1,4,5\\},\leavevmode\nobreak\
\\{1,2,6\\},\leavevmode\nobreak\ \\{1,4,6\\},\leavevmode\nobreak\
\\{2,4,5\\},\leavevmode\nobreak\ \\{3,4,5\\},\leavevmode\nobreak\ \\{3,5,6\\}$

and any other 9 facets of dimension 2, for a total of 16 facets of dimension
2. In this case, the codimension is $c=3$, and $16\geq\binom{6}{3}-2\cdot
3+1=15$, so, this simplicial complex is vertex decomposable by our Theorem
1.1. By our construction, this simplicial complex has $f$-vector $(6,15,16)$
(our initial choice of facets forces this simplicial complex to contain all
the $1$-dimensional faces). However, this $f$-vector does not satisfy [7,
Corollary 1]. Indeed, there is a pure simplicial complex with $f$-vector
$(6,14,16)$, namely the simplicial complex which contains all the facets of
dimension two except $\\{1,5,6\\},\leavevmode\nobreak\
\\{2,5,6\\},\leavevmode\nobreak\ \\{3,5,6\\},$ and $\\{4,5,6\\}$ (this
simplicial complex does not contain the face $\\{5,6\\}$). We see that our
simplicial complex is not extremal, and hence one can not deduce that it is
vertex decomposable from [7].

### Acknowledgements

The authors thank Hailong Dao for his feedback and suggestions. They also
thank Martin Milanič for answering questions about the graph theory
literature. This project began at the workshop “Interactions Between
Topological Combinatorics and Combinatorial Commutative Algebra” held at the
Banff International Research Station (BIRS) in April 2023. We thank BIRS and
the organizers for the opportunity to work together. Dochtermann is partly
supported by Simons Foundation Grant $\\#964659$. Nair is partly supported by
Dao’s Simons Foundation Grant FND0077558. Van Tuyl’s research is supported by
NSERC Discovery Grant 2019-05412. Woodroofe’s research is supported in part by
the Slovenian Research Agency (research program P1-0285 and research projects
N1-0160, J1-2451, J1-3003 and J1-50000).

## References

  * [1] Anders Björner, _Topological methods_ , Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 1819–1872. MR 1373690
  * [2] Anders Björner and Michelle L. Wachs, _Shellable nonpure complexes and posets. II_ , Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945–3975. MR 98b:06008
  * [3] Michaela Coleman, Anton Dochtermann, Nathan Geist, and Suho Oh, _Completing and extending shellings of vertex decomposable complexes_ , SIAM J. Discrete Math. 36 (2022), no. 2, 1291–1305. MR 4431959
  * [4] Reinhard Diestel, _Graph theory_ , fifth ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. MR 3644391
  * [5] John A. Eagon and Victor Reiner, _Resolutions of Stanley-Reisner rings and Alexander duality_ , J. Pure Appl. Algebra 130 (1998), no. 3, 265–275. MR 1633767 (99h:13017)
  * [6] Jürgen Herzog and Takayuki Hibi, _Monomial ideals_ , Graduate Texts in Mathematics, vol. 260, Springer-Verlag London Ltd., London, 2011. MR 2724673 (2011k:13019)
  * [7] Michał Lasoń, _$f$ -vectors implying vertex decomposability_, Discrete Comput. Geom. 49 (2013), no. 2, 296–301. MR 3017912
  * [8] Ezra Miller and Bernd Sturmfels, _Combinatorial commutative algebra_ , Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005. MR 2110098 (2006d:13001)
  * [9] J. Scott Provan and Louis J. Billera, _Decompositions of simplicial complexes related to diameters of convex polyhedra_ , Math. Oper. Res. 5 (1980), no. 4, 576–594. MR 593648 (82c:52010)
  * [10] Robert Samuel Simon, _Combinatorial properties of “cleanness”_ , J. Algebra 167 (1994), no. 2, 361–388. MR 1283293
  * [11] Naoki Terai and Ken-ichi Yoshida, _Stanley-Reisner rings with large multiplicities are Cohen-Macaulay_ , J. Algebra 301 (2006), no. 2, 493–508. MR 2236754
  * [12] Rafael H. Villarreal, _Monomial algebras_ , second ed., Monographs and Research Notes in Mathematics, CRC Press, Boca Raton, FL, 2015. MR 3362802
  * [13] Russ Woodroofe, _Chordal and sequentially Cohen-Macaulay clutters_ , Electron. J. Combin. 18 (2011), no. 1, Paper 208, 20 pages. MR 2853065