# Cooperating RPN’s Improve Few-Shot Object Detection

Weilin Zhang, Yu-Xiong Wang, David A. Forsyth
Department of Computer Science
University of Illinois at Urbana-Champaign
{weilinz2, yxw<EMAIL_ADDRESS>

###### Abstract

Learning to detect an object in an image from very few training examples -
few-shot object detection - is challenging, because the classifier that sees
proposal boxes has very little training data. A particularly challenging
training regime occurs when there are one or two training examples. In this
case, if the region proposal network (RPN) misses even one high intersection-
over-union (IOU) training box, the classifier’s model of how object appearance
varies can be severely impacted. We use multiple distinct yet cooperating
RPN’s. Our RPN’s are trained to be different, but not too different; doing so
yields significant performance improvements over state of the art for COCO and
PASCAL VOC in the very few-shot setting. This effect appears to be independent
of the choice of classifier or dataset.

##  1 Introduction

Achieving accurate few-shot object detection is difficult, because one must
rely on a classifier building a useful model of variation in appearance with
very few examples. This paper identifies an important effect that causes
existing detectors to have weaker than necessary performance in the few-shot
regime. By remediating this difficulty, we obtain substantial improvements in
performance with current architectures.

The effect is most easily explained by looking at the “script” that modern
object detectors mostly follow. As one would expect, there are variations in
detector structure, but these do not mitigate the effect. A modern object
detector will first find promising image locations; these are usually, but not
always, boxes. We describe the effect in terms of boxes reported by a region
proposal network (RPN) (Ren et al., 2015), but expect that it applies to other
representations of location, too. The detector then passes the promising
locations through a classifier to determine what, if any, object is present.
Finally, it performs various cleanup operations (non-maximum suppression,
bounding box regression, etc.), aimed at avoiding multiple predictions in the
same location and improving localization. The evaluation procedure for
reported labeled boxes uses an intersection-over-union (IOU) test as part of
determining whether a box is relevant.

(a) TFA

(b) Ours

Figure 1: Few-shot detectors are subject to the proposal neglect effect. On
the left: an image (from the PASCAL VOC split 3 novel classes test set)
showing the top 10 proposals from a state-of-the-art few-shot detector TFA
(Wang et al., 2020). On the right: the top 10 proposals from our cooperating
RPN’s. Cat is in the novel classes {boat, cat, mbike, sheep, sofa} (i.e., both
models are cat detectors). Note that the classifier in TFA will not see a cat
box, and so it cannot detect the cat. This is a disaster when this image is
used in training. For our approach, the cat box is found and is high in the
top 10 proposals.

A detector that is trained for few-shot detection is trained on two types of
categories. Base categories have many training examples, and are used to train
an RPN and the classifier. Novel categories have one (or three, or five, etc.)
examples per category. The existing RPN is used to find boxes, and the
classifier is fine-tuned to handle novel categories.

Now assume that the detector must learn to detect a category from a single
example. The RPN is already trained on other examples. It produces a
collection of relevant boxes, which are used to train the classifier. The only
way that the classifier can build a model of the categories variation in
appearance is by having multiple high IOU boxes reported by the RPN. In turn,
this means that an RPN that behaves well on base categories may create serious
problems for novel categories. Imagine that the RPN reports only a few of the
available high IOU boxes in training data. For base categories, this is not a
problem; many high IOU boxes will pass to the classifier because there is a
lot of training data, and so the classifier will be able to build a model of
the categories variation in appearance. This variation will be caused by
effects like aspect, in-class variation, and the particular RPN’s choice of
boxes. But for novel categories, an RPN must report as many high IOU boxes as
possible, because otherwise the classifier will have too weak a model of
appearance variation – for example, it might think that the object must be
centered in the box. This will significantly depress accuracy. As Figure 1 and
our results illustrate, this effect (which we call proposal neglect) is
present in the state-of-the-art few-shot detectors.

One cannot escape this effect by simply reporting lots of boxes, because doing
so will require the classifier to be very good at rejecting false positives.
Instead, one wants the box proposal process to not miss high IOU boxes,
without wild speculation. We offer a relatively straightforward strategy. We
train multiple RPN’s to be somewhat redundant (so that if one RPN misses a
high IOU box, another will get it), without overpredicting. In what follows,
we demonstrate how to do so and show how to balance redundancy against
overprediction.

Our contributions are three-fold: (1) We identify an important effect in few-
shot object detection that causes existing detectors to have weaker than
necessary performance in the few-shot regime. (2) We propose to overcome the
proposal neglect effect by utilizing RPN redundancy. (3) We design an RPN
ensemble mechanism that trains multiple RPN’s simultaneously while enforcing
diversity and cooperation among RPN’s. We achieve state-of-the-art performance
on COCO and PASCAL VOC in very few-shot settings.

##  2 Background

Object Detection with Abundant Data. The best-performing modern detectors are
based on convolutional neural networks. There are two families of
architecture, both relying on the remarkable fact that one can quite reliably
tell whether an image region contains an object independent of category
(Endres & Hoiem, 2010; van de Sande et al., 2011). In serial detection, a
proposal process (RPN/s in what follows) offers the classifier a selection of
locations likely to contain objects, and the classifier labels them, with the
advantage that the classifier “knows” the likely support of the object fairly
accurately. This family includes R-CNN and its variants (for R-CNN (Girshick
et al., 2014); Fast R-CNN (Girshick, 2015); Faster R-CNN (Ren et al., 2015);
Mask R-CNN (He et al., 2017); SPP-Net (He et al., 2015); FPN (Lin et al.,
2017); and DCN (Dai et al., 2017)). In parallel, the proposal process and
classification process are independent; these methods can be faster, but the
classifier “knows” very little about the likely support of the object, which
can affect accuracy. This family includes YOLO and its variants (for YOLO
versions (Redmon et al., 2016; Redmon & Farhadi, 2017; 2018; Bochkovskiy et
al., 2020); SSD (Liu et al., 2016); Cornernet (Law & Deng, 2018); and
ExtremeNet (Zhou et al., 2019)). This paper identifies an issue with the
proposal process that can impede strong performance when there is very little
training data (the few-shot case). The effect is described in the context of
serial detection, but likely occurs in parallel detection too.

Few-Shot Object Detection. Few-shot object detection involves detecting
objects for which there are very few training examples. There is a rich few-
shot classification literature (roots in (Thrun, 1998; Fei-Fei et al., 2006)).
Dvornik et al. (2019) uses ensemble procedures for few-shot classification. As
to detection, Chen et al. (2018) proposes a regularized fine-tuning approach
to transfer knowledge from a pre-trained detector to a few-shot detector.
Schwartz et al. (2019) exploits metric-learning for modeling multi-modal
distributions for each class. State-of-the-art few-shot detectors are usually
serial (Wang et al., 2019; Yan et al., 2019; Wang et al., 2020; Fan et al.,
2020; Wu et al., 2020; Xiao & Marlet, 2020). The existing literature can be
seen as variations on a standard framework, where one splits data into two
sets of categories: base classes $C_{b}$ (which have many training examples)
and novel classes $C_{n}$ (which have few). The RPN and classifier are then
trained with instances from the base classes, producing a detector for
$|C_{b}|$ categories. The final layer of the resulting classifier is expanded
to classify into $|C_{b}|+|C_{n}|$ classes by inserting random weights
connecting the final feature layer to the $|C_{n}|$ novel categories. Now the
model is fine-tuned using either only the novel class instances or a balanced
dataset containing training instances of both base and novel classes. Wang et
al. (2020) shows that a simple two-stage fine-tuning approach outperforms
other complex methods. Much work seeks improvements by applying few-shot
classification techniques. Kang et al. (2019) designs a meta-model that learns
to reweight pre-trained features given few-shot data. Wang et al. (2019) and
Yan et al. (2019) further explore the meta-learning direction by attaching
meta-learned classifiers to Faster R-CNN. Wu et al. (2020) improves few-shot
detection by positive sample refinement.

Relatively little work adjusts the proposal process, which is usually seen as
robust to few-shot issues because there are many base examples. One
possibility is to introduce attention mechanisms and feed category-aware
features instead of plain image features into the proposal process (Hsieh et
al., 2019; Fan et al., 2020; Xiao & Marlet, 2020; Osokin et al., 2020), as
well as re-ranking proposals based on similarity with query images (Hsieh et
al., 2019; Fan et al., 2020). Making the RPN category-aware improves the
quality of novel class proposals, but at inference time the model suffers from
catastrophic forgetting of base categories – current category-aware features
cannot summarize the very large number of base class examples efficiently or
accurately. An RPN that is generally well-behaved can still create serious
trouble in the few-shot case by missing high IOU proposals for the novel
classes during fine-tuning – the proposal neglect effect. We show that this
problem is severe in the few-shot regime, and can be fixed by a carefully
constructed ensemble of RPNs without substantial loss of performance for the
base classes.

Evaluating Few-Shot Detectors. The standard procedure is to compute average
precision (AP) separately for novel and base categories for a detector that is
engineered to detect $|C_{b}|+|C_{n}|$ classes, typically using standard
test/train splits and standard novel/base splits (Wang et al., 2020). This
evaluation procedure is the same as in incremental few-shot detection (Yang et
al., 2020; Pérez-Rúa et al., 2020). This procedure makes sense, because in
most applications an incoming test image could contain instances from both
base and novel classes. Furthermore, the standard procedure exposes any
catastrophic forgetting that occurs. However, other evaluation methodologies
occur, and some detectors are evaluated using variant procedures, making the
comparison of AP’s difficult. In one variant, the detector detects only the
$|C_{n}|$ novel classes or only one novel class. In this paper, all reported
results are for the standard procedure; when relevant, we re-implement and re-
evaluate using the standard procedure.

##  3 Our Approach

We believe that the proposal neglect effect is generic, and it applies to any
detector that uses a structure like the standard structure. For this reason,
we focus on finding and fixing the effect within a standard state-of-the-art
few-shot object detection framework, as described below.

Few-Shot Object Detection Framework. We use the few-shot detection setting
introduced in Kang et al. (2019). We split the dataset into two sets of
categories: base classes $C_{b}$ and novel classes $C_{n}$. As shown in Figure
2, the training process is two-phase: (1) base classes training, and (2) fine-
tuning with novel classes. In phase 1, the model is trained with base class
instances which results in a $|C_{b}|$-way detector. After base classes
training, weights for novel classes are randomly initialized, making the
classifier a $(|C_{b}|+|C_{n}|)$-way classifier. In phase 2, the model is
fine-tuned using either a set of few novel class instances or a balanced
dataset containing both novel and base classes. After the fine-tuning phase,
we evaluate our model by average precision (AP) on novel and base categories.
Although the focus of few-shot detection is the novel classes, since most test
images contain instances from both base and novel classes, it is essential to
maintain good performance on base classes.

Figure 2: Illustration of two-phase training in Faster R-CNN. During phase 1,
all blocks are trained. During phase 2, only the top-layer classifier and
bounding box regressor are fine-tuned. Figure 3: Left is the original
structure for the RPN in Faster R-CNN; right is our CoRPNs, consisting of
cooperating box classifiers.

We adopt the widely-used Faster R-CNN (Ren et al., 2015) as our base model. As
shown in Figure 2, Faster R-CNN is a serial detector, which consists of a
backbone image feature extractor, a regional proposal network (RPN), followed
by the region of interest (ROI) pooling layer, and a bounding box classifier
and a bounding box regressor on top of the model. The RPN determines if a box
is a foreground or a background box. Following the RPN is non-maximum
suppression (NMS) which ranks and selects top proposal boxes. After passing
the ROI pooling layer, the predictor’s head classifies and localizes each box.
In phase 1, the whole model is trained on many-shot base class instances.
Phase 2 fine-tunes the head classifier and the bounding box regressor with
novel class instances; everything before and including the proposal generator
is frozen.

Learning Cooperating RPN’s (CoRPNs). We wish to avoid high IOU boxes for novel
classes being dropped by RPN when novel classes are trained. Our strategy is
to train multiple redundant RPN’s. The RPN’s should be distinct, but cooperate
– if one misses a high IOU box, we want another to find it. However, they
should not be so distinct that the classifier is flooded with false positives.

As Figure 3 shows, Faster R-CNN’s RPN consists of a feature extractor, a
binary classifier (which decides whether a box is foreground or background),
and a bounding box regressor (which is not relevant to our current purpose).
There is no reason for our RPN’s to use distinct sets of features, and we do
not want to create problems with variance, so we construct redundant
classifiers while keeping both the feature extractor and the bounding box
regressor shared between all RPN’s. In what follows, a reference to an RPN is
actually a reference to the RPN classifier, unless otherwise noted. An RPN
with a single classifier is trained with a cross-entropy loss
$\mathcal{L}_{cls}=\mathcal{L}_{CE}$ and produces a single prediction. In our
case, we train $N$ different binary classifiers simultaneously, and must
determine (1) what prediction is made at test time and (2) what gradient goes
to what classifier at training time. At test time, a given box gets the score
from the most certain RPN. If the highest foreground probability is closer to
one than the highest background probability, the box is foreground; otherwise,
it is background.

Training time is more interesting. Merely taking the gradient of the best RPN
score is not good enough, because we may find that one RPN scores all boxes,
and the others do nothing interesting. For any foreground box, we want at
least one RPN to have a very strong foreground score and all others to have
good foreground scores too (so that no foreground box is missed).

We use the following strategy. For a specific anchor box $i$, each RPN $j$
outputs a raw score $r_{i}^{j}$, indicating if the box is a foreground box or
not: $r_{i}=[r^{1}_{i},r^{2}_{i},\dots,r^{N}_{i}].$ After applying a sigmoid,
the $j$th RPN produces the foreground probability
$f^{j}_{i}=\sigma(r^{j}_{i})$ for anchor box $i$. We choose the score from the
$j^{*}$th RPN such that
$j^{*}={\mathrm{argmin}_{j}}\min\\{f^{j}_{i},1-f^{j}_{i}\\}$, namely the most
certain RPN which produces probability closest to the edge of the $[0,1]$
interval. At training time, only the chosen $j^{*}$th RPN gets the gradient
from anchor box $i$. The RPN selection procedure is per-box, even adjacent
boxes can pass through different RPN’s.

Other than the standard cross-entropy loss, we use two additional loss terms:
a diversity loss $L_{div}$ encourages RPN’s to be distinct, and a cooperation
loss $L_{coop}$ encourages cooperation and suppresses foreground false
negatives. The final loss
$\mathcal{L}_{cls}:=\mathcal{L}^{j^{*}}_{CE}+\lambda_{d}\mathcal{L}_{div}+\lambda_{c}\mathcal{L}_{coop}$,
where $\lambda_{d}$ and $\lambda_{c}$ are trade-off hyperparameters.

Enforcing Diversity. We do not want our RPN’s to be too similar. For each
positive anchor box, RPN responses should be different because we want ensure
that at novel class training time, if one RPN misses a high IOU anchor box,
another will find it. To this end, we propose a methodology to enforce
diversity among RPN’s. Given a set of $N_{A}$ anchor boxes, the $N$ RPN’s
produce an $N$ by $N_{A}$ matrix of probabilities
$\mathcal{F}=[f^{1},f^{2},\dots,f^{N}]^{T}$. The covariance matrix
$\Sigma(\mathcal{F})$ is
$\Sigma(\mathcal{F})=\operatorname{E}[(f^{j}-\operatorname{E}[f^{j}])(f^{k}-\operatorname{E}[f^{k}])]$.
We define the diversity loss $\mathcal{L}_{div}$ by the log determinant loss
$\mathcal{L}_{div}:=-\log(\det(\Sigma(\mathcal{F})))$.

By the diversity loss, we encourage the probability matrix to have rank $N$,
so each RPN is reacting differently on the collection of $N_{A}$ boxes. This
procedure ensures each RPN to be the most certain RPN for some boxes, so that
every RPN is being selected and trained. Omitting this loss can cause an RPN
to receive no or little training.

Learning to Cooperate. We also want the RPN’s to cooperate so that they all
agree to a certain extent for foreground boxes. We propose a cooperation loss
to prevent any RPN from firmly rejecting any foreground box. For foreground
box $i$, with the $j$th RPN, we define the cooperation loss
$\mathcal{L}_{coop}^{i,j}:=\max\\{0,\phi-f^{j}_{i}\\}$, where $\phi$ is a
constant parameter (usually less than 0.5), acting as a lower bound for each
RPN’s probability assigning to a foreground box. If a RPN’s response is below
$\phi$, that RPN is going to be penalized. The final cooperation loss is an
average of cooperation losses over all foreground boxes and all RPN’s.

##  4 Experiments

Datasets and Implementation Details. We evaluate our approach on two widely-
used few-shot detection benchmarks: MS-COCO (Lin et al., 2014) and PASCAL VOC
(07 + 12) (Everingham et al., 2010). For a fair comparison, we use the same
train/test splits and novel class instances as in Kang et al. (2019); Wang et
al. (2020) to learn and evaluate all models. On COCO, we report base/novel
classes AP, AP50, and AP75 under shots 1, 2, 3, 5, 10, and 30. On PASCAL VOC,
we report AP50 for three different base/novel classes splits under shots 1, 2,
3, 5, and 10. Consistent with recent works (Yan et al., 2019; Wang et al.,
2020), we mainly use an ImageNet pretrained (Russakovsky et al., 2015)
ResNet-101 architecture (He et al., 2016) as the backbone for all models,
unless otherwise noted. More implementation details are included in the
Appendix.

Baselines and Evaluation Procedure. To investigate the proposal neglect effect
and for a fair comparison, we mainly focus on comparing against the state-of-
the-art baseline TFA (Wang et al., 2020). Our approach introduces CoRPNs into
TFA, while keeping other model components and design choices unchanged. In
addition, we thoroughly compare with a variety of recent few-shot detectors,
including CoAE (Hsieh et al., 2019), Meta R-CNN (Yan et al., 2019), FSOD (Fan
et al., 2020), MPSR (Wu et al., 2020), FSDetView (Xiao & Marlet, 2020), and
ONCE (Pérez-Rúa et al., 2020). These baselines address other aspects of few-
shot detection which are different from us (Section 2), and their
modifications are thus largely orthogonal to our effort here. Note that our
evaluation follows the standard procedure in Wang et al. (2020). As explained
in Section 2, this standard procedure computes AP separately for novel and
base categories for a detector that is engineered to detect $|C_{b}|+|C_{n}|$
classes. For a fair comparison, we re-evaluate CoAE (Hsieh et al., 2019) and
FSOD (Fan et al., 2020) using the standard procedure.

Main Results. Tables 1 and 2 summarize the results for novel classes on COCO
and PASCAL VOC, respectively, and Table 3 summarizes the results for base
classes on COCO.

Comparisons with the Main Baseline TFA on Novel Classes. From Tables 1 and 2,
we have the following important observations. (I) Our approach produces a
substantial improvement in AP over TFA (Wang et al., 2020) on novel classes in
the very low-shot regime (1, 2, and 3 shots), and marginal improvement or
sometimes slight degradation in the higher-shot regime. These improvements are
manifest for both existing benchmarks. Interestingly, on the more challenging
COCO dataset, our improvements over TFA are consistent across different shots
(except slight degradation in 30 shot under AP75 with fully-connected
classifier). (II) We investigate two types of classifiers: either fully-
connected (denoted as ‘fc’ in Tables 1 and 2) or cosine (denoted as ‘cos’ in
Tables 1 and 2). Note that our approach obtains improvements regardless of
classifier choice. This is because CoRPNs is a strategy to control variance in
the estimate of classifier parameters that applies independently of the
classifier. Any high IOU box missing from the RPN output in the training phase
must cause variance for the few-shot regime. Because there are very few such
boxes, the effect of not losing boxes is pronounced. We provide visualization
comparisons of detection results in the Appendix.

Comparisons with Other State-of-the-Art Approaches. With our simple
modification on RPN, we also outperform other sophisticated approaches on both
benchmarks in the very low-shot regime, and achieve comparable performance in
the higher-shot regime. In particular, we significantly outperform those
baselines that introduce attention mechanisms for adjusting proposal
generation (Hsieh et al., 2019; Fan et al., 2020). For other approaches that
improve few-shot detection from different perspectives, such as exploiting
better multi-scale representation (Wu et al., 2020), our approach can be
potentially combined with them for further improvements.

Comparisons on Base Classes. While improving detection on novel classes
through fine-tuning, we maintain strong performance on base classes without
suffering from catastrophic forgetting as shown in Table 3. By contrast, the
performance of the state-of-the-art baselines dramatically drops,
demonstrating that they cannot simultaneously deal with both novel and base
classes.

|  |  | 1-shot | 2-shot | 3-shot
---|---|---|---|---|---
| Method | Backbone |  AP | AP50 | AP75 | AP | AP50 | AP75 | AP | AP50 | AP75
Ours | CoRPNs w/ fc | ResNet-101 |  3.4 | 6.7 | 3.0 | 5.4 | 10.4 | _5.1_ | 7.1 | 13.7 | _6.8_
CoRPNs w/ cos | ResNet-101 |  4.1 | _7.2_ | 4.4 | 5.4 | 9.6 | 5.6 | 7.1 | _13.2_ | 7.2
CoRPNs w/ cos | ResNet-50 |   _3.7_ | 6.8 | _3.8_ | 4.7 | 8.8 | 4.4 | 6.3 | 12.0 | 6.0
Main baselines | TFA w/ fc (Wang et al., 2020) | ResNet-101 |  2.9 | 5.7 | 2.8 | 4.3 | 8.5 | 4.1 | 6.7 | 12.6 | 6.6
TFA w/ cos (Wang et al., 2020) | ResNet-101 |  3.4 | 5.8 | _3.8_ | 4.6 | 8.3 | 4.8 | 6.6 | 12.1 | 6.5
Other baselines | Meta R-CNN (Yan et al., 2019) | ResNet-101 |  – | – | – | – | – | – | – | – | –
FRCN+ft-full (Wang et al., 2020) | ResNet-101 |  – | – | – | – | – | – | – | – | –
MPSR (Wu et al., 2020) | ResNet-101 |  2.3 | 4.1 | 2.3 | 3.5 | 6.3 | 3.4 | 5.2 | 9.5 | 5.1
FsDetView (Xiao & Marlet, 2020) | ResNet-101 |  2.9 |  8.3 | 1.2 | 3.7 | _10.3_ | 1.6 | 4.7 | 12.9 | 2.0
ONCE (Pérez-Rúa et al., 2020) | ResNet-50 |  0.7 | – | – | – | – | – | – | – | –
FSOD* (Fan et al., 2020) | ResNet-50 |  2.4 | 4.8 | 2.0 | 2.9 | 5.9 | 2.7 | 3.7 | 7.2 | 3.3
|  |  | 5-shot | 10-shot | 30-shot
| Method | Backbone |  AP | AP50 | AP75 | AP | AP50 | AP75 | AP | AP50 | AP75
Ours | CoRPNs w/ fc | ResNet-101 |  8.9 | 16.9 | _8.6_ | _10.5_ | 20.2 | _9.8_ | 13.5 | _25.0_ | 12.9
CoRPNs w/ cos | ResNet-101 |   _8.8_ | _16.4_ | 8.7 | 10.6 | _19.9_ | 10.1 | 13.9 | 25.1 | 13.9
CoRPNs w/ cos | ResNet-50 |  7.8 | 14.4 | 7.6 | 9.0 | 17.6 | 8.3 | 13.4 | 24.6 | 13.3
Main baselines | TFA w/ fc (Wang et al., 2020) | ResNet-101 |  8.4 | 16.0 | 8.4 | 10.0 | 19.2 | 9.2 | 13.4 | 24.7 | 13.2
TFA w/ cos (Wang et al., 2020) | ResNet-101 |  8.3 | 15.3 | 8.0 | 10.0 | 19.1 | 9.3 | _13.7_ | 24.9 | _13.4_
Other baselines | Meta R-CNN (Yan et al., 2019) | ResNet-101 |  – | – | – | 8.7 | – | 6.6 | 12.4 | – | 10.8
FRCN+ft-full (Wang et al., 2020) | ResNet-101 |  – | – | – | 9.2 | – | 9.2 | 12.5 | – | 12.0
MPSR (Wu et al., 2020) | ResNet-101 |  6.7 | 12.6 | 6.4 | 9.7 | 18.0 | 9.4 | _13.7_ | _25.0_ | _13.4_
FsDetView (Xiao & Marlet, 2020) | ResNet-101 |  5.8 | 15.6 | 2.9 | 6.7 | 17.3 | 3.7 | 9.6 | 22.1 | 6.6
ONCE (Pérez-Rúa et al., 2020) | ResNet-50 |  1.0 | – | – | 1.2 | – | – | – | – | –
| FSOD* (Fan et al., 2020) | ResNet-50 |  4.2 | 8.2 | 4.0 | 4.3 | 8.7 | 3.8 | 5.4 | 10.4 | 5.0

Table 1: Few-shot detection performance on COCO novel classes. The upper row
shows the 1, 2, 3-shot results, and the lower row shows the 5, 10, 30-shot
results. Results in red are the best, and results in _blue_ are the second
best. All approaches are evaluated following the standard procedure in Wang et
al. (2020). *Model re-evaluated using the standard procedure for a fair
comparison. ‘–’ denotes that numbers are not reported in the corresponding
paper. Note that the publicly released models of ONCE and FSOD are based on
ResNet-50; we include our CoRPNs based on ResNet-50 as well for a fair
comparison. CoRPNs consistently outperform state of the art in almost all
settings, with substantial improvements especially in the very few-shot
regime. Our strategy is also effective regardless of classifier choice.

|  | Novel Set 1 | Novel Set 2 | Novel Set 3
---|---|---|---|---
| Method | shot=1 | 2 | 3 | 5 | 10 | shot=1 | 2 | 3 | 5 | 10 | shot=1 | 2 | 3 | 5 | 10
Ours | CoRPNs w/ fc (Ours) |  40.8 | 44.8 | 45.7 | 53.1 | 54.8 | 20.4 | 29.2 | 36.3 | 36.5 | 41.5 | 29.4 | 40.4 | 44.7 | 51.7 | _49.9_
CoRPNs w/ cos (Ours) |  44.4 | 38.5 | _46.4_ | 54.1 | 55.7 | 25.7 | 29.5 | _37.3_ | 36.2 | 41.3 | 35.8 | 41.8 | _44.6_ | _51.6_ | 49.6
Main baselines | TFA w/ fc (baseline) (Wang et al., 2020) |  36.8 | 29.1 | 43.6 | 55.7 | 57.0 | 18.2 | 29.0 | 33.4 | 35.5 | 39.0 | 27.7 | 33.6 | 42.5 | 48.7 | 50.2
TFA w/ cos (baseline) (Wang et al., 2020) |  39.8 | 36.1 | 44.7 | 55.7 | 56.0 | 23.5 | 26.9 | 34.1 | 35.1 | 39.1 | 30.8 | 34.8 | 42.8 | 49.5 | 49.8
Other baselines | FRCN+ft-full (Wang et al., 2020) |  15.2 | 20.3 | 29.0 | 40.1 | 45.5 | 13.4 | 20.6 | 28.6 | 32.4 | 38.8 | 19.6 | 20.8 | 28.7 | 42.2 | 42.1
Meta R-CNN (Yan et al., 2019) |  19.9 | 25.5 | 35.0 | 45.7 | 51.5 | 10.4 | 19.4 | 29.6 | 34.8 | 45.4 | 14.3 | 18.2 | 27.5 | 41.2 | 48.1
CoAE* (Hsieh et al., 2019) |  12.7 | 14.6 | 14.8 | 18.2 | 21.7 | 4.4 | 11.3 | 20.5 | 18.0 | 19.0 | 6.3 | 7.6 | 9.5 | 15.0 | 19.0
MPSR (Wu et al., 2020) |   _41.7_ | _43.1_ | 51.4 | 55.2 | 61.8 | _24.4_ | 29.5 | 39.2 | 39.9 | 47.8 | _35.6_ | _40.6_ | 42.3 | 48.0 | 49.7
FsDetView (Xiao & Marlet, 2020) |  24.2 | 35.3 | 42.2 | 49.1 | _57.4_ | 21.6 | 24.6 | 31.9 | _37.0_ | _45.7_ | 21.2 | 30.0 | 37.2 | 43.8 | 49.6

Table 2: Few-shot detection performance (AP50) on PASCAL VOC novel classes
under three base/novel splits. All models are based on Faster R-CNN with a
ResNet-101 backbone. Results in red are the best, and results in _blue_ are
the second best. We follow the standard evaluation procedure in Wang et al.
(2020). *Model re-evaluated under the standard procedure. CoRPNs outperform
all the baselines in the very low shots, and achieve comparable performance in
the higher shots.

|  |  | 1-shot finetuned | 2-shot finetuned | 3-shot finetuned
---|---|---|---|---|---
| Method | Backbone |  AP | AP50 | AP75 | AP | AP50 | AP75 | AP | AP50 | AP75
Ours | CoRPNs w/ cos | ResNet-101 |  34.1 | 55.1 | 36.5 | 34.7 | 55.3 | 37.3 | 34.8 | 55.2 | 37.6
CoRPNs w/ cos | ResNet-50 |  32.1 | 52.9 | 34.4 | 32.7 | 52.9 | 35.5 | 32.6 | 52.4 | 35.4
Main baseline | TFA w/ cos (Wang et al., 2020) | ResNet-101 |  34.1 | 54.7 | 36.4 | 34.7 | 55.1 | 37.6 | 34.7 | 54.8 | 37.9
Other baselines | MPSR (Wu et al., 2020) | ResNet-101 |  12.1 | 17.1 | 14.2 | 14.4 | 20.7 | 16.9 | 15.8 | 23.3 | 18.3
FsDetView (Xiao & Marlet, 2020) | ResNet-101 |  1.9 | 5.7 | 0.8 | 2.7 | 8.2 | 0.9 | 3.9 | 10.8 | 2.0
FSOD* (Fan et al., 2020) | ResNet-50 |  11.9 | 20.3 | 12.5 | 15.6 | 24.4 | 17.2 | 17.4 | 27.3 | 19.0
|  |  | 5-shot finetuned | 10-shot finetuned | 30-shot finetuned
| Method | Backbone |  AP | AP50 | AP75 | AP | AP50 | AP75 | AP | AP50 | AP75
Ours | CoRPNs w/ cos | ResNet-101 |  34.7 | 54.8 | 37.5 | 34.6 | 54.5 | 38.2 | 35.8 | 55.4 | 39.4
CoRPNs w/ cos | ResNet-50 |  32.3 | 51.6 | 34.9 | 32.7 | 51.9 | 36.0 | 33.5 | 52.7 | 37.0
Main baseline | TFA w/ cos (Wang et al., 2020) | ResNet-101 |  34.7 | 54.4 | 37.6 | 35.0 | 55.0 | 38.3 | 35.8 | 55.5 | 39.4
Other baselines | MPSR (Wu et al., 2020) | ResNet-101 |  17.4 | 25.9 | 19.8 | 19.5 | 29.5 | 21.9 | 21.0 | 32.4 | 23.4
FsDetView (Xiao & Marlet, 2020) | ResNet-101 |  5.3 | 14.2 | 2.8 | 6.4 | 15.9 | 4.1 | 9.0 | 20.6 | 6.7
FSOD* (Fan et al., 2020) | ResNet-50 |  16.7 | 26.2 | 18.3 | 18.9 | 29.3 | 20.7 | 18.8 | 29.4 | 20.1

Table 3: Detection performance on COCO base classes after fine-tuning with
k-shot novel classes instances. *Model re-evaluated under the standard
procedure (Wang et al., 2020). Our CoRPNs and TFA (Wang et al., 2020) maintain
good performance on base classes, whereas MPSR (Wu et al., 2020) and FsDetView
(Xiao & Marlet, 2020) suffer from severe catastrophic forgetting.

Ablation Studies. We conduct a series of ablations to evaluate the
contribution of each component and different design choices. Specifically, we
show that (1) with our novel loss terms, CoRPNs outperform naive RPN
ensembles; (2) CoRPNs outperform an existing cosine loss based diversity
method; (3) our cooperation loss is helpful; (4) the number of RPN’s matters.

CoRPNs vs. Naive RPN Ensembles. We compare CoRPNs with an ensemble of the same
number of RPN’s trained separately, each with a different initialization. At
the fine-tuning phase, we apply the same RPN selection mechanism to both
approaches. Table 4 shows that novel AP50 of CoRPNs largely outperforms naive
ensembles. This suggests that pure redundancy does not lead to improvements,
confirming that our loss terms enforce diversity and cooperation. In addition,
there are $N$ groups of parameters in naive ensembles, because each model is
trained separately. Hence, the number of parameters and training time of our
CoRPNs are $N$ times less than naive ensembles.

CoRPNs vs. Cosine Loss Diversity. Results in Table 5 confirm that in this
context, our diversity loss – the log-determinant loss – outperforms another
diversity loss introduced in Dvornik et al. (2019). Dvornik et al. (2019)
encourage diversity among classifiers by enlarging the cosine distance in
classifier outputs. To compare with their method, we replace our diversity
loss term by a pairwise cosine similarity loss among RPN’s (if there are $N$
RPN’s, the pairwise cosine similarity loss is an average over all
${N(N-1)}/{2}$ pairs).

Avoiding False Negatives. In our cooperation loss $\mathcal{L}_{coop}$ (which
pushes all RPN’s to agree on certain degree for foreground boxes) has a
threshold hyperparameter $\phi$. Table 6 reports results under different
thresholds on PASCAL VOC novel split 3 fine-tuned on 1-shot novel instance. In
addition to AP50, we report the average number of false negative foreground
boxes (‘Avg # FN’) during fine-tuning and the average number of foreground
samples (‘Avg # FG’) after non-maximum suppression (NMS). The table shows that
the cooperation loss term causes the number of false negatives (i.e. high IOU
boxes not presented to the classifier at fine-tuning time) to decrease.
Furthermore, the average number of foreground samples after NMS increases.

Method | AP50 | Method | AP50
---|---|---|---
2 RPN’s Naive | 24.6 | 5 RPN’s Naive | 23.7
2 RPN’s Ours | 35.8 | 5 RPN’s Ours | 34.8

Table 4: CoRPNs significantly outperform naive ensembles of RPN’s. The table
shows novel class AP50 after phase 2 of our (resp. naive) RPN ensembles with 2
or 5 RPN’s, all trained and evaluated under PASCAL VOC novel split 3, shot 1,
using the same parameter settings.

Method | AP50
---|---
2 RPN’s, Div and Coop (Dvornik et al., 2019) | 32.4
2 RPN’s, CoRPNs (Ours) | 35.8

Table 5: Our diversity enforcing term – the log-determinant loss – offers
improvements over the pairwise cosine similarity based diversity loss in
Dvornik et al. (2019). The table shows novel class AP50 of both models,
trained and evaluated under PASCAL VOC novel split 3, shot 1, using the same
parameter settings.

Method | AP50 | Avg # FN ($\downarrow$) | Avg # FG ($\uparrow$)
---|---|---|---
TFA (Wang et al., 2020) | 28.9 | 3.1 | 18.6
CoRPNs w/ |  $\phi$ = 0.1 | 29.5 | 2.4 | 22.3
$\phi$ = 0.3 | 31.5 | 3.0 | 19.5
$\phi$ = 0.5 | 32.2 | 2.5 | 19.3
$\phi$ = 0.7 | 26.8 | 1.3 | 21.3
$\phi$ = 0.9 | 31.7 | 0.8 | 20.0

Table 6: Our threshold $\phi$ controls the average number of false-negative
foreground boxes and the number of foreground samples. The table shows the
novel class AP50, the average number of false-negative foreground boxes (with
threshold = 0.5), and the average number of foreground boxes after NMS (higher
is better). The last two numbers are calculated during the fine-tuning phase
when RPN’s are frozen. All models are trained and evaluated under PASCAL VOC
novel split 3, shot 1. At phase 2, different from other experiments, we fine-
tune with novel classes only, so the last two columns capture each model’s
ability to detect novel class boxes.

The Number of RPN’s. As expected, increasing the number of RPN’s produces
improvements up to a point, and then either the number of false positives or
variance in the RPN parameter estimates leads to a decline in performance
(Figure 4). This figure plots the base AP50 (after phase 1) and novel AP50
under PASCAL VOC novel splits 1 and 3, shot 1. Note that the optimal number of
RPN’s differs over different splits (and assumably datasets). As shown in
Figure 4, the optimal number is different between PASCAL VOC split 1 (left two
figures) and split 3 (right two figures).

Figure 4: Effect of the number of RPN’s on novel and base AP50, under PASCAL
VOC splits 1 and 3, both with shot 1 and fine-tuned on base + novel classes.
Note that the horizontal scale is not linear. Though there is considerable
variance, the graphs suggest that at small numbers of RPN’s, novel AP50 (blue)
is somewhat depressed, likely because some high IOU boxes are missed. As the
number of RPN’s increases, there is an improvement, but when there are a large
number of RPN’s, the rate at which false positive boxes passes the RPN system
increases and the gain is lost. The effect might be present for base classes
as well (orange), but is smaller (the vertical scale is different).

##  5 Conclusion

A substantial improvement in few-shot performance can be obtained by
engineering a system of RPN’s to ensure that high IOU boxes for few-shot
training images almost always pass the system of RPN’s. Our method achieves a
new state of the art on widely-used benchmarks and outperforms the current
state of the art by a large margin in the very few-shot regime. This is
because, as ablation experiments indicate, proposal neglect is a real effect.
We engineered our ensemble of RPN’s by using a diversity loss and a
cooperation loss, which gave us some control of the false negative rate. We
showed that controlling proposal neglect is an essential part of building a
strong few-shot object detector by showing that the state-of-the-art few-shot
detector could be improved in this way. We do not claim that our method is the
best way to control proposal neglect. For example, our $\phi$ threshold in the
cooperation loss may cause false positives to be correlated. We plan to
investigate methods that can offer more delicate control of the false negative
rate. Furthermore, it is very likely that proposal neglect applies to one-
stage detectors like YOLO (Redmon & Farhadi, 2018), and future work will
investigate this.

## References

  * Bochkovskiy et al. (2020) Alexey Bochkovskiy, Chien-Yao Wang, and Hong-Yuan Mark Liao.  YOLOv4: Optimal speed and accuracy of object detection.  _arXiv preprint arXiv:2004.10934_ , 2020.
  * Chen et al. (2018) Hao Chen, Yali Wang, Guoyou Wang, and Yu Qiao.  LSTD: A low-shot transfer detector for object detection.  In _AAAI_ , 2018.
  * Dai et al. (2017) Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei.  Deformable convolutional networks.  In _ICCV_ , 2017.
  * Dvornik et al. (2019) Nikita Dvornik, Cordelia Schmid, and Julien Mairal.  Diversity with cooperation: Ensemble methods for few-shot classification.  In _ICCV_ , 2019.
  * Endres & Hoiem (2010) Ian Endres and Derek Hoiem.  Category independent object proposals.  In _ECCV_ , 2010.
  * Everingham et al. (2010) Mark Everingham, Luc Van Gool, Christopher K. I. Williams, John Winn, and Andrew Zisserman.  The PASCAL visual object classes (VOC) challenge.  _IJCV_ , 88(2):303–338, 2010.
  * Fan et al. (2020) Qi Fan, Wei Zhuo, Chi-Keung Tang, and Yu-Wing Tai.  Few-shot object detection with attention-rpn and multi-relation detector.  In _CVPR_ , 2020.
  * Fei-Fei et al. (2006) Li Fei-Fei, Rob Fergus, and Pietro Perona.  One-shot learning of object categories.  _IEEE TPAMI_ , 28(4):594–611, 2006.
  * Girshick (2015) Ross Girshick.  Fast R-CNN.  In _ICCV_ , 2015.
  * Girshick et al. (2014) Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In _CVPR_ , 2014.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Spatial pyramid pooling in deep convolutional networks for visual recognition.  _IEEE TPAMI_ , 37(9):1904–1916, 2015.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , 2016.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask R-CNN.  In _ICCV_ , 2017.
  * Hsieh et al. (2019) Ting-I Hsieh, Yi-Chen Lo, Hwann-Tzong Chen, and Tyng-Luh Liu.  One-shot object detection with co-attention and co-excitation.  In _NeurIPS_ , 2019.
  * Kang et al. (2019) Bingyi Kang, Zhuang Liu, Xin Wang, Fisher Yu, Jiashi Feng, and Trevor Darrell.  Few-shot object detection via feature reweighting.  In _ICCV_ , 2019.
  * Law & Deng (2018) Hei Law and Jia Deng.  Cornernet: Detecting objects as paired keypoints.  In _ECCV_ , 2018.
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft COCO: Common objects in context.  In _ECCV_ , 2014.
  * Lin et al. (2017) Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In _CVPR_ , 2017.
  * Liu et al. (2016) Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C. Berg.  SSD: Single shot multibox detector.  In _ECCV_ , 2016.
  * Osokin et al. (2020) Anton Osokin, Denis Sumin, and Vasily Lomakin.  OS2D: One-stage one-shot object detection by matching anchor features.  In _ECCV_ , 2020.
  * Pérez-Rúa et al. (2020) Juan-Manuel Pérez-Rúa, Xiatian Zhu, Timothy Hospedales, and Tao Xiang.  Incremental few-shot object detection.  In _CVPR_ , 2020.
  * Redmon & Farhadi (2017) Joseph Redmon and Ali Farhadi.  YOLO9000: better, faster, stronger.  In _CVPR_ , 2017.
  * Redmon & Farhadi (2018) Joseph Redmon and Ali Farhadi.  YOLOv3: An incremental improvement.  _arXiv preprint arXiv:1804.02767_ , 2018.
  * Redmon et al. (2016) Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In _CVPR_ , 2016.
  * Ren et al. (2015) Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster R-CNN: Towards real-time object detection with region proposal networks.  In _NeurIPS_ , 2015.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  _IJCV_ , 115(3):211–252, 2015.
  * Schwartz et al. (2019) Eli Schwartz, Leonid Karlinsky, Joseph Shtok, Sivan Harary, Mattias Marder, Sharathchandra Pankanti, Rogerio Feris, Abhishek Kumar, Raja Giries, and Alex M. Bronstein.  RepMet: Representative-based metric learning for classification and one-shot object detection.  In _CVPR_ , 2019.
  * Thrun (1998) Sebastian Thrun.  Lifelong learning algorithms.  _Learning to learn_ , 8:181–209, 1998.
  * van de Sande et al. (2011) Koen van de Sande, Jasper Uijlings, Theo Gevers, and Arnold Smeulders.  Segmentation as selective search for object recognition.  In _ICCV_ , 2011.
  * Wang et al. (2020) Xin Wang, Thomas E. Huang, Trevor Darrell, Joseph E Gonzalez, and Fisher Yu.  Frustratingly simple few-shot object detection.  In _ICML_ , 2020.
  * Wang et al. (2019) Yu-Xiong Wang, Deva Ramanan, and Martial Hebert.  Meta-learning to detect rare objects.  In _ICCV_ , 2019.
  * Wu et al. (2020) Jiaxi Wu, Songtao Liu, Di Huang, and Yunhong Wang.  Multi-scale positive sample refinement for few-shot object detection.  In _ECCV_ , 2020.
  * Xiao & Marlet (2020) Yang Xiao and Renaud Marlet.  Few-shot object detection and viewpoint estimation for objects in the wild.  In _ECCV_ , 2020.
  * Yan et al. (2019) Xiaopeng Yan, Ziliang Chen, Anni Xu, Xiaoxi Wang, Xiaodan Liang, and Liang Lin.  Meta R-CNN: Towards general solver for instance-level low-shot learning.  In _ICCV_ , 2019.
  * Yang et al. (2020) Ze Yang, Yali Wang, Xianyu Chen, Jianzhuang Liu, and Yu Qiao.  Context-transformer: Tackling object confusion for few-shot detection.  In _AAAI_ , 2020.
  * Zhou et al. (2019) Xingyi Zhou, Jiacheng Zhuo, and Philipp Krahenbuhl.  Bottom-up object detection by grouping extreme and center points.  In _CVPR_ , 2019.


# Graded linearity of Stanley-Reisner ring of broken circuit complexes

Mohammad Reza Rahmati, Gerardo Flores<EMAIL_ADDRESS>(M. Reza Rahmati),
<EMAIL_ADDRESS>(G. Flores)

###### Abstract.

This paper introduces two new notions of graded linear resolution and graded
linear quotients, which generalize the concepts of linear resolution property
and linear quotient for modules over the polynomial ring
$A=k[x_{1},\dots,x_{n}]$. Besides, we compare graded linearity with
componentwise linearity in general. For modules minimally generated by a
regular sequence in a maximal ideal of $A$, we show that graded linear
quotients imply graded linear resolution property for the colon ideals. On the
other hand, we provide specific characterizations of graded linear resolution
property for the Stanley-Reisner ring of broken circuit complexes and
generalize several results of [32] on the decomposition of matroids into the
direct sum of uniform matroids. Specifically, we show that the matroid can be
stratified such that each strata has a decomposition into uniform matroids. We
also present analogs of our results for the Orlik-Terao ideal of hyperplane
arrangements which are translations of the corresponding results on matroids.

###### 2010 Mathematics Subject Classification:

##  1\. Introduction

We consider finitely generated graded modules over the polynomial ring,
$A=k[x_{1},\dots,x_{n}]$ where $k$ is an infinite field. One of the essential
facts about the finitely generated rings over $A$ is the Hilbert syzygy
theorem [23], stating that any such module has a graded minimal $A$-resolution
by free modules as

(1.1) $\dots\longrightarrow\bigoplus_{j}A(-j)^{\beta_{p,j}}\longrightarrow\ \
\dots\ \ \longrightarrow\bigoplus_{j}A(-j)^{\beta_{0j}}\longrightarrow
M\longrightarrow 0,$

where the graded Betti numbers $\beta_{ij}$ of the graded module $M$ are the
exponents appearing in a graded minimal free resolution. Another way to
express it is $\beta_{ij}=\dim_{k}Tor_{i}(M,k)_{j}$. One can arrange the Betti
numbers in a table by assigning $\beta_{i,i+j}$ in the $(i,j)$ entry, called
the Betti table. The graded $A$-module $M$ is said to have a linear resolution
if its non-zero Betti numbers in minimal $A$-resolution appear just in one
line of entries, successively in the table. In special cases, one can
characterize this property by the combinatorial data associated with these
modules. We generalize this concept by mentioning finitely generated graded
modules where their non-zero Betti numbers appear successively in several
lines. Then, an important question is the combinatorial identification of the
above property. A parallel concept is that of having linear quotients. This
notion is defined in terms of the colon ideals of the module $M$. It is well
known that having a linear quotient implies the linear resolution property for
colon ideals, [17].

In this text we also generalize the concept of quotient linearity, and we
define the graded linear quotient property. We compare it with graded linear
property and prove the analogous theorem in the graded case. Our proof uses a
standard inductive technique of passing to the long exact Tor-sequence
associated with short exact sequence on colon ideals of $M$. This
generalization aims to study the notion of component-wise linearity, which
plays a crucial role in commutative algebra. We show that graded linearity is
a weaker property than component-wise linearity.

For Cohen-Macaulay graded ideals $I$ in $A$, the property of having a linear
resolution is characterized by the combinatorial data of the ideal such as its
Hilbert polynomial. In this case, the Hilbert polynomial can be summarized in
a single binomial coefficient. An interesting example is the Stanley-Reisner
ideal $I_{<}(X)$ of the Broken circuit complex of matroid $X$. The Stanley-
Reisner ideal $I_{<}(X)$ is generated by monomials on the broken circuits of
$X$. The broken circuit complex of an ordered matroid $X$ is a Shellable
complex where it shows the Stanley-Reisner ring $A/I_{<}(X)$ is Cohen-Macaulay
[23]. The linearity property, in this case, can be translated into a
combinatorial decomposition of the matroid in terms of uniform matroids, [see
[32]] in the form

(1.2) $X=U_{s,n-r+s}\bigoplus U_{r-s,r-s},$

where matroid $U_{p,n}$ is the uniform matroid on $n$-element, whose
independent sets are subsets having at most $p$ element. The proof of the
Theorem uses the assertions of an external bound for the $f$-vectors of a
$r-1$ dimensional shellable complex on the vector set $S$ of size $|S|=n$ in
the form

(1.3) $f_{k-1}\geq\sum_{i=0}^{s-1}{n-r+i-1\choose i}{r-i\choose k-i},\qquad
k=0,\dots,r$

when all $s$-element subsets of $S$ belong to $\Delta$. The decomposition in
(1.2) holds when the equality holds in (1.3), [6].

A significant attempt in this work is to find analogous characterizations of
graded linearity for these ideals. One also asks how the decomposition of the
matroid can be extended. In other words, we investigate what the corresponding
operation in the category of matroids is. To answer this question, we
introduce the notion of stratification (filtration) of matroids by
submatroids. Stratification of a matroid $X$ is a decreasing filtration
sequence,

(1.4) $X=X_{0}\supset X_{1}\supset\dots\supset X_{d},\qquad
S_{j}=X_{j}\smallsetminus X_{j+1}$

by submatroids $X_{j}$, where we call $X_{j}\smallsetminus X_{j+1}$ the $j$-th
strata of the stratification. If $X$ is a rank $r$ loopless matroid on $[n]$
we establish a new inequality

(1.5) $I_{j-1}\geq\sum_{i=0}^{c-1}\sum_{l=1}^{d}c_{l}^{(S)}{n-r+l-1\choose
l}{r-i\choose j-i}$

generalizing (1.3), and the equality holds if and only if the ideal $I_{<}(X)$
has graded linear resolution. In that case, we first establish that the
Hilbert function of $I_{<}(X)$ has the form

(1.6) $H(\frac{A}{I_{<}(X)},s)=c_{0}{s+q-1\choose s}+c_{1}{s+q-2\choose
s}+\cdots+c_{d-1}{s+q-d\choose s}$

for some $d$. The coefficients $c_{i}=c_{i}(I_{<}(X))$ can be easily
calculated, (called Hilbert coefficient of $I_{<}(X)$). In this case there
exists a stratification as in (1.4) such that

(1.7) $S_{j}=U_{r_{j}-s_{j},r_{j}-s_{j}}\bigoplus U_{s_{j},n_{j}-r_{j}+s_{j}}$

where $s_{j}\leq r_{j}$. We have $n=\Sigma_{j}n_{j},\ r=\Sigma_{j}r_{j}$.

To an arrangement of hyperplanes in a vector space, one can associate a
matroid, where the independent sets correspond to the independent hyperplanes.
In this way, some properties for matroids can be translated into the language
of hyperplane arrangements. The properties above can be applied to certain
graded ideals associated with a hyperplane arrangement. In particular, they
apply to the Orlik-Solomon ideal and also the Orlik-Terao ideal of the
arrangements. As an application, we provide similar assertions for graded
linearity of the Orlik-Terao ideal of hyperplane arrangements, which
translates the above results to this area. We discuss the Koszul property of
the Stanley-Reisner ring of the broken circuit complex. We define an extension
of Koszulness, namely graded Koszulness, and characterize this concept via the
decomposition of the associated matroid.

Another important concept is the entire intersection property of Orlik-Solomon
algebra and the Orlik-Terao ideal of hyperplane arrangements, [9], [32], [15],
[27]. There appears several characterizations of this property in [32]
concerning the linearity of the corresponding ideals. We express the
generalizations of these theorems to the graded linearity as a natural
application to our results. We also present an application to graphs and their
cycle matroids. Specifically, we discuss the entire intersection property of
the facet ideal of $r$-cyclic graph $G_{n,r}$. We provide an alternative for
the proof of the Cohen-Macaulayness of the facet ideal of $G_{n,r}$. The
properties of the facet ideal $I_{F}(\Delta)$ has been discussed in [4], [14],
[24], [31], [5]. Our method gives a simple proof of the Cohen-Macaulayness of
the facet ideal of $G_{n,r}$. This property was proved in [4] by direct
methods. Our proof is based on the criteria characterizing the complete
intersection properties on the cycle matroid of a graph.

###  1.1. Related works

This work is based on the results of [19, 32] about several combinatorial
characterizations of linear resolution property for the Stanley-Reisner ring
of broken circuit complexes. The main theorem that is proven in that work is
that of characterization for the decomposition of the broken circuit complex
of a matroid when the associated Stanley-Reiner ring has a linear resolution.
The authors also express the analogs theorems on the arrangement of
hyperplanes. The results identify the linear resolution property for the
Orlik-Solomon ideal of the arrangement and the complete intersection and
Koszul property of their Orlik-Solomon and Orlik-Terao ideals.

On the other hand, a comprehensive study of the combinatorics of the broken
circuits of matroids is done [6]. In this regard, we have generalized a
fundamental argument of [6] on the decomposition of Matroids based on a lower
bound for the components of the $f$-vectors of shellable complexes. The lower
bound in its extreme case implies a decomposition of the complex of
independent subsets of a matroid into the direct sum of two uniform matroids;
see also [7]. Our approach in generalizing the above decomposition is through
the stratification of a matroid by its submatroids. The concept has been
explored in [10]; however, it has not worked out very much in the literature.
Therefore, we have explained it through basic operations on matroids [10, 33,
34, 35]. The stratification describes a decreasing filtration by submatroids
and results in a kind of graded decomposition on the matroid, i.e.,
decomposition on each stratum.

A comprehensive exposition on Koszul algebras and the related conjectures is
presented in [9]. The characterization of this property for Orlik-Terao Ideals
of arrangement of hyperplanes can be considered as a special case of having
general linear resolution mentioned above. In this case, the Orlik-Terao ideal
has a 2-linear resolution, [32]. In this regard, the combinatorial
identification of the Koszul property for algebras associated with matroids
and hyperplane arrangements is one of the significant and crucial challenging
problems in this area [15, 9, 29, 27, 28].

###  1.2. Organization of text

Section 2 contains the basic definitions and theorems that we use throughout
the text. We have divided that into six subsections containing different
notions in combinatorial algebra. Sections 3 and 4 consists of our main
results and contributions. Specifically, Section 4 consists of the
applications of the results in Section 3 to the hyperplane arrangements. In
the end, we also prove a complete intersection property for the broken circuit
complex of $r$-cyclic graph. Finally, in Section sec:conc, we present some
remarks and conclusions.

##  2\. Preliminaries

###  2.1. Linear resolutions

Let $A=K[x_{1},\dots,x_{n}]$ be the polynomial ring over an infinite field $k$
and $\mathfrak{m}=(x_{1},\dots,x_{n})$ the maximal ideal. A finitely generated
graded $A$-module $M$ is said to have $s$-linear resolution if the graded
minimal free resolution of $M$ is of the form

(2.1) $0\longrightarrow A(-s-p)^{\beta_{p}}\longrightarrow\ \dots\
\longrightarrow A(-s-1)^{\beta_{1}}\longrightarrow
A(-s)^{\beta_{0}}\longrightarrow M\longrightarrow 0.$

In other words $M$ has $s$-linear resolution if $\beta_{i,i+j}=0$ for $j\neq
s$; a relevant notion is that of $s$-linear quotient (see [17, 3]).

Next, we give some definitions and nomenclature to set the conditions of
Theorem 2.1 presented in the following. First, let assume that $<$ is a
monomial order on $A$. Write a non-zero polynomial in $A$ as,
$f=\sum_{v}a_{v}v$, where $v\in A$ is a monomial. The initial monomial of $f$
w.r.t. $<$ is the biggest monomial w.r.t. $<$ among the monomials belonging to
$supp(f)$. We write $in_{<}(f)$ for the initial monomial of $f$ with respect
to $<$. The leading coefficient of $f$ is the coefficient of $in_{<}(f)$. If
$I$ is a nonzero ideal of $A$, the initial ideal of $I$ w.r.t $<$ is the
monomial ideal of $A$, which is generated by $\\{in_{<}(f):f\in I\\}$. We
write $in_{<}(I)$ for the initial ideal of $I$. Thus, we are ready to present
the following theorem, which characterizes the linear resolution property.

######  Theorem 2.1 ([32]).

Assume $I=\bigoplus_{k}I_{k}$ is a graded Cohen-Macaulay ideal in $A$ of
codimension $q$ and $s$ is the smallest index that $I_{s}\neq 0$. The
followings are equivalent

  * •

$I$ has $s$-linear resolution.

  * •

If $a_{1},\dots,a_{n-q}$ is a maximal $(A/I)$-regular sequence of linear forms
in $A$. we have $\overline{I}=\overline{\mathfrak{m}^{s}}$ in
$A/(a_{1},\dots,a_{n-q})$.

  * •

The Hilbert function of $I$ has the form $H(I,s)={s+q-1\choose s}$.

  * •

Suppose $<$ is a monomial order on $A$. If $\ in_{<}(I)\ $ (the initial ideal
of $I$) is Cohen-Macaulay, then $\ in_{<}(I)\ $ has $s$-linear resolution.

Now let us suppose that $I$ is a graded ideal of $A$ and $in_{<}(I)$ is Cohen-
Macaulay, then from the above Theorem, it follows that $I$ has linear
resolution if and only if $in_{<}(I)$ has a linear resolution, cf. [32] loc.
Cit. A relevant definition is that of linear quotients as follows.

######  Definition 2.2.

Say $M$ has linear quotient, if there exists a minimal system of generators
$a_{1},\dots,a_{m}$ of $M$ such that the colon ideals

(2.2) $J_{l}=(a_{1},\dots,a_{l-1}):a_{l}$

are generated by linear forms of all $l$.

On the other hand, the following result relative to linear quotients is also
well known.

######  Theorem 2.3.

([17] prop. 8.2.1) Suppose that $I$ is a graded ideal of $A$ generated in
degree $s$. If $I$ has linear quotients, then it has a $s$-linear resolution.

Another important concept related to linearity is the componentwise linearity,
[17]. For that, we consider the following construction. Assume
$M=\bigoplus_{j}M_{j}$ is a finitely generated graded $A$-module and let
$(\mathfrak{F},d)=\left((\mathfrak{F}_{n}),d_{n}:\mathfrak{F}_{n}\to\mathfrak{F}_{n-1}\right)$
be the minimal graded free resolution of $M$. Define subcomplexes

(2.3) $\mathfrak{F}^{(i)}:=\big{(}\ \mathfrak{m}^{i-n}\mathfrak{F}_{n},\
d_{n}\ \big{)}.$

The linear part of $\mathfrak{F}$ is the complex

(2.4) $\mathfrak{F}^{\text{lin}}=\big{(}\
\bigoplus_{i}\mathfrak{F}^{(i)}/\mathfrak{F}^{(i+1)},\ gr^{(i)}(d)\ \big{)}$

Also, we have an important definition and theorem regarding the graded module
$M=\oplus_{j}M_{j}$. These are presented next.

######  Definition 2.4.

The graded module $M=\oplus_{j}M_{j}$ is said to be componentwise linear if
$M_{\langle s\rangle}$ has linear resolution for all $s$, where by definition
$M_{\langle s\rangle}$ is the submodule generated by $M_{s}$.

######  Theorem 2.5 ([19], [9]).

The followings are equivalent

  * •

$M$ is componentwise linear.

  * •

$M_{\langle q\rangle}$ has a linear resolution for every $q$.

  * •

$\mathfrak{F}^{\text{lin}}$ is acyclic.

One can choose a homogeneous basis for the $A$-graded modules
$\mathfrak{F}^{(i)}$, (for all $i$) so that matrices present the differentials
with homogeneous entries. Then, the differential of the complex
$\mathfrak{F}^{\text{lin}}$ is obtained by killing all the monomials of
degrees bigger than one in the entries. The resulting matrix is called the
linearization of differentials.

###  2.2. Broken circuit complexes

One can consider the above properties for certain ideals constructed from
combinatorial data of a matroid. Let $(X,<)$ be an ordered simple matroid of
rank $r$ on $[n]$. The minimal dependent subsets of $X$ are called circuits.
Denote by $BC_{<}(X)$ the broken circuit complex of $X$, i.e., the collection
of all subsets of $M$ not containing any broken circuit. It is known that,
$BC_{<}(X)$ is an $(r-1)$-dimensional shellable complex. The Stanley-Reisner
ideal of $BC_{<}(X)$ denoted $I_{<}(X)$ is the ideal generated by all
monomials on broken circuits. We denote a broken circuit by
$bc_{<}(C)=C\smallsetminus min_{<}(C)$, [32]. By definition,

(2.5) $I_{<}(X)=\big{\langle}x_{bc_{<}(C)}:=\prod_{j\in
bc_{<}(C)}x_{j}\big{\rangle}.$

The shellability of $BC_{<}(X)$ implies that $A/I_{<}(X)$ is Cohen-Macaulay.
Thus, the following theorem characterizes the linear resolution of the ideal
$I_{<}(X)$.

######  Theorem 2.6 ([32]).

The following are equivalent

  * •

$I_{<}(X)$ has $s$-linear resolution.

  * •

$X=U_{s,n-r+s}\bigoplus U_{r-s,r-s}$.

  * •

All powers of $I_{<}(X)$ have linear resolutions.

The matroid $U_{p,n}$ is the uniform matroid on the $n$-element, whose
independent sets are subsets having at most $p$ elements. $U_{p,n}$ has rank
$p$ and its circuits have $p+1$ elements. In particular, $U_{n,n}$ has no
dependent sets and is called free. The proof of the Theorem 2.6 uses [theorem
7.5.2 of reference [6]] on an external bound for the $f$-vectors; please refer
to [32]. For the sake of completeness, we briefly recall this fact from [6] in
the following theorem.

######  Theorem 2.7 ([6]).

Let us consider the following.

  * (1)

Let $\Delta$ be an $r-1$ dimensional shellable complex on the vector set $S$
of size $|S|=n$. If for some $s\in\mathbb{N}$, all $s$-element subsets of $S$
belong to $\Delta$, then the inequality

(2.6) $f_{k-1}\geq\sum_{i=0}^{s-1}{n-r+i-1\choose i}{r-i\choose k-i},\qquad
k=0,\dots,r$

holds for the $f$-vector.

  * (2)

Assume $\Delta=In(X)$ is the complex of independent subsets of a loopless
matroid. Then, inequality (2.6) holds for $f_{k}$ replaced with the $I_{k}$,
the number of independent $k$-element subsets of $X$. The equality holds if
and only if

(2.7) $X=U_{s,n-r+s}\bigoplus U_{r-s,r-s},\qquad s+1=\min\\{|C|\ ;C\ \text{is
a circuit}\\}.$

We sketch some explanations related to the above theorem inspired from [6].
The condition that all $s$-element subsets of $S$ are in $\Delta$, implies
that $f_{k}={n\choose k},\ k=0,1,2,3,\dots,s$. By using formal combinatorial
identities,

(2.8) $h_{k}=\sum_{i=0}^{k}(-1)^{i+k}{r-i\choose k-i}{n\choose
i}={n-r+k-1\choose k},\qquad k\leq s.$

Therefore, the inequality in (2.6) follows by singling out the first $s+1$
terms in

(2.9) $f_{k}=\sum_{i=0}^{k}h_{i}{r-i\choose k-i},\qquad k=1,\dots,r.$

In case $\Delta=In(X)$, let $b(X)=I_{r}$, then $b(X)={n-r+s\choose s}$ is the
number of bases of $X$. The $h$-vector is given by

(2.10) $\underline{\textbf{h}}=\left(\ 1,n-r,\ \dots\ ,{n-r+s-1\choose s}\
\right)$

and the Tutte polynomial of $X$ is

(2.11) $T_{X}(x,1)=h_{\Delta}(x)=x^{r}+(n-r)x^{r-1}+\cdots+{n-r+s-2\choose
s-1}x^{r-s}.$

The form of the Tutte polynomial shows that, $X$ has exactly $n-r+s$ coloops.
This forces $X=N\oplus U_{r-s,r-s}$ where $N$ is a matroid of rank $s$ on
$n-r+s$ points. Now $b(N)=b(X)={n-r+s\choose s}$. This forces that
$N=U_{s,n-r+s}$. The equality in (2.6) holds, if $h_{c}=h_{c+1}=\dots=0$, cf.
[6] loc. cit.

###  2.3. Complete intersection property

In Section 4, we need to decide whether a graded ideal is a complete
intersection. We recall some definitions from commutative algebra. For a
commutative Noetherian local ring $A$, the depth of $A$ (the maximum length of
a regular sequence in the maximal ideal of $A$), is at most the Krull
dimension of $A$. The ring $A$ is called Cohen–Macaulay if its depth is equal
to its dimension. A regular sequence is a sequence $a_{1},\dots a_{n}$ of
elements of $\mathfrak{m}$ such that, for all $i$, the element $a_{i}$ is not
a zero divisor in $A/(a_{1},\dots a_{n})$. A local ring $A$ is a
Cohen–Macaulay ring if there exists a regular sequence $a_{1},\dots a_{n}$
such that the quotient ring $A/(a_{1},\dots a_{n})$ is Artinian. In that case,
$n=\dim(A)$. More generally, a commutative ring is called Cohen–Macaulay if it
is Noetherian, and all of its localizations at prime ideals are
Cohen–Macaulay. Besides, we say that a ring $A$ is a complete intersection if
there exists some surjection $R\to A$, with $R$ a regular local ring, such
that a regular sequence generates the kernel. Our goal is to identify the
complete intersection property for the Stanley-Reisner ideal of broken circuit
ideals of matroids. For that, let us present some definitions next.

Let us assume that $(X,<)$ is an ordered matroid on $[n]$, and
$\mathcal{C}(X)$ is the set of broken circuits of $X$. Let $I_{<}(X)$ be the
Stanley-Reisner ideal of the broken circuit complex $BC_{<}(X)$. A subset
$D\in\mathcal{C}(X)$ is called generating set if $\langle x_{bc_{<}(C)};\ C\in
D\rangle$ generates $I_{<}(X)$. It is clear from definition that $D$ is a
generating set of $\mathcal{C}(X)$ iff $bc_{<}(C)$ for $C\in D$ containing
minimal broken circuits of $X$. Denote by $L(D)$ the intersection graph of
$D$, that is the vertex set of $L(D)$ is $D$ and the edges are pairs
$(C,C^{\prime})$ such that $C\cap C^{\prime}=\emptyset$. Say $D$ is simple if
whenever $C,C^{\prime}\in D$ then either $C\cap C^{\prime}=min_{<}(C)\
\text{or}\ min_{<}(C^{\prime})$, and otherwise $C\cap C^{\prime}=\emptyset$.

######  Theorem 2.8 ([32]).

Assume $(X,<)$ be and simple ordered matroid. The following are equivalent.

  * •

$I_{<}(X)$ is complete intersection.

  * •

The minimal broken circuits of $X$ are pairwise disjoint.

  * •

There exists a simple subset $D\subset\mathcal{C}(X)$ such that
$\mathcal{C}(X)=\\{L(D^{\prime});\ D^{\prime}\subset D\\}$.

Theorem 2.8 gives a concrete combinatorial criteria to check the complete
intersection property of Stanley-Reisner ideal of broken circuit complex of
matroids. It can also be applied to graph matroids, see [32].

###  2.4. Hyperplane arrangements

To an arrangement of hyperplanes $\mathcal{A}$ one naturally associates a
matroid denoted by $X=X(\mathcal{A})$ with the ground set to be the same as
$\mathcal{A}$ and the independent sets to be the independent hyperplanes in
$\mathcal{A}$, i.e., those whose corresponding reflections as said above are
independent. Assume that the matroid $X(\mathcal{A})$ is associated to an
essential central hyperplane arrangement of $n$ hyperplanes
$\mathcal{A}=\\{H_{1},\dots,H_{n}\\}$ in a vector space $V$ of dimension $r$
over the infinite field $k$. When $k=\mathbb{C}$, then the integral cohomology
of the complement $V\smallsetminus\bigcup_{i}H_{i}$ is isomorphic to the
Orlik-Solomon algebra of $A(\mathcal{A})$, which is the quotient of standard
graded exterior algebra on $\mathbb{C}\langle e_{1},\dots,e_{n}\rangle$ by the
Orlik-Solomon ideal $J(\mathcal{A})$ generated by the elements

(2.12) $\partial e_{i_{1}\dots i_{p}}=\ \sum_{r}\
(-1)^{r-1}e_{i_{1}}\dots\widehat{e_{i_{r}}}\dots e_{i_{p}},$

when $\\{H_{i_{1}},\dots,H_{i_{p}}\\}$ are dependent subsets of $\mathcal{A}$,
i.e. the reflections $\alpha_{i_{j}}$ through $H_{i_{j}}$ are independent.
Therefore,

(2.13) $A(\mathcal{A})=\frac{A}{J(\mathcal{A})}=\frac{\bigwedge\mathbb{Z}\
\langle e_{1},\dots,e_{n}\rangle}{\langle\partial e_{i_{1}\dots
i_{p}}\rangle}=H^{*}(V\smallsetminus\bigcup_{i}H_{i},\mathbb{Z}).$

The Orlik-Terao algebra is a commutative analogue of Orlik-Solomon algebra.
That is, instead of exterior algebra on $n$ vectors we work on
$A=k[x_{1},\dots,x_{n}]$ and whenever we have a relation
$\sum_{j}a_{j}\alpha_{i_{j}}=0$ we assume a relation
$r=\sum_{j}a_{j}\alpha_{i_{j}}$ in a relation space $F(\mathcal{A})$. The
Orlik-Terao ideal is generated by

(2.14) $\partial{r}=\ \sum_{j}\
(-1)^{j-1}a_{j}x_{i_{1}}\dots\widehat{x_{i_{j}}}\dots
x_{i_{p}},\qquad\Leftarrow\qquad\left(r=\sum_{j}a_{j}\alpha_{i_{j}}\right).$

The quotient $C(\mathcal{A})=A/I(\mathcal{A})$ is called the Orlik-Terao
algebra of the hyperplane arrangement. The Orlik-Solomon algebras and Orlik-
Terao algebras of hyperplane arrangements are related to each other by an idea
of deformation [17]. A relevant notion in this context is that of a Koszul
algebra defined next.

######  Definition 2.9 ([32]).

Suppose $L$ is either an exterior or a polynomial algebra over a field $k$. A
graded algebra $B=L/I$ is called Koszul if $k$ has linear resolution over $B$.

The characterization of the Koszulness of the Orlik-Solomon algebra of
hyperplane arrangement is one of the essential questions in this area. In this
regard, we mention the following theorem.

######  Theorem 2.10 ([32]).

Let $\mathcal{A}$ be an essential central arrangement of $n$ hyperplanes in
dimension $r$, and assume $I(\mathcal{A})$ is complete intersection. Then the
following are equivalent.

  * (1)

$A(\mathcal{A})$ is Koszul.

  * (2)

$C(\mathcal{A})$ is Koszul.

  * (3)

$X(\mathcal{A})=U_{2,n-r+2}\bigoplus U_{r-2,r-2}$.

  * (4)

$\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}$ where $\mathcal{A}_{1}$ is
generic central arrangement of $n-r+2$ hyperplanes in dimension $p$ and
$\mathcal{A}_{2}$ is Boolian in dimension $r-2$.

  * (5)

$I(\mathcal{A})$ has $2$-linear resolution.

  * (6)

$J(\mathcal{A})$ has $2$-linear resolution.

It is well-known that if $B$ is Koszul then $I$ is generated by quadrics.
Unfortunately, the converse is not true in general. The following consequence
is immediate from the above theorem.

######  Theorem 2.11 ([32]).

The Orlik-Terao ideal $I(\mathcal{A})$ of an essential central arrangement has
2-linear resolution if $\mathcal{A}$ is obtained by successively coning a
central arrangement of lines in the plane. In this case The Orlik-Terao
algebra is Koszul.

###  2.5. Basic operations on matroids

Assume $X$ is a matroid with an element set $E$, and $S$ is a subset of $E$.
The restriction of $X$ to $S$, written $X|S$, is the matroid on the set S
whose independent sets are the independent sets of $X$ that are contained in
$S$. Its circuits are the circuits of $X$ contained in S, and its rank
function is that of $X$ restricted to subsets of $S$. In linear algebra, this
corresponds to restricting to the subspace generated by the vectors in $S$. If
$T=X-S$, this is equivalent to the deletion of $T$, written $X\smallsetminus
T$. The submatroids of $X$ are precisely the results of a sequence of
deletions (the order is irrelevant). The dual operation of restriction is
contraction. If $T$ is a subset of $E$, the contraction of $X$ by $T$, written
$X/T$, is the matroid on the underlying set $E-T$ whose rank function is
${\displaystyle r^{\prime}(A)=r(A\cup T)-r(T)}$. In linear algebra, this
corresponds to looking at the quotient space by the linear space generated by
the vectors in $T$, together with the images of the vectors in $E-T$. Then,
the Tutte polynomial is defined by the recurrence relation ${\displaystyle
T(A)=T(A\cup T)-T(T)}$, [33, 34, 35]. Given a matroid $([n],I)$, and if
$X\subset[n]$ then, the deletion $[n]\smallsetminus X$ is the matroid with
ground set $[n]\smallsetminus X$ and independent sets
$\\{J\subset[n]\smallsetminus X:J\in I\\}$. The matroid dual $X^{*}$ of $X$ is
the matroid on $[n]$ where $I$ is a basis of $X$ iff $I^{c}$ is a basis of
$X^{*}$. If $X\subset[n]$ then the contraction can be defined as
$N/X=(N^{*}\diagdown X)^{*}$.

Now, let $X$ and $Y$ be matroids on the same ground set $E$. We say that $Y$
is a quotient of $X$ if one of the following equivalent statements holds:

  * •

Every circuit of $X$ is a union of circuits of $Y$.

  * •

If $X^{\prime}\subset Y^{\prime}\subset E$, then
$r_{M}(Y^{\prime})-r_{M}(X^{\prime})\geq r_{N}(Y^{\prime})-r_{N}(X^{\prime})$,
($r$ is the rank function, see [10]).

  * •

There exists a matroid $R$ and a subset $X^{\prime}$ of $E(R)$ such that
$X=R\smallsetminus X^{\prime}$ and $Y=R/X^{\prime}$.

  * •

For all bases $B$ of $X$, and $x\in B$, there is a basis $B_{0}$ of $Y$, with
$B_{0}\subset B$, such that $\\{y:(B_{0}-y)\cup x\in
B(N)\\}\subset\\{y:(B-y)\cup x\in B(X)\\}$.

For the equivalences, we refer to [22], Proposition 7.3.6. If $Y$ be a
quotient of $X$, it follows that:

  * •

Every basis of $Y$ is contained in a basis of $X$, and every basis of $X$
contains a basis of $Y$.

  * •

$rk(Y)\leq rk(X)$ and in case of equality, $Y=X$.

cf. [10] loc. cit.

######  Definition 2.12.

A stratification of a matroid $X$ is a decreasing filtration sequence
$X=M_{0}\supset X_{1}\supset\dots\supset X_{d}$ by submatroids $X_{j}$, where
we call $X_{j}\smallsetminus X_{j+1}$ the $j$-th strata of the stratification.

The Tutte polynomial of $X$ becomes the sum of the Tutte polynomials on each
strata $S_{j}=X_{j}\smallsetminus X_{j+1}$, [see [33, 34, 35]].

###  2.6. The r-cyclic graph

Let $(G,V,E)$ be a graph, $V$ the vertices and $E$ the edges. Set
$\mathcal{C}$ the edge set of cycles in $G$. It is the set of circuits of a
matroid, namely cycle matroid. We assume the graph and this matroid are
simple, i.e., every circuit has at least three vertices. In [4] the Cohen-
Macaulayness of the facet ideal of $r$-cyclic graph $G_{n,r}$ has been
discussed. We can show that the facet ideal of $G_{n,r}$ is a complete
intersection.

######  Definition 2.13 ([4]).

Let $\Delta$ be a simplicial complex over $[n]$. Let $I_{F}(\Delta)$ be the
monomial ideal minimally generated by square-free monomials
$f_{F(1)},\dots,f_{F(s)}$ such that

(2.15) $f_{F(i)}=x_{i_{1}}x_{i_{2}}\dots x_{i_{r}},\qquad\Leftrightarrow\qquad
F(i)=\\{i_{1},\dots,i_{r}\\}\ \text{is a facet of}\ \Delta\ \text{ for all}\
i,$

known as the facet ideal of complex $\Delta$ and denoted $I_{F}(\Delta)$. The
graph $G_{n,r}$ has $n$ edges and $r$ distinct cycles. One naturally
associates a simplicial complex $\Delta(G_{n,r})=\langle
E\smallsetminus\\{e_{1i_{1}},\dots,e_{ri_{r}}\\}\rangle$ to $G_{n,r}$, where
$C_{i}=\\{e_{1_{1}},\dots,e_{1_{i}}\\}$ is the $i$-th cycle, [4].

The theory of matroids and their broken circuit complexes is very much tied
with the theory of graphs. In Section 4 we present an example of this feature
in our results.

##  3\. Main Results

In this section, we extend some main results presented in [32] to the
corresponding graded notions. All the definitions and theorems in this section
are new results. We prove three kinds of results: a) The first is the
definition of the graded linearity and graded linear quotient property. We
compare the two notions of graded linearity and graded linear quotients on
graded $A$-modules, and then we also compare graded linearity with
componentwise linearity. b) The second is to identify the graded linearity of
the Stanley-Reisner ring of broken circuit complexes in terms of the Hilbert
polynomial. c) The third is a stratified decomposition property of the matroid
when the Stanley-Reisner ideal of broken circuit complex has graded linear
resolution.

###  3.1. Graded linear resolutions

We introduce the two following definitions. Next, we prove a theorem that
compares the two definitions.

######  Definition 3.1.

We say $M$ has graded linear quotient, if there exists a minimal system of
generators $a_{1},\dots,a_{m}$ of $M$ such that the colon ideals satisfy
$indeg(J_{l})=1$ 111We call the least degree of a homogeneous generator of a
graded $A$-module $M$, the initial degree of $M$, denoted by $indeg(M)$..

######  Definition 3.2.

Say $M$ has graded linear resolution if the graded Betti numbers in the graded
Betti table appear in a finite number of horizontal lines, with finitely many
non-zero entries in each line, and successively.

An example of having graded linear resolution is that of having linear
resolution. However, the graded linearity is more general. We stress that
having linear property for the graded modules under consideration is a
strictly special case. Then, we present our next main result.

######  Theorem 3.3 (Main result).

Assume that $M$ is a graded $A$-module minimally generated by a regular
sequence $(a_{1},\dots,a_{n})$ in $\mathfrak{m}$; and $J_{l}$ is defined as in
Definition 2.2. If $M$ has graded linear quotients, then $J_{l}$ has graded
linear resolution for any $l$.

###### Proof.

We use induction on $l$. Consider the short exact sequence,

(3.1) $0\to\frac{A}{(J_{l}:z_{l+1})}\stackrel{{\scriptstyle\times
z_{l+1}}}{{\longrightarrow}}\frac{A}{J_{l}}\longrightarrow\frac{A}{J_{l+1}}\to
0.$

The first and the last module have quasi-linear resolutions by induction
assumption. Now, consider the associated long graded Tor exact sequence:

(3.2)
$\displaystyle\longrightarrow{Tor_{i}\Big{(}\frac{A}{(J_{l}:z_{l+1})},k\Big{)}}_{j}\stackrel{{\scriptstyle\times
z_{l+1}}}{{\longrightarrow}}{Tor_{i}\Big{(}\frac{A}{J_{l}},k\Big{)}}_{j+d}\longrightarrow{Tor_{i}\Big{(}\frac{A}{J_{l+1}},k\Big{)}}_{j+d}\longrightarrow$
(3.3)
$\displaystyle{Tor_{i-1}\Big{(}\frac{A}{(J_{l}:z_{l+1})},k\Big{)}}_{j+d-1}\stackrel{{\scriptstyle\times
z_{l+1}}}{{\longrightarrow}}{Tor_{i-1}\Big{(}\frac{A}{J_{l}},k\Big{)}}_{j+d-1}\longrightarrow$

where $d=\deg(a_{l+1})$. One notes that multiplication by $z_{l+1}$ is in the
annihilator of $k$. This implies the sequence

(3.4)
$0\to{Tor_{i}\Big{(}\frac{A}{J_{l}},k\Big{)}}_{j+d}\longrightarrow{Tor_{i}\Big{(}\frac{A}{J_{l+1}},k\Big{)}}_{j+d}\longrightarrow{Tor_{i-1}\Big{(}\frac{A}{(J_{l}:a_{l+1})},k\Big{)}}_{j+d-1}\to
0$

is short exact. We note that ${Tor_{i}\Big{(}\frac{A}{J_{l}},k\Big{)}}_{j+d}$
embeds into ${Tor_{i}\Big{(}\frac{A}{J_{l+1}},k\Big{)}}_{j+d}$. Therefore, the
non-triviality of the first one implies the non-triviality of the second.
Therefore, in order to check the induction step it suffices to prove

(3.5) $Tor_{i}\big{(}\frac{A}{J_{l+1}},k\big{)}_{j+d}\neq 0\ \iff\
Tor_{i-1}\big{(}\frac{A}{(J_{l}:a_{l+1})},k\big{)}_{j+d-1}\neq 0.$

The last assertion is true for the implication

(3.6)
${Tor_{i-1}\Big{(}\frac{A}{(J_{l}:a_{l+1})},k\Big{)}}_{j+d-1}=0\qquad\Rightarrow\qquad{Tor_{i}\Big{(}\frac{A}{J_{l}},k\Big{)}}_{j+d}=0.$

Now, the assertion follows by induction, and the proof is complete. ∎

In the following theorem, we compare the graded linearity with the
componentwise linearity defined in the previous section. As a result, the
graded linear property is weaker than componentwise linearity. Therefore, our
definition can be regarded as a more general approximation to the concept of
componentwise linear resolution.

######  Theorem 3.4 (Main result).

Assume $M$ is a finitely generated graded $A$-module. Consider the following
statements

  * (1)

$M$ has graded linear resolution.

  * (2)

$M_{\langle s\rangle}$ have graded linear resolutions for all $s$.

  * (3)

$M$ is componentwise linear.

Then, we have (3) $\Rightarrow$ (2) $\Leftrightarrow$ (1).

###### Proof.

: The implications (3) $\Rightarrow$ (2) $\Rightarrow$ (1), are evident by
Theorem 2.5. Therefore, we check out (1) $\Rightarrow$ (2). This follows from
the fact that a graded resolution of $M_{\langle s\rangle}$ can be included
(is a subresolution) in a graded resolution of $M$. ∎

###  3.2. Graded linearity and broken circuit complexes

We want to characterize the graded linear resolution property for the Stanley-
Reisner rings of broken circuit complexes. The following result generalizes
Theorem 2.6 presented in the previous section and conforms to part of our main
results.

######  Theorem 3.5.

Let $(X,<)$ be an ordered simple matroid of rank $r$ on $[n]$. The followings
are equivalent:

  * (1)

$I_{<}(X)$ has graded linear resolution.

  * (2)

If $a_{1},\dots,a_{n-q}$ is a maximal $(A/I_{<}(X))$-regular sequence of
linear forms in $A$, we have

(3.7) $\frac{\overline{A}}{\overline{I_{<}(X)}}=\bigoplus_{i=0}^{d}\
\frac{\overline{\mathfrak{m}}^{s_{i}}}{\overline{\mathfrak{m}}^{s_{i+1}}},$

in $A/(a_{1},\dots,a_{n-s})$.

  * (3)

The Hilbert function of $I_{<}(X)$ has the form,

(3.8) $H(\frac{A}{I_{<}(X)},s)=c_{0}{s+q-1\choose s}+c_{1}{s+q-2\choose
s}+\cdots+c_{d-1}{s+q-d\choose s},$

for some $d$.

  * (4)

If $\prec$ is a monomial order on $A$ and if $\ in_{\prec}(I_{<}(X))\ $ is
Cohen-Macaulay, $\ in_{\prec}(I_{<}(X))\ $ has graded linear resolution.

###### Proof.

(3) follows from (2), and also, (4) follows from (3) and the equality of the
Hilbert functions

(3.9) $H(A/I_{<}(X),s)=H(\overline{A/I_{<}(X)},s),$

where the bar means the image in $A/(a_{1},\dots,a_{n-q})$. Also, one has the
stronger statement

(3.10) $\displaystyle H(A/I_{<}(X),s)=H(\overline{A/I_{<}(X)},s)\leq
H(\bigoplus_{i=0}^{d}\
\frac{\overline{\mathfrak{m}}^{s_{i}}}{\overline{\mathfrak{m}}^{s_{i+1}}},s)=\sum_{i=0}^{d-1}c_{i}{s+q-i-1\choose
s},$

with equality when (3.7) holds. In fact, by factoring out the regular sequence
$(a_{1},\dots,a_{n-q})$ one can assume $A$ is Artinian. Then, it is easy to
establish that it has the form (3.7), [see also [32] proposition 3.1]. This
also proves (2). ∎

######  Remark 3.6.

The coefficients $c_{i}=c_{i}(I_{<}(X))$ can be easily calculated, (called
Hilbert coefficient of $I_{<}(X)$). The sum in the Hilbert polynomial is the
sum of the Hilbert function of each summand where can be calculated by hand.

The following lemma is a generalization of proposition 7.5.2 in [6] and forms
part of our main result.

######  Lemma 3.7.

Assume $X$ is a rank $r$ loopless matroid on $[n]$ such that the Stanley-
Reisner ideal of the broken circuits of $X$ has graded linear resolution.
Then,

(3.11) $I_{j-1}\geq\sum_{i=0}^{c-1}\sum_{l=1}^{d}c_{l}^{(S)}{n-r+l-1\choose
l}{r-i\choose j-i}$

and the equality holds if and only if there exists a stratification
$X=X_{0}\supset X_{1}\supset\dots\supset X_{d}$ by submatroids $X_{j}$ for
some $d$ such that on each strata,

(3.12) $X_{j}\diagdown X_{j+1}=U_{r_{j}-s_{j},r_{j}-s_{j}}\bigoplus
U_{s_{j},n_{j}-r_{j}+s_{j}},$

where $s_{j}\leq r_{j}$ are positive integers and $U_{l,k}$ denotes the
uniform matroid. And also, We have $n=\Sigma_{j}n_{j},\ r=\Sigma_{j}r_{j}$.

###### Proof.

Following the argument of Theorem 2.7 of previous section [or theorem 7.2.5
[6]], and letting $\Delta=In(X)$, then we have,

(3.13) $h_{k}=H(A/I_{<}(X),k)=\ \sum_{l}c_{l}{k+q-l-1\choose k},\qquad
k=0,1,2,\dots,c-1,$

where $c_{l}$ are Hilbert coefficients of $I_{<}(X)$. Then,

(3.14) $b(X)=\sum_{l}c_{l}{q-l+p\choose p}$

is the number of bases of $X$. Besides, the $h$-vector is given by,

(3.15) $\underline{\textbf{h}}=\left(\ 1\ \ ,\ \sum_{l}c_{l}{q-l\choose 1},\ \
\dots\ \ ,\ \sum_{l}c_{l}{c-1+q-l-1\choose c-1}\ \right),$

and the Tutte polynomial of $X$ is
$T_{X}(x,1)=h_{\Delta}(x)=x^{r}+h_{1}x^{r-1}+\cdots+h_{p}x^{r-p}$. The form of
the Tutte polynomial shows the existence of stratification $X=X_{0}\supset
X_{1}\supset\dots\supset X_{d}$ by submatroids $X_{j}$ such that,

(3.16) $X_{j}\diagdown X_{j+1}=U_{r_{j}-s_{j},r_{j}-s_{j}}\bigoplus N_{j}$

holds, where $N_{j}$ is a matroid of rank $s_{j}$ on $n_{j}-r_{j}+s_{j}$
points. In fact, the $\underline{\textbf{h}}$-vector of the submatroids
$X_{j}$ is given by the truncations of the sums appearing in the
$\underline{\textbf{h}}$-vector of $X$. Thus,

(3.17) $b(N_{j})=b(X_{j}\diagdown X_{j+1})=c_{j}{c-j+q-l\choose c-1}$

holds, and this shows that $N_{j}$ has the desired form. The equality in
(3.11) holds when $h_{c}=h_{c+1}=\dots=0$. ∎

We can now formulate the graded linearity of the Stanley-Reisner ideal of the
broken circuits in terms of the combinatorics of $M$. The Theorem 3.5 and the
Lemma 3.7 can be used together to obtain the following decomposition property,
expressed in the following result.

######  Theorem 3.8 (Main result).

Let $(X,<)$ be an ordered simple matroid of rank $r$ on $[n]$, and $I_{<}(X)$
the Stanley-Reisner ideal of broken circuit complex of $X$. Then, the
followings are equivalent.

  * (1)

$I_{<}(X)$ has graded linear resolution.

  * (2)

There exists a stratification $X=X_{0}\supset X_{1}\supset\dots\supset X_{d}$
for some $d$ such that on each strata

(3.18) $X_{j}\diagdown X_{j+1}=U_{r_{j}-s_{j},r_{j}-s_{j}}\bigoplus
U_{s_{j},n_{j}-r_{j}+s_{j}}$

holds, where $s_{j}\leq r_{j}$ are positive integers. Besides, we have
$n=\Sigma_{j}n_{j},\ r=\Sigma_{j}r_{j}$.

###### Proof.

We first show that $(2)\Rightarrow(1)$. First, assume that (2) holds. Then, by
re-arrangement of variables, we can assume that

(3.19) $\displaystyle I_{<}(X)=\big{\langle}\ x_{j_{1}}\cdots x_{j_{s_{1}}}\
,\ \dots\ ,\ x_{l_{1}}\cdots x_{l_{p}}\ |\ \ j_{1}<\dots<j_{s_{1}}<n-r+s_{1}$
(3.20) $\displaystyle,\ \dots\ ,\ l_{1}<\dots<l_{p}<n-r+p\ \big{\rangle}.$

This ideal has graded linear resolution.

Next, we show $(1)\Rightarrow(2)$. For that, let us assume that (1) holds,
i.e., assume $I_{<}(X)$ has graded linear resolution. Then, the properties (2)
and (3) of Theorem 3.5, if $\textbf{a}=(a_{1},\dots,a_{r})$ is a maximal
$S/I_{<}(X)$-regular sequence of linear forms, then

(3.21)
$S=A/(I_{<}(X)+\textbf{a})=\bigoplus_{j=0}^{d}\overline{\mathfrak{m}}^{s_{j}}/\overline{\mathfrak{m}}^{s_{j+1}},\qquad(\mathfrak{m}^{0}=A).$

Thus, the Hilbert function of $A/I_{<}(X)$ is given by

(3.22) $H(A/I_{<}(X),t)=H(S,t)/\prod_{i}(1-t^{s_{i}}).$

So that the $f$-vector of Stanley-Reisner ring is given by

(3.23) $f_{j-1}=\sum_{i=0}^{r}c_{i}{r-i\choose
j-i}=\sum_{i=0}^{r}\sum_{l=1}^{d}c_{l}{n-r+l-1\choose l}{r-i\choose j-i},$

where $d=\deg(H(S,t))$ and $c_{l}=c_{l}^{(S)}$ are the coefficients of
$H(S,t)$. Thus, the lemma 3.7 implies the decomposition in item (2). ∎

######  Remark 3.9.

We highlight three main points:

  * •

There are modules over the polynomial ring that are not componentwise linear
but satisfy being graded linear. A simple example is a direct sum of a non-
componentwise linear module with one componentwise linear, where the
resolutions are just direct sums of the two resolutions of the modules. Being
”graded linear” is a relatively weak property compared to being componentwise
linear.

  * •

Let $X$ be the graphic matroid of parallel connection of a 3-circuit with a
4-circuit. Then, $X$ is a non-uniform 2-connected matroid, and therefore can
not be a direct sum of uniform matroids. We can order the elements of $X$ from
1 to 6 in a way that the Stanley-Reisner ideal of the broken circuit complex
of $M$ gets equal to $I(X)=(x_{5}x_{6},x_{2}x_{3}x_{6},x_{2}x_{3}x_{4}x_{5})$.
Then, $I(X)$ has a linear quotient and is, therefore, componentwise linear.
This example shows that the stratification mentioned in the above theorem is
essential.

  * •

There exist componentwise (matroidal) ideals, which are not generated by the
regular sequence. For instance, let $M$ be the same as the previous item, the
parallel connection of a 3-circuit and a 4-circuit, then $I(X)$ is
componentwise linear and has linear quotients, but a regular sequence does not
generate it.

##  4\. Applications

This section applies the results of the previous section to the Orlik-Solomon
ideal and the Orlik-Terao ideal of the arrangements of hyperplanes. Our
results are direct interpretations of the theorems presented in Section 3, but
into the language of hyperplane arrangements. All the definitions and theorems
of this section are new contributions to this text.

###  4.1. Application to hyperplane arrangements

We begin by the following theorem.

######  Theorem 4.1.

For an essential central arrangement of $\mathcal{A}$ of $n$ hyperplanes,
located in a vector space of dimension $r$, the following points are
equivalent.

  * •

$I(\mathcal{A})$ has graded linear resolution.

  * •

There exists a stratification $X=X_{0}\supset X_{1}\supset\dots\supset X_{d}$
by submatroids $X_{j}$ for some $d$ such that $X_{j}(\mathcal{A})\diagdown
X_{j+1}(\mathcal{A})=U_{r_{j}-s_{j},r_{j}-s_{j}}\\\ \bigoplus
U_{s_{j},n_{j}-r_{j}+s_{j}}$ where $s_{j}\leq r_{j}$ are positive integers.
Also, we have $n=\Sigma_{j}n_{j},\ r=\Sigma_{j}r_{j}$.

  * •

$\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}\times\dots\times\mathcal{A}_{k}$
where $\mathcal{A}_{1}$ is boolian and the other factors $\mathcal{A}_{j}$ for
$j>1$ are generic arrangements of $n_{j}-r_{j}+s_{j}$ hyperplanes ina
$s_{j}$-dimensional vector space.

###### Proof.

The proof is analogous to the 2-decomposition case in [32], and is just an
interpretation of the Theorems in the previous section. ∎

In the following, we generalize the Koszul property to that of graded Koszul
in a natural way. First, let consider the following definition.

######  Definition 4.2.

In the settings of Definition 2.9 we call $B$ graded Koszul if $k$ has graded
linear resolution.

The following consequence is immediate from the above theorem.

######  Theorem 4.3.

The Orlik-Terao ideal $I(\mathcal{A})$ has 2-graded linear resolution if
$\mathcal{A}$ is obtained by successively coning central arrangements of lines
in the plane. In this case, the Orlik-Terao algebra is graded Koszul.

###### Proof.

The proof is a direct application of Theorem 4.1. ∎

######  Theorem 4.4.

With the same set-up of Theorem 4.1 the following are equivalent

  * (1)

$A(\mathcal{A})$ is graded Koszul.

  * (2)

$C(\mathcal{A})$ is graded Koszul.

  * (3)

There exists a stratification $X=X_{0}\supset X_{1}\supset\dots\supset X_{d}$
by submatroids $X_{j}$ for some $d$ such that $X_{j}(\mathcal{A})\diagdown
X_{j+1}(\mathcal{A})=U_{r_{j}-s_{j},r_{j}-s_{j}}\\\ \bigoplus
U_{s_{j},n_{j}-r_{j}+t_{j}}$, where $s_{j}\leq r_{j}$ are positive integers.
Also, we have $n=\Sigma_{j}n_{j},\ r=\Sigma_{j}r_{j}$.

  * (4)

$\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}\times\dots\times\mathcal{A}_{k}$
where $\mathcal{A}_{1}$ is boolian and the other factors $\mathcal{A}_{j}$ for
$j>1$ are generic arrangement of $n_{j}-r_{j}+s_{j}$ hyperplanes in a
$s_{j}$-dimensional vector space.

  * (5)

$I(\mathcal{A})$ has $2$-graded linear resolution.

  * (6)

$J(\mathcal{A})$ has $2$-graded linear resolution.

###### Proof.

The equivalence of (2)-(5) was already established above. The equivalence of
(1)-(2) follows from Theorem 4.1 and the argument in Theorem 3.8. ∎

The characterization of the Koszul property of Orlik-Solomon algebras of
matroids (arrangments) is one of the essential problems in this area. It is a
conjecture that; a matroid (an arrangement) is supersolvable if and only if
its Orlik-Solomon algebra is Koszul, [see [32, 9] for instance].

###  4.2. Application on the facet ideal of the $r$-cyclic graph

Our last result is an application to prove the entire intersection property of
the facet ideal of the $r$-cyclic graph, [see Subsection 2.6].

######  Proposition 4.1.

The facet ideal $I_{F}(\Delta(G_{n,r}))$ is a complete intersection.

###### Proof.

By definition, $G_{n,r}$ is a graph on $n$ edges with exactly $r$ distinct
cycles. Therefore, the broken circuits of the cycle matroid $X(G_{n,r})$ are
pairwise disjoint. On the other hand, the Stanley-Reisner ideal of the broken
circuit complex of cycle matroid $X(G_{n,r})$ is exactly the facet ideal of
the complex $\Delta(G_{n,r})$. Now, the theorem follows from Theorem 2.8. ∎

######  Corollary 4.4.1.

The facet ideal $I_{F}(\Delta(G_{n,r}))$ is Cohen-Macaulay.

The corollary has been proved in [4] by a direct computational method. We
proved it as an immediate consequence of our result. A comprehensive analysis
of the entire intersection property for graph matroids related to broken
circuits is given in [32].

##  5\. Conclusion

The notion of graded linear resolution is introduced, and several
characterizations of this property are shown for certain the graded algebras
associated with matroids. The notion is compared with that of graded linear
quotions and componentwise linearity in general. Specifically, it is proved
that the graded linearity of the Stanley-Reisner ideal of broken circuit
complex of a simple matroid implies a mixed decomposition of a matroid into
uniform matroids, along with a stratification. The translation of these
results into the language of hyperplane arrangements is also given at the end.
Finally, an application to complete the intersection property of the facet
ideal of $r$-cyclic graph is given.

## Conflict of Interest

The work’s authors declare that they do not have any conflict of interests.

## Author contributions statement

M. Reza-Rahmati and G. Flores reviewed the manuscript and contributed equally
to the work.

## References

  * [1] Aramova, A., Avramov, L.L., Herzog, J.: Resolutions of monomial ideals and cohomology over exterior algebras. Trans. Am. Math. Soc. 352(2), 579–594 (2000)
  * [2] Anwar I., Raza Z., Quasi-linear quotient and shellability of pure simplicial complexes, Communications in Algebra, 43: 4698–4704, (2015)
  * [3] Anwar I., Ahmad A., Nazir S., Monomial Ideals with Quasi-Linear Quotients, Lobachevskii Journal of Mathematics volume 40, 85–89 (2019)
  * [4] Anwar I., Raza Z., Quasi-linear quotients and shellability of pure simplicial complexes, Communications in Algebra 43 (11), 4698-4704
  * [5] Anwar, I., Raza, Z., Kashif, A. Spanning simplicial complexes of uni-cyclic graphs. Algebra Colloquium.
  * [6] Björner, A.: The homology and shellability of matroids and geometric lattices. In: White, N. (ed.) matroid Applications, pp. 226–283. Cambridge Univ. Press, Cambridge (1992)
  * [7] Björner, A., Ziegler, G.: Broken circuit complexes: factorizations and generalizations. J. Comb. Theory, Ser. B 51(1), 96–126 (1991)
  * [8] Brylawski, T., Oxley, J.: The broken-circuit complex: its structure and factorizations. Eur. J. Comb. 2(2), 107–121 (1981)
  * [9] Conca A., E. De Negri, M. Rossi, Koszul Algebras and Regularity, Commutative Algebra (2012), 285-315
  * [10] Cameron A.; Dinu R., Michalek M.; Seynnaeve T., Flag matroids: algebra and geometry, preprint https://arxiv.org/pdf/1811.00272.pdf
  * [11] Dress, A. A new algebraic criterion for shellability. Beitr. Algebr. Geom. 340(1): 45–50. (1993)
  * [12] Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Springer, New York (1995)
  * [13] Eisenbud, D., Popescu, S., Yuzvinsky, S.: Hyperplane arrangement cohomology and monomials in the exterior algebra. Trans. Am. Math. Soc. 355, 4365–4383 (2003)
  * [14] Faridi, S. The facet ideal of a simplicial complex. Manuscripta Mathematica 109: 159–174. (2002)
  * [15] Fröberg, R.: Koszul algebras. In: Advances in Commutative Ring Theory, Fez, 1997. Lecture Notes in Pure and Appl. Math., vol. 205, pp. 337–350. Dekker, New York (1999)
  * [16] Herzog, J., Popescu, D. (2006). Finite Filterations of modules and shellable multicomplexes. Manuscripta Math. 121: 385–410.
  * [17] Herzog, J., Hibi, T.: Monomial Ideals. Graduate Texts in Mathematics, vol. 260. Springer, Berlin (2011)
  * [18] Kämpf, G., Römer, T.: Homological properties of Orlik–Solomon algebras. Manuscr. Math. 129, 181– 210 (2009)
  * [19] Nagel U., Römer T., Criteria for Componentwise Linearity, Journal Communications in Algebra Volume 43, 2015, Issue 3, 935-952
  * [20] Orlik, P., Solomon, L.: Combinatorics and topology of complements of hyperplanes. Invent. Math. 56, 167–189 (1980)
  * [21] Orlik, P., Terao, H.: Arrangements of Hyperplanes. Grundlehren Math. Wiss., Bd., vol. 300. Springer, Berlin (1992)
  * [22] Oxley J., Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011.
  * [23] Peeva, I.: Graded Syzygies. Algebra and Applications, vol. 14. Springer, London (2011)
  * [24] Popescu, D. (2006). Criterions for shellable multicomplexes. An. St. Univ. Ovidius, Constanta 14(2): 73–84.
  * [25] Provan, J. S.: Decompositions, shellings, and diameters of simplicial complexes and convex polyhedra. Thesis, Cornell Univ., Ithaca, NY (1977)
  * [26] Proudfoot, N., Speyer, D.: A broken circuit ring. Beiträge Algebra Geom. 47, 161–166 (2006)
  * [27] Renteria, C., Villarreal, R.: Koszul homology of Cohen–Macaulay rings with linear resolutions. Proc. Am. Math. Soc. 115, 51–58 (1992)
  * [28] Shelton, B., Yuzvinsky, S.: Koszul algebras from graphs and hyperplane arrangements. J. Lond. Math. Soc. 56, 477–490 (1997)
  * [29] Schenck H., Arrangements of Hyperplanes : computations and conjectures, Adv. Stud. Pure Math., Sapporo 2009, H. Terao and S. Yuzvinsky, eds. (Tokyo: Mathematical Society of Japan, 2012), 323-358
  * [30] Suciu A., Hyperplane arrangements and Milnor fibrations Annales de la Faculte des Sciences de Toulouse 23 (2), (2014), 417-481
  * [31] Stanley, R. P., Combinatorics and Commutative Algebra. 2nd ed. (1996)
  * [32] Van Le D., Römer T., Broken circuit complexes and hyperplane arrangements, Journal of Algebraic Combinatorics volume 38, 989–1016 (2013)
  * [33] White, N., Theory of Matroids, Encyclopedia of Mathematics and its Applications, 26, Cambridge: Cambridge University Press, , ed. (1986) ISBN 978-0-521-30937-0, Zbl 0579.00001.
  * [34] White, N., Combinatorial geometries, Encyclopedia of Mathematics and its Applications, 29, Cambridge: Cambridge University Press, ed. (1987), ISBN 978-0-521-33339-9, Zbl 0626.00007
  * [35] White, N., Matroid Applications, Encyclopedia of Mathematics and its Applications, 40, Cambridge: Cambridge University Press, , ed. (1992) ISBN 978-0-521-38165-9, Zbl 0742.00052