# Regularities and multiplicities of Veronese type algebras

Kuei-Nuan Lin and Yi-Huang Shen  Department of Mathematics, The Penn State
University, McKeesport, PA, 15132, USA<EMAIL_ADDRESS>CAS Wu Wen-Tsun Key
Laboratory of Mathematics, School of Mathematical Sciences, University of
Science and Technology of China, Hefei, Anhui, 230026, P.R. China
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we study the algebra of Veronese type. We show that the
presentation ideal of this algebra has an initial ideal whose Alexander dual
has linear quotients. As an application, we explicitly obtain the Castelnuovo-
Mumford regularity of the Veronese type algebra. Furthermore, we give an
effective upper bound on the multiplicity of this algebra.

2020 Mathematics Subject Classification. Primary 05E40 13F55 13F65 Secondary
14M25 13H15 13D02

Keyword: Algebra of Veronese type, Regularity, Cohen–Macaulay, Multiplicity

##  1\. Introduction

Let $S={\mathbb{K}}[x_{1},\dots,x_{n}]$ be a polynomial ring over a field
${\mathbb{K}}$ with $n\geq 2$. Suppose that $I$ is an ideal minimally
generated by some monomials $f_{1},\ldots,f_{u}$ in $S$. The _semigroup ring_
associated to $I$, denoted by ${\mathbb{K}}[I]$, is the subalgebra of $S$
generated by $f_{1},\dots,f_{u}$. This ring is also known as the _toric ring_
associated with $I$. In this work, we focus on investigating several algebraic
invariants of ${\mathbb{K}}[I]$ associated with an ideal of Veronese type.

We fix a degree $d$ and a sequence
${\bm{\alpha}}=(\alpha_{1},\ldots,\alpha_{n})$ of integers with
$1\leq\alpha_{1}\leq\cdots\leq\alpha_{n}\leq d$ and
$d<\sum_{i=1}^{n}\alpha_{i}$. Let ${\mathbb{N}}=\Set{0,1,2,\dots}$ be the set
of non-negative integers and

$I_{d,{\bm{\alpha}}}\coloneqq\Braket{{\bm{x}}^{\bm{c}}:{\bm{c}}=(c_{1},\dots,c_{n})\in{\mathbb{N}}^{n},\,\sum_{i=1}^{n}c_{i}=d\text{
and }c_{i}\leq\alpha_{i}\text{ for each $i$ }}$

be _an ideal of Veronese type_. Related, let
$\mathcal{A}_{d,{\bm{\alpha}}}={\mathbb{K}}[I]\subset S$ and call it an
_algebra of Veronese type_. If $\alpha_{1}=\cdots=\alpha_{n}$, then
$I_{d,{\bm{\alpha}}}$ is a special strongly symmetric shifted ideal. Moreover,
if $\alpha_{i}=d$ for all $i$, then $\mathcal{A}_{d,{\bm{\alpha}}}$ is the
$d$-th Veronese subring of $S$. Algebras of Veronese type have been studied
from the viewpoint of toric varieties, see [Sturmfels]. De Negri and Hibi also
classified the Gorensteinness of $\mathcal{A}_{d,{\bm{\alpha}}}$ in
[MR1458806, Theorem 2.4]. In addition, Costantini and Seceleanu studied
algebras associated with strongly symmetric shifted ideals in
[arXiv:2208.10476]. In this paper, we continue their work and compute the
Castelnuovo–Mumford regularity and the multiplicity of
$\mathcal{A}_{d,{\bm{\alpha}}}$.

Recall that for a finitely generated graded module $M$ over the polynomial
ring $S$, the _Castelnuovo–Mumford regularity_ of $M$, denoted by
$\operatorname{reg}(M)$, is $\max\Set{j-i:\beta_{i,j}\neq 0}$, where the
$\beta_{i,j}$’s are the graded Betti numbers of $M$. This regularity can be
used to bound the degree of the syzygy generators of the module $M$. Another
important invariant that we study here is the _multiplicity_ $\mathtt{e}(M)$
of $M=\bigoplus_{k}M_{k}$ with respect to the graded maximal ideal, where
$M_{k}$ is the degree $k$ component of the graded module $M$. Recall that the
Hilbert function $H(M,k):=\operatorname{dim}_{{\mathbb{K}}}(M_{k})$ is
eventually a polynomial in $k$ of degree $\operatorname{dim}(M)-1$. The
leading coefficient of this polynomial is of form
$\mathtt{e}(M)/(\operatorname{dim}(M)-1)!$. If $M$ is the homogeneous
coordinate ring of a projective variety $X$, then the multiplicity is just the
_degree_ of $X$.

One way to study the semigroup ring ${\mathbb{K}}[I]$ algebraically is to
investigate its presentation ideal. Let
${\mathbb{K}}[{\bm{T}}]={\mathbb{K}}[T_{f_{1}},\ldots,T_{f_{u}}]$ be a
polynomial ring in $u$ variables over ${\mathbb{K}}$. Then the _presentation
ideal_ $J$ is the kernel of the canonical ${\mathbb{K}}$-algebra homomorphism
$\psi:{\mathbb{K}}[{\bm{T}}]\rightarrow{\mathbb{K}}[I]$ with
$\psi(T_{f_{i}})=f_{i}$. Obviously, $J$ is a prime ideal and we have
${\mathbb{K}}[{\bm{T}}]/J\cong{\mathbb{K}}[I]$.

The study of algebra ${\mathbb{K}}[I]$ becomes more feasible if the Gröbner
basis of the presentation ideal $J$ exists; see [MR3595300] for the case of
chordal bipartite graphs, [MR2955237] for the $d$-th Veronese subring, and
[Lin-Shen3DMulti] for the case of three-dimensional Ferrers diagrams. This is
because the invariants of the initial ideal and the original ideal are closely
related, c.f. [MR2724673, Section 3.3]. According to the work of Conca and
Varbaro in [CV], these relations become tight when the initial ideal is
squarefree. On the other hand, without knowing the Gröbner basis of $J$,
finding the Castelnuovo–Mumford regularity or the multiplicity of
${\mathbb{K}}[I]$, for example, becomes a difficult task; cf. [MR1953712].

It is worth noting that if $J$ has a quadratic Gröbner basis, then the algebra
${\mathbb{K}}[I]$ is Koszul (that is, ${\mathbb{K}}$ has a linear resolution
over ${\mathbb{K}}[I]$) by [Froberg]. The authors of the current paper proved
in [Lin-Shen3D] that if $I$ is associated with a three-dimensional Ferrers
diagram satisfying a mild property, then the presentation ideal $J$ has a
quadratic Gröbner basis. This is the foundation for the calculation of the
Castelnuovo–Mumford regularity and the multiplicity in [Lin-Shen3DMulti].
However, the way we obtained the quadratic Gröbner basis seems to be model-
dependent. A more useful tool is the idea of _sorting monomials_ introduced by
Sturmfels. With this technique, Sturmfels [Sturmfels] proved that the
presentation ideal of $\mathcal{A}_{d,{\bm{\alpha}}}$ has a quadratic Gröbner
basis. More recently, Herzog et al. [arXiv:2209.10799] generalized the notion
of sortability to the non-equigenerated case and proved that the presentation
ideal of the algebra associated with a sortable monomial ideal also has a
quadratic Gröbner basis.

With the quadratic Gröbner basis of $J$ described earlier by Sturmfels, we can
study the Veronese type algebra $\mathcal{A}_{d,{\bm{\alpha}}}$ in more
detail. As a main result, we obtain the Castelnuovo–Mumford regularity of
$\mathcal{A}_{d,{\bm{\alpha}}}$ explicitly in 5.6. This generalizes the result
[MR2955237, Theorem 4.2] of Nitsche in the case of the $d$-th Veronese
subring. We then offer an effective bound on the multiplicity of
$\mathcal{A}_{d,{\bm{\alpha}}}$ in 5.14.

This work is organized as follows. In Section 2, we recall some essential
definitions and terminology that we will need later. In Section 3, we use the
combinatorial structure of the sorting operation to study the algebra
$\mathcal{A}_{d,{\bm{\alpha}}}$. From the initial ideal of the presentation
ideal $J$ of $\mathcal{A}_{d,{\bm{\alpha}}}$, we introduce a structural graph
$\mathcal{G}_{d,{\bm{\alpha}}}$ and study its maximal cliques. As a result, we
derive the generators of the Alexander dual of $\operatorname{in}(J)$ in 3.10.
In Section 4, we propose a carefully constructed order in 4.13. With it, we
show in 4.21 that this Alexander dual ideal has linear quotients.
Combinatorial details of the quotients are also presented in this section.
Finally, in Section 5, we gather all the tools and results and present the two
main theorems mentioned above.

##  2\. Preliminaries

Throughout this paper, we fix a positive integer $n\geq 2$. Following the
convention, $[n]$ stands for the set $\\{1,2,\dots,n\\}$. Let
$S={\mathbb{K}}[x_{1},\dots,x_{n}]$ be a polynomial ring over a field
${\mathbb{K}}$, and $\mathfrak{S}_{n}$ be the symmetric group of $[n]$.

######  Notation 2.1.

  1. a

Let ${\bm{a}}\in{\mathbb{Z}}^{n}$ be a tuple written in boldface. Unless
otherwise stated, we usually write $a_{i}$ correspondingly with subscript, not
in boldface, for its $i$-th coordinate. Namely, we expect that
${\bm{a}}=(a_{1},\dots,a_{n})\in{\mathbb{Z}}^{n}$. Following this convention,
if we encounter several tuples
${\bm{a}}^{1},\dots,{\bm{a}}^{t}\in{\mathbb{Z}}^{n}$, we will have
${\bm{a}}^{i}=(a_{1}^{i},\dots,a_{n}^{i})$ for each $i\in[t]$.

  2. b

Suppose that ${\bm{a}}\in{\mathbb{N}}^{n}$. We will write ${\bm{x}}^{\bm{a}}$
for the monomial $x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$ in $S$ and define
$|{\bm{a}}|\coloneqq a_{1}+\cdots+a_{n}$.

  3. c

Let $I$ be a monomial ideal of $S$. We write $G(I)$ for the minimal monomial
generating set of $I$, and $\mu(I)=\\#G(I)$ for the minimal number of
generators.

Recall that Sturmfels introduced in [Sturmfels, Chapter 14] a sorting operator
for monomials of the same degree.

######  Definition 2.2.

  1. i

Let $\operatorname{Mon}_{d}$ be the set of monomials of degree $d$ in
$S={\mathbb{K}}[x_{1},\dots,x_{n}]$. Then, we have the _sorting operator_ for
$p\geq 2$:

$\operatorname{sort}:\underbrace{\operatorname{Mon}_{d}\times\cdots\times\operatorname{Mon}_{d}}_{\text{$p$
times}}\to\underbrace{\operatorname{Mon}_{d}\times\cdots\times\operatorname{Mon}_{d}}_{\text{$p$
times}},\qquad(u_{1},\dots,u_{p})\mapsto(v_{1},\dots,v_{p}),$

which is defined as follows. Suppose that $u_{1}\cdots
u_{p}=x_{i_{1}}x_{i_{2}}\cdots x_{i_{pd}}$ with $i_{1}\leq i_{2}\leq\cdots\leq
i_{pd}$. Then, $v_{k}\coloneqq x_{i_{k}}x_{i_{p+k}}\cdots x_{i_{(d-1)p+k}}$
for $k\in[p]$. The sequence $(u_{1},\dots,u_{p})$ of monomials in
$\operatorname{Mon}_{d}$ is called _sorted_ if
$\operatorname{sort}(u_{1},\dots,u_{p})=(u_{1},\dots,u_{p})$. A subset $U$ of
$V_{n,d}$ is _sortable_ if $\operatorname{sort}(U\times U)\subseteq U\times
U$.

  2. ii

Let $V_{n,d}\coloneqq\\{{\bm{a}}\in{\mathbb{N}}^{n}:|{\bm{a}}|=d\\}$. Since we
have a natural correspondence between
${\bm{x}}^{{\bm{a}}}\in\operatorname{Mon}_{d}$ and ${\bm{a}}\in V_{n,d}$, by
abuse of notation, we also derive a sorting operator

$\operatorname{sort}:V_{n,d}\times\cdots\times V_{n,d}\to
V_{n,d}\times\cdots\times V_{n,d}.$

Similarly, we can also talk about whether a subset of $V_{n,d}$ is sortable.

In this paper, we always assume the following.

######  Setting 2.3.

Suppose that $n\geq 3$. We fix a degree $d$ and a sequence
${\bm{\alpha}}=(\alpha_{1},\ldots,\alpha_{n})$ of integers with
$1\leq\alpha_{1}\leq\cdots\leq\alpha_{n}\leq d$ and $d<|{\bm{\alpha}}|$. Let
$V_{n,d}^{{\bm{\alpha}}}\coloneqq\Set{{\bm{c}}=(c_{1},\dots,c_{n})\in
V_{n,d}:c_{i}\leq\alpha_{i}\text{ for all $i$}}$. Furthermore, let
$I_{d,{\bm{\alpha}}}\coloneqq\braket{{\bm{x}}^{{\bm{c}}}:{\bm{c}}\in
V_{n,d}^{{\bm{\alpha}}}}$ be the Veronese type ideal in $S$, and
$\mathcal{A}_{d,{\bm{\alpha}}}=\mathbb{K}[I_{d,{\bm{\alpha}}}]$ be the
Veronese type algebra.

######  Remark 2.4.

  1. a

When $n=2$, it is not difficult to see that the Veronese type algebra
$\mathcal{A}_{d,{\bm{\alpha}}}$ is isomorphic to a Veronese ring, up to a
shift.

  2. b

If $d=|{\bm{\alpha}}|$, then the Veronese type algebra
$\mathcal{A}_{d,{\bm{\alpha}}}$ is generated principally by the monomial
${\bm{x}}^{{\bm{\alpha}}}$.

######  Remark 2.5.

Let $\mathcal{A}_{d,{\bm{\alpha}}}$ be the Veronese type algebra in 2.3. Since
$V_{n,d}^{{\bm{\alpha}}}$ is sortable by [MR2850142, Proposition 6.11], the
set

$\mathscr{J}\coloneqq\Set{\underline{T_{{\bm{a}}^{1}}T_{{\bm{a}}^{2}}}-T_{{\bm{b}}^{1}}T_{{\bm{b}}^{2}}:{\bm{a}}^{1},{\bm{a}}^{2}\in
V_{n,d}^{{\bm{\alpha}}},\text{ $({\bm{a}}^{1},{\bm{a}}^{2})$ unsorted and
$\operatorname{sort}({\bm{a}}^{1},{\bm{a}}^{2})=({\bm{b}}^{1},{\bm{b}}^{2})$}}$

is a Gröbner basis of the presentation ideal $J$ of
$\mathcal{A}_{d,{\bm{\alpha}}}$ with respect to a term order such that the
marked (underlined) monomials are the leading terms by [MR2850142, Theorem
6.16]. In particular, $J$ has a quadratic squarefree initial ideal.
Consequently, $\mathcal{A}_{d,{\bm{\alpha}}}$ is a Cohen–Macaulay Koszul
normal domain, by [MR2850142, Theorems 5.16, 5.17, and 6.7].

######  Proposition 2.6.

Let $\mathcal{A}_{d,{\bm{\alpha}}}$ be the Veronese type algebra in 2.3. Then,
$\operatorname{dim}(\mathcal{A}_{d,{\bm{\alpha}}})=n$.

###### Proof.

By assumption, we have $d<|{\bm{\alpha}}|$. Since $I_{d,{\bm{\alpha}}}$ is
equigenerated, the dimension of $\mathcal{A}_{d,{\bm{\alpha}}}$ equals the
rank of the matrix ${\bm{M}}_{d,{\bm{\alpha}}}$ whose rows are the exponent
vectors of the monomial generators of $I_{d,{\bm{\alpha}}}$ (see [MR2266432,
Exercise 8.21]). Based on this, we consider two cases.

  1. i

Suppose that $d<n$. Then, let ${\bm{\alpha}}^{\prime}=(1,1,\dots,1)$. Since
the corresponding matrix ${\bm{M}}_{d,{\bm{\alpha}}^{\prime}}$ is a submatrix
of ${\bm{M}}_{d,{\bm{\alpha}}}$, it remains to show that
$\operatorname{rank}({\bm{M}}_{d,{\bm{\alpha}}^{\prime}})=n$, or equivalently,
$\operatorname{dim}(\mathcal{A}_{d,{\bm{\alpha}}^{\prime}})=n$. Notice that
$I_{d,{\bm{\alpha}}^{\prime}}$ is a strongly symmetric shifted ideal. That
$\operatorname{dim}(\mathcal{A}_{d,{\bm{\alpha}}^{\prime}})=n$ follows from
[arXiv:2208.10476, Proposition 3.29].

  2. ii

Suppose that $d\geq n$. Then, we can find suitable ${\bm{\alpha}}^{\prime}$
such that $1\leq\alpha_{i}^{\prime}\leq\alpha_{i}$ for all $i$ and
$d=|{\bm{\alpha}}^{\prime}|-1$. Since the corresponding matrix
${\bm{M}}_{d,{\bm{\alpha}}^{\prime}}$ is a submatrix of
${\bm{M}}_{d,{\bm{\alpha}}}$, it remains to show that
$\operatorname{rank}({\bm{M}}_{d,{\bm{\alpha}}^{\prime}})=n$. Let
${\bm{e}}^{i}$ be the $i$-th standard basis of ${\mathbb{Z}}^{n}$ for $1\leq
i\leq n$. It is not difficult to see that
${\bm{M}}_{d,{\bm{\alpha}}^{\prime}}$ is an $n\times n$ matrix, whose rows
take the form ${\bm{\alpha}}^{\prime}-{\bm{e}}^{i}$ for $i=1,\ldots,n$. It is
then an elementary task to show that
${\bm{\alpha}}^{\prime}-{\bm{e}}^{1},\dots,{\bm{\alpha}}^{\prime}-{\bm{e}}^{n}$
are linearly independent. Say,
$\sum_{i}k_{i}({\bm{\alpha}}^{\prime}-{\bm{e}}^{i})={\bm{0}}$ for suitable
$k_{i}\in{\mathbb{R}}$. Thus,
$\sum_{i}k_{i}{\bm{e}}^{i}=(\sum_{i}k_{i}){\bm{\alpha}}^{\prime}$ and
consequently $\sum_{i}k_{i}=(\sum_{i}k_{i})|{\bm{\alpha}}^{\prime}|$. If
$\sum_{i}k_{i}=0$, then
$\sum_{i}k_{i}{\bm{e}}^{i}=(\sum_{i}k_{i}){\bm{\alpha}}^{\prime}={\bm{0}}$. As
a result, each $k_{i}=0$. If instead that $\sum_{i}k_{i}\neq 0$, then
$|{\bm{\alpha}}^{\prime}|=1$, which contradicts the assumption that
$|{\bm{\alpha}}^{\prime}|-1=d\geq n\geq 3$. ∎

##  3\. Maximal cliques

Let $\mathcal{A}_{d,{\bm{\alpha}}}$ be the Veronese type algebra in 2.3. In
one of the main results of this paper, we determine the Castelnuovo–Mumford
regularity of the algebra $\mathcal{A}_{d,{\bm{\alpha}}}$. Recall that if
$\beta_{i,j}$ is the graded Betti number of $\mathcal{A}_{d,{\bm{\alpha}}}$
considered as a ${\mathbb{K}}[{\bm{T}}]$-module, then the Castelnuovo–Mumford
regularity of $\mathcal{A}_{d,{\bm{\alpha}}}$ is defined to be

$\operatorname{reg}(\mathcal{A}_{d,{\bm{\alpha}}})\coloneqq\max_{i,j}\Set{j-i:\beta_{i,j}\neq
0}.$

Our exploration of the Castelnuovo–Mumford regularity depends on the following
key observations.

######  Observation 3.1.

Let $J$ be the presentation ideal of $\mathcal{A}_{d,{\bm{\alpha}}}$ generated
by the set $\mathscr{J}$ in 2.5. Since $\mathcal{A}_{d,{\bm{\alpha}}}$ is
Cohen–Macaulay and $\operatorname{in}(J)$ is squarefree by 2.5, it follows
from [CV, Corollary 2.7] that the quotient ring
${\mathbb{K}}[{\bm{T}}]/\operatorname{in}(J)$ is Cohen–Macaulay. Let
$(\operatorname{in}(J))^{\vee}$ be the Alexander dual of the squarefree ideal
$\operatorname{in}(J)$. By [CV, Corollary 2.7] and [MR2724673, Proposition
8.1.10],
$\operatorname{reg}(\mathcal{A}_{d,{\bm{\alpha}}})=\operatorname{reg}({\mathbb{K}}[{\bm{T}}]/J)=\operatorname{reg}({\mathbb{K}}[{\bm{T}}]/\operatorname{in}(J))=\operatorname{pd}((\operatorname{in}(J))^{\vee})$.

Inspired by the above observation, we turn to find the projective dimension of
$(\operatorname{in}(J))^{\vee}$. To do this, we proceed as follows. First,
since ${\mathbb{K}}[{\bm{T}}]/\operatorname{in}(J)$ is Cohen–Macaulay,
$(\operatorname{in}(J))^{\vee}$ is an equigenerated ideal. We will describe
the minimal monomial generators of this ideal as the maximal cliques of length
$n$ of some graph in 3.5. Then, in Section 4, we give a total order on the
minimal monomial generating set $G((\operatorname{in}(J))^{\vee})$ and show
that $(\operatorname{in}(J))^{\vee}$ has linear quotients with respect to this
order. Details of these quotients are important by the following lemma.

######  Lemma 3.2 ([MR2724673, Corollary 8.2.2]).

Let $I$ be an equigenerated ideal in the polynomial ring $S$. Suppose that the
minimal generating set $G(I)$ consists of $f_{1},\dots,f_{m}$ such that
$Q_{i}\coloneqq\braket{f_{1},\dots,f_{i-1}}:_{S}f_{i}$ is linear for each $i$.
Let $p=\max_{i}\mu(Q_{i})$ be the maximum of the minimal numbers of generators
of the successive linear quotient ideals. Then, the top nonzero total Betti
number of $I$ is $\beta_{p}(I)$, which has the value
$\\#\Set{i:\mu(Q_{i})=p}$. In particular, the projective dimension of $I$ is
given by $p$.

######  Definition 3.3.

  1. a

Recall that $V_{n,d}$ is the set
$\\{{\bm{a}}\in{\mathbb{N}}^{n}:|{\bm{a}}|=d\\}$. For any distinct
${\bm{a}},{\bm{b}}\in V_{n,d}$, we write
${\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}$ if the leftmost nonzero entry of
${\bm{a}}-{\bm{b}}$ is positive.

  2. b

Let ${\bm{\eta}}=(\eta_{1},\dots,\eta_{n})$ be the smallest tuple in
$V_{n,d}^{{\bm{\alpha}}}$ with respect to $>_{{\operatorname{lex}}}$, namely,
if ${\bm{a}}\in V_{n,d}^{{\bm{\alpha}}}$, then
${\bm{a}}\geq_{{\operatorname{lex}}}{\bm{\eta}}$. It is clear that
$\eta_{n}=\alpha_{n}$ and
$\eta_{i}=\min\\{\alpha_{i},d-\eta_{n}-\eta_{n-1}-\cdots-\eta_{i+1}\\}$ for
$i=n-1,n-2,\dots,1$.

  3. c

Let $\mathcal{G}=\mathcal{G}(d,{\bm{\alpha}})$ be a simple graph on the set
$V_{n,d}^{{\bm{\alpha}}}$, such that $\\{{\bm{a}},{\bm{b}}\\}$ with
${\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}$ is an edge if and only if
$({\bm{a}},{\bm{b}})$ is sorted. A _clique_ of $\mathcal{G}$ is a collection
of vertices, in which, every two different vertices are adjacent. A _maximal
clique_ is a clique that is maximal with respect to inclusion. Let
$\operatorname{MC}(\mathcal{G})=\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}))$
be the set of maximal cliques of $\mathcal{G}$.

######  Remark 3.4.

  1. a

If $({\bm{a}},{\bm{b}})$ is a sorted pair in $V_{n,d}$, then
${\bm{a}}\geq_{{\operatorname{lex}}}{\bm{b}}$.

  2. b

The fact (ii) before [Sturmfels, Theorem 14.2] can be restated as follows.
Suppose that
$\\{{\bm{a}}^{1}>_{{\operatorname{lex}}}{\bm{a}}^{2}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{s}\\}$
is a subset of $V_{n,d}^{{\bm{\alpha}}}$ such that
$\operatorname{sort}({\bm{a}}^{i},{\bm{a}}^{j})=({\bm{a}}^{i},{\bm{a}}^{j})$
for all $1\leq i<j\leq s$. Then,
$\operatorname{sort}({\bm{a}}^{1},{\bm{a}}^{2},\dots,{\bm{a}}^{s})=({\bm{a}}^{1},{\bm{a}}^{2},\dots,{\bm{a}}^{s})$.
In other words, sorted subsets of $V_{n,d}^{{\bm{\alpha}}}$ are precisely
cliques in $\mathcal{G}$.

  3. c

It follows from the description in 2.5 and the fact just stated in b that the
squarefree monomial ideal $\operatorname{in}(J)$ is the edge ideal of the
complement graph $\mathcal{G}^{\complement}$. Suppose that
$T_{{\bm{a}}^{1}}T_{{\bm{a}}^{2}}\cdots T_{{\bm{a}}^{m}}\in
G(\operatorname{in}(J)^{\vee})$ is a minimal monomial generator of the
Alexander dual ideal. This is equivalent to saying that
$\\{{\bm{a}}^{1},\dots,{\bm{a}}^{m}\\}$ is a minimal vertex cover of the
complement graph $\mathcal{G}^{\complement}$, by [MR2724673, Corollary 9.1.5].
In other words, the set complement
$\\{{\bm{a}}^{1},\dots,{\bm{a}}^{m}\\}^{\complement}$ is a maximal clique of
$\mathcal{G}$.

Consequently, in this section, we turn to the study of the maximal cliques.

######  Proposition 3.5.

Every maximal clique of $\mathcal{G}$ has cardinality $n$.

###### Proof.

The Veronese type algebra $\mathcal{A}_{d,{\bm{\alpha}}}$ is Cohen–Macaulay by
2.5. In other words, the presentation ideal $J$ is Cohen–Macaulay. Since
$\operatorname{in}(J)$ is squarefree, this implies that $\operatorname{in}(J)$
is Cohen–Macaulay by [CV, Corollary 2.7]. In particular,
$\operatorname{in}(J)$ is height unmixed. Notice that
$\operatorname{ht}(\operatorname{in}(J))=\operatorname{ht}(J)=\\#{\bm{T}}-n$
by 2.6, where $\\#{\bm{T}}$ is the number of variables in
${\mathbb{K}}[{\bm{T}}]$, i.e., the dimension of this polynomial ring.
Consequently, every minimal monomial generator of
$\operatorname{in}(J)^{\vee}$ has degree $\\#{\bm{T}}-n$, and every maximal
clique has size $\\#{\bm{T}}-(\\#{\bm{T}}-n)=n$ by 3.4 c. ∎

We need more tools to describe these maximal cliques in detail.

######  Definition 3.6.

Let ${\bm{a}},{\bm{b}}\in{\mathbb{Z}}^{n}$ be two tuples. Suppose that the
following condition is satisfied.

  1. (S):

There exist $1\leq i_{1}<i_{2}<\cdots<i_{2k-1}<i_{2k}\leq n$ such that
$b_{i_{2j-1}}=a_{i_{2j-1}}-1$ while $b_{i_{2j}}=a_{i_{2j}}+1$ for $1\leq j\leq
k$. Furthermore, for $t\in[n]\setminus\\{i_{1},i_{2},\dots,i_{2k}\\}$, one has
$b_{t}=a_{t}$.

In this case, the _sorting signature set_ $\Delta({\bm{a}},{\bm{b}})$ of this
pair is defined to be

$\Delta({\bm{a}},{\bm{b}})\coloneqq\bigcup_{j=1}^{k}[i_{2j-1},i_{2j}),$

which is considered as the union of intervals on the real line. Consequently,
the _length_ of this set is $\sum_{j=1}^{k}(i_{2j}-i_{2j-1})$, denoted by
$\operatorname{length}(\Delta({\bm{a}},{\bm{b}}))$.

From the definition, we can directly verify the following simple fact.

######  Lemma 3.7.

Let ${\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}$ be two tuples in $V_{n,d}$.
Then, $\operatorname{sort}({\bm{a}},{\bm{b}})=({\bm{a}},{\bm{b}})$ if and only
if the condition (S) is satisfied.

The following are further important observations when using the sorting
operator.

######  Lemma 3.8.

If
$\\{{\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}>_{{\operatorname{lex}}}{\bm{c}}\\}$
is a sorted subset in $V_{n,d}$, then
$\Delta({\bm{a}},{\bm{c}})=\Delta({\bm{a}},{\bm{b}})\sqcup\Delta({\bm{b}},{\bm{c}})$.

###### Proof.

It suffices to show that
$\Delta({\bm{a}},{\bm{b}})\cap\Delta({\bm{b}},{\bm{c}})=\emptyset$. Suppose
for contradiction that
$\Delta({\bm{a}},{\bm{b}})\cap\Delta({\bm{b}},{\bm{c}})$ is not empty. Then,
we can find suitable intersecting $[i_{2j-1},i_{2j})$ and
$[i_{2j^{\prime}-1}^{\prime},i_{2j^{\prime}}^{\prime})$ in the definition of
$\Delta({\bm{a}},{\bm{b}})$ and $\Delta({\bm{b}},{\bm{c}})$ respectively. Let
$j$ and $j^{\prime}$ be the smallest such that this happens.

  1. a

Suppose that $i_{2j-1}=i_{2j^{\prime}-1}^{\prime}$. Whence
$b_{i_{2j-1}}=a_{i_{2j-1}}-1$ and $c_{i_{2j-1}}=b_{i_{2j-1}}-1$. This forces
$c_{i_{2j-1}}=a_{i_{2j-1}}-2$. Since condition (S) is not satisfied here, we
have a contradiction to the assumption that $({\bm{a}},{\bm{c}})$ is a sorted
pair by 3.7.

  2. b

Suppose that $i_{2j-1}<i_{2j^{\prime}-1}^{\prime}<i_{2j}$. Now, we derive
$i_{2j^{\prime}-2}^{\prime}\leq i_{2j-1}$ from the minimality assumption. From
the interval positions, it is clear that
$a_{i_{2j^{\prime}-1}^{\prime}}=b_{i_{2j^{\prime}-1}^{\prime}}=c_{i_{2j^{\prime}-1}^{\prime}}+1$
and consequently
$a_{i_{2j^{\prime}-1}^{\prime}}+b_{i_{2j^{\prime}-1}^{\prime}}+c_{i_{2j^{\prime}-1}^{\prime}}\equiv
2\pmod{3}$. Meanwhile, it is not difficult to check that $-1+\sum_{k\leq
i_{2j-1}}a_{k}=\sum_{k\leq i_{2j-1}}b_{k}=\sum_{k\leq i_{2j-1}}c_{k}$.
Furthermore, we have $a_{t}=b_{t}=c_{t}$ for
$i_{2j-1}<t<i_{2j^{\prime}-1}^{\prime}$. Whence, the sorting operator will
produce
$a_{i_{2j^{\prime}-1}^{\prime}}+1=b_{i_{2j^{\prime}-1}^{\prime}}=c_{i_{2j^{\prime}-1}^{\prime}}$,
which is a contradiction.

  3. c

Suppose that $i_{2j^{\prime}-1}^{\prime}<i_{2j-1}<i_{2j^{\prime}}^{\prime}$.
This case is similar to b above. ∎

######  Lemma 3.9.

  1. a

If
$\\{{\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}>_{{\operatorname{lex}}}{\bm{d}}\\}$
and
$\\{{\bm{b}}>_{{\operatorname{lex}}}{\bm{c}}>_{{\operatorname{lex}}}{\bm{d}}\\}$
are two cliques in $\mathcal{G}$, then
$\\{{\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}>_{{\operatorname{lex}}}{\bm{c}}>_{{\operatorname{lex}}}{\bm{d}}\\}$
is also a clique in $\mathcal{G}$.

  2. b

Symmetrically, if
$\\{{\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}>_{{\operatorname{lex}}}{\bm{c}}\\}$
and
$\\{{\bm{a}}>_{{\operatorname{lex}}}{\bm{c}}>_{{\operatorname{lex}}}{\bm{d}}\\}$
are two cliques in $\mathcal{G}$, then
$\\{{\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}>_{{\operatorname{lex}}}{\bm{c}}>_{{\operatorname{lex}}}{\bm{d}}\\}$
is also a clique in $\mathcal{G}$.

###### Proof.

By symmetry, we will only consider the first case. Since
$\Delta({\bm{a}},{\bm{b}})\cap\Delta({\bm{b}},{\bm{d}})=\emptyset$ while
$\Delta({\bm{b}},{\bm{c}})\subseteq\Delta({\bm{b}},{\bm{d}})$ by 3.8, we have
$\Delta({\bm{a}},{\bm{b}})\cap\Delta({\bm{b}},{\bm{c}})=\emptyset$. Then, we
can apply 3.7 and 3.8 to show that
$\operatorname{sort}({\bm{a}},{\bm{c}})=({\bm{a}},{\bm{c}})$ with
$\Delta({\bm{a}},{\bm{c}})=\Delta({\bm{a}},{\bm{b}})\sqcup\Delta({\bm{b}},{\bm{c}})$.
Whence,
$\\{{\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}>_{{\operatorname{lex}}}{\bm{c}}>_{{\operatorname{lex}}}{\bm{d}}\\}$
is a clique in $\mathcal{G}$. ∎

We know from 3.5 that every maximal clique has cardinality $n$. Additional
information can be drawn here.

######  Corollary 3.10.

For each maximal clique
$\\{{\bm{a}}^{1}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}\\}$
in $\mathcal{G}$, we have
$\operatorname{length}(\Delta({\bm{a}}^{i},{\bm{a}}^{j}))=j-i$ when $1\leq
i<j\leq n$. Furthermore, $\Delta({\bm{a}}^{1},{\bm{a}}^{n})=[1,n)$. In other
words, $a_{1}^{n}=a_{1}^{1}-1$, $a_{n}^{n}=a_{n}^{1}+1$ and
$a_{i}^{n}=a_{i}^{1}$ for $i\in\\{2,\dots,n-1\\}$.

###### Proof.

Since $\Delta({\bm{a}}^{1},{\bm{a}}^{n})\subseteq[1,n)$ and
$\operatorname{length}(\Delta({\bm{a}}^{1},{\bm{a}}^{n}))\geq\sum_{i=1}^{n-1}\operatorname{length}(\Delta({\bm{a}}^{i},{\bm{a}}^{i+1}))\geq
n-1$ by 3.8, the first two statements are clear. The last statement follows
from the definition of the sorting signature set. ∎

######  Corollary 3.11.

Let
$\\{{\bm{a}}^{1}>_{{\operatorname{lex}}}{\bm{a}}^{2}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}>_{{\operatorname{lex}}}{\bm{a}}^{n+1}\\}$
be a set of vertices in $\mathcal{G}$. Suppose that
$\\{{\bm{a}}^{1}>_{{\operatorname{lex}}}{\bm{a}}^{2}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}\\}$
is a maximal clique of $\mathcal{G}$ and
$\Delta({\bm{a}}^{1},{\bm{a}}^{2})=\Delta({\bm{a}}^{n},{\bm{a}}^{n+1})$. Then,
$\\{{\bm{a}}^{2}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}>_{{\operatorname{lex}}}{\bm{a}}^{n+1}\\}$
is also a maximal clique of $\mathcal{G}$.

###### Proof.

We have
$\Delta({\bm{a}}^{2},{\bm{a}}^{n})\sqcup\Delta({\bm{a}}^{n},{\bm{a}}^{n+1})=\Delta({\bm{a}}^{2},{\bm{a}}^{n})\sqcup\Delta({\bm{a}}^{1},{\bm{a}}^{2})=\Delta({\bm{a}}^{1},{\bm{a}}^{n})=[1,n)$
by 3.10. Thus, we can verify by definition that
$\Delta({\bm{a}}^{2},{\bm{a}}^{n+1})=[1,n)$. In particular,
$\\{{\bm{a}}^{2}>_{{\operatorname{lex}}}{\bm{a}}^{n+1}\\}$ is an edge of
$\mathcal{G}$ by 3.7. Now, as
$\\{{\bm{a}}^{2}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}\\}$
is a clique and $\\{{\bm{a}}^{n}>_{{\operatorname{lex}}}{\bm{a}}^{n+1}\\}$ is
an edge,
$\\{{\bm{a}}^{2}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}>_{{\operatorname{lex}}}{\bm{a}}^{n+1}\\}$
is also a maximal clique of $\mathcal{G}$ by 3.9. ∎

##  4\. Linear Quotients

In this section, we continue to assume that $\mathcal{A}_{d,{\bm{\alpha}}}$ is
the Veronese type algebra of 2.3 and ${\bm{\eta}}$ is the tuple given in 3.3.
As explained at the beginning of Section 3, we intend to show that the
Alexander dual ideal $(\operatorname{in}(J))^{\vee}$ has linear quotients.
This tactic allows us to have more control over its minimal free resolution.
In particular, we can explicitly calculate the Castelnuovo–Mumford regularity
of $\mathcal{A}_{d,{\bm{\alpha}}}$ in Section 5, and also give a reasonable
upper bound on its multiplicity.

To prove the linear quotient property, we need to impose a total order $\prec$
on the minimal monomial generating set $G(\operatorname{in}(J)^{\vee})$, such
that with respect to this order, the ideal $\operatorname{in}(J)^{\vee}$ has
linear quotients. Let $\operatorname{MC}(\mathcal{G})$ be the set of maximal
cliques of the graph $\mathcal{G}=\mathcal{G}(d,{\bm{\alpha}})$. As observed
in 3.4c,

$G(\operatorname{in}(J)^{\vee})=\Set{{\bm{T}}_{A^{\complement}}\coloneqq\prod_{v\in
V_{n,d}^{{\bm{\alpha}}}\setminus A}T_{v}:A\in\operatorname{MC}(\mathcal{G})}.$

Thus, we will consider the corresponding total order, still denoted by
$\prec$, on $\operatorname{MC}(\mathcal{G})$. By definition, we want to show
that the quotient ideal $\braket{{\bm{T}}_{B^{\complement}}:B\prec
A}:{\bm{T}}_{A^{\complement}}$ is generated by some ring variables of
${\mathbb{K}}[{\bm{T}}]$ for each $A\in\operatorname{MC}(\mathcal{G})$. Notice
that

$\braket{{\bm{T}}_{B^{\complement}}}:{\bm{T}}_{A^{\complement}}=\prod_{v\in
A\setminus B}T_{v}.$ (1)

Therefore, for any given maximal clique $B$ with $B\prec A$, it suffices to
find a suitable maximal clique $D$ with $D\prec A$ such that $A\setminus D$ is
a singleton set with $A\setminus D\subseteq A\setminus B$.

Unfortunately, the total order $\prec$ introduced here is really involved. We
have to postpone its debut to 4.13. Before that, we need to make some
preparations.

######  Definition 4.1.

  1. a

A priori, a maximal clique of the graph $\mathcal{G}$ is a set of vertices.
When we write a maximal clique
$A=({\bm{a}}^{1},{\bm{a}}^{2},\dots,{\bm{a}}^{n})$ in the tuple form, we
intend to indicate that
${\bm{a}}^{1}>_{\operatorname{lex}}{\bm{a}}^{2}>_{\operatorname{lex}}\cdots>_{\operatorname{lex}}{\bm{a}}^{n}$.

  2. b

Two maximal cliques $A=({\bm{a}}^{1},{\bm{a}}^{2},\dots,{\bm{a}}^{n})$ and
$B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})$ are called _equivalent_ , if and only if
${\bm{a}}^{1}={\bm{b}}^{1}$. It follows from 3.10 that this is also equivalent
to saying that ${\bm{a}}^{n}={\bm{b}}^{n}$. With respect to this binary
relation, we have _equivalence classes_. We will write $\mathcal{E}_{A}$ for
the equivalence class to which $A$ belongs.

  3. c

The _rank_ of a tuple ${\bm{a}}=(a_{1},\dots,a_{n})\in V_{n,d}$ (with respect
to the given tuple ${\bm{\eta}}$) is defined to be

$\operatorname{rank}({\bm{a}})\coloneqq\sum_{j=1}^{n-1}(a_{j}-\eta_{j})(n-j).$

It is clear that $\operatorname{rank}({\bm{\eta}})=0$. Furthermore, if
${\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}$ belong to some common maximal
clique of $\mathcal{G}$, then it is easy to verify directly that
$\operatorname{rank}({\bm{a}})=\operatorname{rank}({\bm{b}})+\operatorname{length}(\Delta({\bm{a}},{\bm{b}}))$.

  4. d

For each maximal clique $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$, we define the
_rank_ of $\mathcal{E}_{A}$ to be $\operatorname{rank}({\bm{a}}^{n})$. This is
well-defined, since if $B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})$ and $A$ are
equivalent, then ${\bm{b}}^{n}={\bm{a}}^{n}$.

  5. e

Suppose that $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$, where
${\bm{a}}^{i}=(a_{1}^{i},\dots,a_{n}^{i})\in{\mathbb{Z}}^{n}$ and
$\sum_{k}a_{k}^{i}=d$ for each $i\in[n]$. Assume that there exists a
permutation $(s_{1},\dots,s_{n-1})$ of $\\{1,2,\dots,n-1\\}$, written in one-
line notation, such that $\Delta({\bm{a}}^{i},{\bm{a}}^{i+1})=[s_{i},s_{i}+1)$
for $i\in[n-1]$. Then we say the tuple $(s_{1},\dots,s_{n-1})$ is the
_signature_ of $A$ and denote it by $\operatorname{sgn}(A)$. Of course, we are
mostly interested in the case where $A$ is a maximal clique of $\mathcal{G}$.
Whence, by 3.8 and 3.10, the signature of $A$ must exist.

  6. f

Let $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ be a maximal clique. If there exists
a maximal clique $B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})$ such that
$({\bm{a}}^{2},\dots,{\bm{a}}^{n})=({\bm{b}}^{1},\dots,{\bm{b}}^{n-1})$, then
we will say that $B$ is the _root_ of $A$ and write $B=rA$. It follows from
3.10 that if the root of $A$ exists, then it is unique.

######  Remark 4.2.

  1. a

For any ${\bm{a}}\in V_{n,d}^{\bm{\alpha}}$, if ${\bm{a}}\neq{\bm{\eta}}$, we
can find ${\bm{b}}\in V_{n,d}^{\bm{\alpha}}$ such that
${\bm{a}}>_{{\operatorname{lex}}}{\bm{b}}\geq_{{\operatorname{lex}}}{\bm{\eta}}$,
$\operatorname{sort}({\bm{a}},{\bm{b}})=({\bm{a}},{\bm{b}})$, and
$\operatorname{length}({\bm{a}},{\bm{b}})=1$. If we use this repeatedly, we
can find by induction ${\bm{b}}^{0},{\bm{b}}^{1},\dots,{\bm{b}}^{m}\in
V_{n,d}^{\bm{\alpha}}$ such that ${\bm{b}}^{0}={\bm{a}}$,
${\bm{b}}^{m}={\bm{\eta}}$ and
$\operatorname{rank}({\bm{b}}^{i})=\operatorname{rank}({\bm{b}}^{i+1})+1$ for
each $i$. In particular, $\operatorname{rank}({\bm{a}})=m\in{\mathbb{N}}$.

  2. b

For each maximal clique $A$, we have $\operatorname{rank}(A)\in{\mathbb{N}}$.

  3. c

If $B=rA$, then $\operatorname{rank}(A)=\operatorname{rank}(B)+1$.

  4. d

We have precisely one equivalence class $\mathcal{E}_{A}$ such that
$\operatorname{rank}(\mathcal{E}_{A})=0$. If
$B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})$ belongs to such $\mathcal{E}_{A}$, then
${\bm{b}}^{n}={\bm{\eta}}$.

Here is the converse of 3.10.

######  Lemma 4.3.

Let ${\bm{a}}^{1}=(a_{1}^{1},\dots,a_{n}^{1})$ be a tuple in
$V_{n,d}^{{\bm{\alpha}}}$. Suppose that $1\leq a_{1}^{1}$ while
$a_{n}^{1}\leq\alpha_{n}-1$. Then, there exists a maximal clique in
$\mathcal{G}$ of the form
$\Set{{\bm{a}}^{1}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}}$.

###### Proof.

It is clear that
${\bm{a}}^{n}\coloneqq(a_{1}^{1}-1,a_{2}^{1},\dots,a_{n-1}^{1},a_{n}^{1}+1)$
belongs to $V_{n,d}^{{\bm{\alpha}}}$, by assumption. Notice that
$\\{{\bm{a}}^{1}>_{{\operatorname{lex}}}{\bm{a}}^{n}\\}$ is a clique in
$\mathcal{G}$ and $\Delta({\bm{a}}^{1},{\bm{a}}^{n})=[1,n)$. Thus, we can
complete $\\{{\bm{a}}^{1}>_{{\operatorname{lex}}}{\bm{a}}^{n}\\}$ to a maximal
clique. This maximal clique must have the form
$\Set{{\bm{a}}^{1}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}}$,
due to 3.5 and the rank reason given at the end of 4.1c. ∎

Next, we describe a necessary and sufficient condition for a given maximal
clique $A$ such that $\operatorname{rank}(A)>0$ and $rA$ does not exist. This
characterization ensures that we pick the correct element when ordering for
the linear quotients.

######  Lemma 4.4.

Suppose that $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ is a maximal clique such
that ${\bm{a}}^{1}=(a_{1}^{1},\dots,a_{n}^{1})$ and
$\operatorname{sgn}(A)=(s_{1},\dots,s_{n-1})$. If $\operatorname{rank}(A)>0$,
then $rA$ does not exist, if and only if $a_{1}^{1}=1$ and $s_{1}=1$, or
$a_{n}^{1}=\alpha_{n}-1$ and $s_{1}=n-1$.

###### Proof.

Suppose that ${\bm{a}}^{2}=(a_{1}^{2},\dots,a_{n}^{2})$. Let ${\bm{a}}^{n+1}$
be the tuple such that $\Delta({\bm{a}}^{2},{\bm{a}}^{n+1})=[1,n)$. It is easy
to see that
${\bm{a}}^{n+1}=(a_{1}^{2}-1,a_{2}^{2},\dots,a_{n-1}^{2},a_{n}^{2}+1)$ and
$\Delta({\bm{a}}^{n},{\bm{a}}^{n+1})=[s_{1},s_{1}+1)$. Then, $rA$ does not
exist if and only if ${\bm{a}}^{2},\dots,{\bm{a}}^{n},{\bm{a}}^{n+1}$ is not a
legitimate maximal clique. By 3.11, the latter happens precisely when
${\bm{a}}^{n+1}\notin V_{n,d}^{{\bm{\alpha}}}$, which means either
$a_{1}^{2}=0$ or $a_{n}^{2}=\alpha_{n}$.

  1. a

Suppose that $a_{1}^{2}=0$. We claim that $s_{1}=1$. Otherwise, $s_{j}=1$ for
some $2\leq j\leq n-1$. This implies that ${\bm{a}}^{k}=(a_{1}^{2},\dots)$ for
$k=1,\dots,j$, and ${\bm{a}}^{k}=(a_{1}^{2}-1,\dots)$ for $k=j+1,\dots,n$. But
as $a_{1}^{2}-1=-1$ in this case, we have a contradiction. Now, since
$s_{1}=1$, it is clear that $a_{1}^{1}=1$.

  2. b

Suppose that $a_{n}^{2}=\alpha_{n}$. The argument is similar.

Conversely, if $a_{1}^{1}=1$ and $s_{1}=1$, or $a_{n}^{1}=\alpha_{n}-1$ and
$s_{1}=n-1$, then $a_{1}^{2}=0$ or $a_{n}^{2}=\alpha_{n}$. By the argument at
the beginning of this proof, $rA$ does not exist. ∎

To facilitate exhibiting the claimed linear quotients property, we need the
subsequent handy tool.

######  Lemma 4.5.

Let $A=({\bm{a}}^{1},\ldots,{\bm{a}}^{n})$ and
$B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})$ be two tuples of elements in
${\mathbb{Z}}^{n}$ such that ${\bm{a}}^{1}={\bm{b}}^{1}$ and
${\bm{a}}^{n}={\bm{b}}^{n}$. Suppose that
$\operatorname{sgn}(A)=(s_{1},\ldots,s_{n-1})$ and
$\operatorname{sgn}(B)=(t_{1},\ldots,t_{n-1})$. Then, the following conditions
are equivalent for an index $k\in[n-2]$:

  1. a

the signature $\operatorname{sgn}(B)$ takes the form
$(s_{1},\ldots,s_{k-1},s_{k+1},s_{k},s_{k+2},\dots,s_{n-1})$;

  2. b

the difference set
$\operatorname{diff}(A,B)\coloneqq\\{i:{\bm{a}}^{i}\neq{\bm{b}}^{i}\\}$ is
exactly $\\{k+1\\}$.

If in addition $A$ and $B$ are two maximal cliques in an equivalence class
$\mathcal{E}$, then the following is an additional equivalent condition:

  1. (3)

the quotient ideal
$\braket{{\bm{T}}_{B^{\complement}}}:_{{\mathbb{K}}[{\bm{T}}]}{\bm{T}}_{A^{\complement}}$
is generated by $T_{{\bm{a}}^{k+1}}$.

###### Proof.

Firstly, we show that a $\Rightarrow$ b. By assumption, we have
${\bm{a}}^{1}={\bm{b}}^{1}$ and $s_{i}=t_{i}$ for $i=1,2,\dots,k-1$. Since

$\Delta({\bm{a}}^{i},{\bm{a}}^{i+1})=[s_{i},s_{i}+1)=[t_{i},t_{i}+1)=\Delta({\bm{b}}^{i},{\bm{b}}^{i+1}),$

by induction, we have ${\bm{a}}^{j}={\bm{b}}^{j}$ for $j=1,2,\dots,k$.
Similarly, we have ${\bm{a}}^{n}={\bm{b}}^{n}$ and $s_{i}=t_{i}$ for
$i=n-1,n-2,\dots,k+2$ by assumption. Thus, we also have
${\bm{a}}^{j}={\bm{b}}^{j}$ for $j=n,n-1,\dots,k+2$. On the other hand, since
$s_{k}\neq t_{k}$ while ${\bm{a}}^{k}={\bm{b}}^{k}$, we have

$\Delta({\bm{a}}^{k},{\bm{a}}^{k+1})=[s_{k},s_{k}+1)\neq[t_{k},t_{k}+1)=\Delta({\bm{b}}^{k},{\bm{b}}^{k+1}),$

and hence ${\bm{a}}^{k+1}\neq{\bm{b}}^{k+1}$. It is now clear that
$\operatorname{diff}(A,B)=\\{k+1\\}$.

Secondly, we show that b $\Rightarrow$ a. By assumption, we have
${\bm{a}}^{j}={\bm{b}}^{j}$ whenever $j\neq k+1$. Since

$\bigsqcup_{j\leq
i}\,[s_{j},s_{j}+1)=\Delta({\bm{a}}^{1},{\bm{a}}^{i+1})=\Delta({\bm{b}}^{1},{\bm{b}}^{i+1})=\bigsqcup_{j\leq
i}\,[t_{j},t_{j}+1)$

for all $1\leq i\leq k-1$, we must have $s_{i}=t_{i}$ for each such $i$.
Similarly, we have $s_{i}=t_{i}$ when $k+2\leq i\leq n-1$, by looking at
$\Delta({\bm{a}}^{i},{\bm{a}}^{n})=\Delta({\bm{b}}^{i},{\bm{b}}^{n})$. Notice
that $\\{s_{1},\dots,s_{n-1}\\}=\\{1,\dots,n-1\\}=\\{t_{1},\dots,t_{n-1}\\}$.
Therefore, $\\{s_{k},s_{k+1}\\}=\\{t_{k},t_{k+1}\\}$. Since $A\neq B$, there
is only one possibility for this: $s_{k}=t_{k+1}$ and $s_{k+1}=t_{k}$.

Finally, assume that $A$ and $B$ are two maximal cliques in $\mathcal{E}$. The
equivalence of b and 3 is then clear from Equation 1. ∎

We need tools to determine whether a potential maximal clique is really
legitimate.

######  Definition 4.6.

Suppose that ${\bm{a}}=(a_{1},\dots,a_{n})\in V_{n,d}^{{\bm{\alpha}}}$. If
there exists some ${\bm{b}}\in V_{n,d}^{{\bm{\alpha}}}$ such that
$\Delta({\bm{a}},{\bm{b}})=[s,s+1)$, we say that we apply an _$s$ -jump_ to
${\bm{a}}$ in order to get ${\bm{b}}$. It is clear that such an operation
exists if and only if $a_{s}>0$ and $a_{s+1}<\alpha_{s+1}$.

######  Remark 4.7.

Suppose that $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ is a maximal clique and
$\operatorname{sgn}(A)=(s_{1},\dots,s_{n-1})$. For each $i,j\in[n]$, we have
$a_{j}^{i}\in\\{a_{j}^{1}-1,a_{j}^{1},a_{j}^{1}+1\\}$. The case
$a_{j}^{i}=a_{j}^{1}-1$ occurs if and only if the $j$-jump is applied before
${\bm{a}}^{i}$ (i.e., $j=s_{k}$ for some $k<i$), while the $(j-1)$-jump is not
applied before it. Similarly, the case $a_{j}^{i}=a_{j}^{1}+1$ happens if and
only if the $(j-1)$-jump is applied before ${\bm{a}}^{i}$, while the $j$-jump
is not applied before it.

######  Definition 4.8.

Let $\mathcal{E}$ be an equivalence class, in which, every maximal clique
starts with ${\bm{a}}^{1}=(a^{1}_{1},\dots,a^{1}_{n})$. We consider a partial
order $\triangleleft$ on $[n-1]$ with respect to $\mathcal{E}$ as follows.
Suppose that $i\in[n-1]$.

  * •

If $a_{i}^{1}=0$ and $i>1$, then we require that $(i-1)\,\triangleleft\,i$.

  * •

Likewise, if $a_{i+1}^{1}=\alpha_{i+1}$ and $i+1<n$, then we require that
$(i+1)\,\triangleleft\,i$.

After considering each $i\in[n-1]$, the underlined parts _generate_ a partial
order $\triangleleft$ on $[n-1]$. The induced poset will be called the _poset
of obstructions_ with respect to $\mathcal{E}$.

The next two lemmas justify the terminology of this poset from the point of
view of allowing permutations in $\mathfrak{S}_{n-1}$ to be legitimate
signatures.

######  Lemma 4.9.

The poset of 4.8 is well-defined. Furthermore, suppose that
$A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ is a maximal clique in $\mathcal{E}$ and
$\operatorname{sgn}(A)=(s_{1},\dots,s_{n-1})$. Then, the following condition
is satisfied:

  1. (PO):

whenever $s_{i}\,\triangleleft\,s_{j}$, we have $i<j$.

###### Proof.

For each $i\in[n-1]$, by definition, we apply an $s_{i}$-jump to
${\bm{a}}^{i}$ in order to get ${\bm{a}}^{i+1}$.

  * •

If $a_{s_{i}}^{1}=0$ and $s_{i}>1$, then we must have applied an
$(s_{i}-1)$-jump somewhere before the $s_{i}$-jump. Meanwhile, we require that
$(s_{i}-1)\,\triangleleft\,s_{i}$ in 4.8.

  * •

Likewise, if $a_{s_{i}+1}^{1}=\alpha_{s_{i}+1}$ and $s_{i}+1<n$, then we must
have applied an $(s_{i}+1)$-jump somewhere before the $s_{i}$-jump. Meanwhile,
we require that $(s_{i}+1)\,\triangleleft\,s_{i}$ in 4.8.

Note that we won’t have $s_{i}\,\triangleleft\,(s_{i}+1)$ and
$(s_{i}+1)\,\triangleleft\,s_{i}$ at the same time: the first requires the
$s_{i}$-jump to be applied before the $(s_{i}+1)$-jump in $A$, while the
second requires the opposite. This shows that the poset is well-defined. It is
also clear that the condition (PO) holds. ∎

######  Lemma 4.10.

Conversely, let ${\bm{s}}=(s_{1},\dots,s_{n-1})$ be a permutation of in
$\mathfrak{S}_{n-1}$. Suppose that the condition (PO) is satisfied by
${\bm{s}}$. Then, ${\bm{s}}$ is a legitimate signature with respect to
$\mathcal{E}$, namely, there exists some $A\in\mathcal{E}$ such that
$\operatorname{sgn}(A)={\bm{s}}$.

###### Proof.

Suppose that the maximal cliques in $\mathcal{E}$ all start with
${\bm{a}}^{1}$ and end with ${\bm{a}}^{n}$. It suffices to construct
${\bm{a}}^{2},\dots,{\bm{a}}^{n-1}\in V_{n,d}^{{\bm{\alpha}}}$, such that
$\Delta({\bm{a}}^{i-1},{\bm{a}}^{i})=[s_{i-1},s_{i-1}+1)$ when $i\geq 2$. We
do this by induction on $i$. The degenerate base case when $i=1$ is trivial.
Next, assume that ${\bm{a}}^{1},\dots,{\bm{a}}^{i-1}$ have been constructed
and $2\leq i\leq n-1$.

  1. a

If $a_{s_{i-1}}^{i-1}>0$ and $a_{s_{i-1}+1}^{i-1}<\alpha_{s_{i-1}+1}$, it is
clear that we can apply the $s_{i-1}$-jump to ${\bm{a}}^{i-1}$ to get a tuple
${\bm{a}}^{i}\in V_{n,d}^{{\bm{\alpha}}}$. Certainly
$\Delta({\bm{a}}^{i-1},{\bm{a}}^{i})=[s_{i-1},s_{i-1}+1)$.

  2. b

Suppose that $a_{s_{i-1}}^{i-1}=0$. As $a_{s_{i-1}}^{1}\geq 0$, we deduce that
$a_{s_{i-1}}^{i-1}\neq a_{s_{i-1}}^{1}+1$. Since ${\bm{s}}$ is a permutation,
we cannot apply the $s_{i-1}$-jump before ${\bm{a}}^{i-1}$. Thus, it follows
from 4.7 that we cannot use the $(s_{i-1}-1)$-jump before ${\bm{a}}^{i-1}$.

    1. i

Suppose that $s_{i-1}=1$. Whence, $s_{k}\neq 1$ for $k<i-1$. Consequently, we
deduce that $a_{1}^{1}=\cdots=a_{1}^{i-1}=0$. But this is impossible since it
is necessary that $a_{1}^{1}\geq 1$.

    2. ii

Suppose that $s_{i-1}>1$. If in addition $a_{s_{i-1}}^{1}=0$, we have
$(s_{i-1}-1)\,\triangleleft\,s_{i-1}$ from 4.8. Then, the condition (PO)
implies that the $(s_{i-1}-1)$-jump is applied before the $s_{i-1}$-jump,
i.e., the $(s_{i-1}-1)$-jump is applied before ${\bm{a}}^{i-1}$, a
contradiction. If instead $a_{s_{i-1}}^{1}>0$, then
$a_{s_{i-1}}^{i-1}=a_{s_{i-1}}^{1}-1$. It follows from 4.7 that the
$s_{i-1}$-jump is applied before ${\bm{a}}^{i-1}$, again a contradiction.

  3. c

Suppose that $a_{s_{i-1}+1}^{i-1}=\alpha_{s_{i-1}+1}$. We can argue as in the
previous case to see that this is impossible. ∎

The final step is to provide each equivalence class with additional
structures.

######  Remark 4.11.

Suppose that $i\,\triangleleft\,j$ in the poset of obstructions with respect
to $\mathcal{E}$. If $i<j$, then we have
$i\,\triangleleft\,(i+1)\,\triangleleft\,\cdots\,\triangleleft\,(j-1)\,\triangleleft\,j$.
If instead $i>j$, then we have
$i\,\triangleleft\,(i-1)\,\triangleleft\,\cdots\,\triangleleft\,(j+1)\,\triangleleft\,j$.

######  Definition 4.12.

Let $\mathcal{E}$ be an equivalence class of maximal cliques.

  1. i

In $\mathcal{E}$, we will take a maximal clique $L=L(\mathcal{E})$ as follows.
If $a_{1}^{1}=1$, then let $\kappa_{1}$ be the largest integer such that
$\kappa_{1}\leq n-1$ and $a_{2}^{1}=\cdots=a_{\kappa_{1}}^{1}=0$. When
$a_{2}^{1}>0$, we will simply take $\kappa_{1}=1$. Symmetrically, if
$a_{n}^{1}=\alpha_{n}-1$, then let $\kappa_{2}$ be the smallest integer such
that $\kappa_{2}\geq 2$ and $a_{j}^{1}=\alpha_{j}$ for all $\kappa_{2}\leq
j\leq n-1$. When $a_{n-1}^{1}<\alpha_{n-1}$, we will simply take
$\kappa_{2}=n$. It is clear that $\kappa_{1}<\kappa_{2}$ if both exist.
Furthermore, in 4.8, we have the relations
$1\,\triangleleft\,2\,\triangleleft\,\cdots\,\triangleleft\,\kappa_{1}$ and
$(n-1)\,\triangleleft\,(n-2)\,\triangleleft\,\cdots\,\triangleleft\,(\kappa_{2}-1)$.
Note that these relations are the only nontrivial ones that include the
integers $1,2,\dots,\kappa_{1}-1,\kappa_{2},\kappa_{2}+1,\dots,n-1$ in the
poset of obstructions with respect to $\mathcal{E}$. On the other hand,
although it is possible to have like
$(\kappa_{1}+1)\,\triangleleft\,\kappa_{1}$ or
$(\kappa_{2}-2)\,\triangleleft\,(\kappa_{2}-1)$ in the poset, we won’t have
any $t\in[n-1]$ such that either $\kappa_{1}\,\triangleleft\,t$ or
$(\kappa_{2}-1)\,\triangleleft\,t$, by the choice of $\kappa_{1}$ and
$\kappa_{2}$, as well as 4.11. Thus, we can choose an $L$ in $\mathcal{E}$
such that

$\qquad\qquad\operatorname{sgn}(L)\coloneqq\begin{cases}(\tau_{1},\dots,\tau_{\kappa_{2}-\kappa_{1}-2},\underbrace{n-1,n-2,\dots,\kappa_{2}-1},\underbrace{1,2,\dots,\kappa_{1}}),&\text{if
$\kappa_{1}<\kappa_{2}-1$,}\\\\[10.00002pt]
(\underbrace{n-1,n-2,\dots,\kappa_{2}},\underbrace{1,2,\dots,\kappa_{1}}),&\text{if
$\kappa_{1}=\kappa_{2}-1$}\end{cases}$

for suitable $\tau_{i}$’s that are compatible with the poset of obstructions.
In the case where $\kappa_{2}$ is not defined, namely when
$a_{n}^{1}<\alpha_{n}-1$, we can superficially assume that $\kappa_{2}=n+1$
and treat it as a degenerate case of the first one. Similarly, when
$\kappa_{1}$ is not defined, namely, when $a_{1}^{1}>1$, we can assume that
$\kappa_{1}=0$. A priori, the $\operatorname{sgn}(L)$ just constructed is only
a permutation in $\mathfrak{S}_{n-1}$. It is indeed a legal signature since
such a maximal clique $L$ exists by 4.10.

  2. ii

We will call $(\mathcal{E},L)$ a _marked equivalence class_. This is an
equivalence class with a chosen representative. Since we will take this
particular $L$ for this $\mathcal{E}$ once and for all in the rest of this
paper, we will simply write $(\mathcal{E},L)$ as $\mathcal{E}$.

  3. iii

Suppose that
${\bm{\tau}}\coloneqq\operatorname{sgn}(L)=(\tau_{1},\tau_{2},\ldots,\tau_{n-1})$.
Now, take any $A\in\mathcal{E}$ and assume that
$\operatorname{sgn}(A)=(k_{1},\dots,k_{n-1})$. Let $s_{i}$ be the index such
that $\tau_{s_{i}}=k_{i}$. We will say that the _relative signature of $A$
with respect to ${\bm{\tau}}$_ (or equivalently, with respect to $L$) is
$\operatorname{sgn}_{{\bm{\tau}}}(A)\coloneqq(s_{1},\dots,s_{n-1})$.
Obviously, $\operatorname{sgn}_{\bm{\tau}}(L)=(1,2,\dots,n-1)$.

Since we have all the necessary definitions and notations in place, we are
ready to state the order that gives rise to the linear quotient property.
Recall that $\operatorname{MC}(\mathcal{G})$ is the set of maximal cliques of
$\mathcal{G}$.

######  Setting 4.13 (Rules of order).

Let $\prec$ be a total order on $\operatorname{MC}(\mathcal{G})$ satisfying
the following conditions.

  1. a

If $\operatorname{rank}(B)<\operatorname{rank}(A)$, then $B\prec A$.

  2. b

Suppose that $\operatorname{rank}(B)=\operatorname{rank}(A)$,
$\mathcal{E}_{A}\neq\mathcal{E}_{B}$, and $B\prec A$. Then, for any
$A^{\prime}\in\mathcal{E}_{A}$ and $B^{\prime}\in\mathcal{E}_{B}$, we have
$B^{\prime}\prec A^{\prime}$. Therefore, $\prec$ also induces a total order on
the set of equivalence classes.

  3. c

Let $\mathcal{E}$ be an equivalence class and $L$ be the special maximal
clique we chose in 4.12. Suppose that
${\bm{\tau}}\coloneqq\operatorname{sgn}(L)=(\tau_{1},\dots,\tau_{n-1})$. The
restriction of $\prec$ to $\mathcal{E}$ is given by the lexicographical order
with respect to $\tau_{1}<\tau_{2}<\cdots<\tau_{n-1}$. In other words, if
$A,B\in\mathcal{E}$, then $B\prec A$ if and only if the first nonzero entry of
$\operatorname{sgn}_{{\bm{\tau}}}(B)-\operatorname{sgn}_{{\bm{\tau}}}(A)$ is
negative.

Such a total order $\prec$ exists, but in general, it is not unique. In the
rest of this paper, we will simply fix one that works.

######  Example 4.14.

We present here an example showing how the maximal cliques in a marked
equivalence class $(\mathcal{E},L)$ are ordered according to 4.13. Consider
$n=5$, $d=8$, and ${\bm{\alpha}}=(2,2,2,3,3)$. Let $\mathcal{E}$ be the
equivalence containing

$A=((1,1,1,3,2),(0,2,1,3,2),(0,1,2,3,2),(0,1,2,2,3),(0,1,1,3,3)).$

Write $A=({\bm{a}}^{1},\dots,{\bm{a}}^{5})$. Note that $rA$ does not exist.
This is because if $\Delta({\bm{a}}^{2},{\bm{a}}^{5+1})=[1,5)$, then
${\bm{a}}^{5+1}=(-1,2,1,3,3)$, which does not belong to
$V_{n,d}^{{\bm{\alpha}}}$. Using the notation in 4.12, we have $\kappa_{1}=1$
and $\kappa_{2}=4$. Consequently, we choose a maximal clique $L$ with
${\bm{\tau}}\coloneqq\operatorname{sgn}(L)=(2,4,3,1)$. Since ${\bm{a}}^{1}$ is
given, we have

$L=((1,1,1,3,2),(1,0,2,3,2),(1,0,2,2,3),(1,0,1,3,3),(0,1,1,3,3))$

for our equivalence class $\mathcal{E}$.

The poset of obstructions, defined in 4.8, contains only the nontrivial
relation $4\,\triangleleft\,3$. As a result, we have exactly $4!/2=12$ maximal
cliques in the equivalence class $\mathcal{E}$. In Table 1, we list all their
signatures and their relative signatures with respect to ${\bm{\tau}}$.

Table 1. Ordered maximal cliques in an equivalence class

| $\operatorname{sgn}(A)$ | $\operatorname{sgn}_{{\bm{\tau}}}(A)$
---|---|---
$1$ | $(2,4,3,1)$ | $(1,2,3,4)$
$2$ | $(2,4,1,3)$ | $(1,2,4,3)$
$3$ | $(2,1,4,3)$ | $(1,4,2,3)$
$4$ | $(4,2,3,1)$ | $(2,1,3,4)$
$5$ | $(4,2,1,3)$ | $(2,1,4,3)$
$6$ | $(4,3,2,1)$ | $(2,3,1,4)$

| $\operatorname{sgn}(A)$ | $\operatorname{sgn}_{{\bm{\tau}}}(A)$
---|---|---
$7$ | $(4,3,1,2)$ | $(2,3,4,1)$
$8$ | $(4,1,2,3)$ | $(2,4,1,3)$
$9$ | $(4,1,3,2)$ | $(2,4,3,1)$
$10$ | $(1,2,4,3)$ | $(4,1,2,3)$
$11$ | $(1,4,2,3)$ | $(4,2,1,3)$
$12$ | $(1,4,3,2)$ | $(4,2,3,1)$

Due to lack of space, we will not explicitly list every maximal clique in this
equivalence class. We only mention one here for illustration. Since every such
maximal clique starts with ${\bm{a}}^{1}=(1,1,1,3,2)$, the maximal clique $B$
satisfying $\operatorname{sgn}(B)=(1,4,2,3)$ is

$B=((1,1,1,3,2),(0,2,1,3,2),(0,2,1,2,3),(0,1,2,2,3),(0,1,1,3,3)).$

We can then check that $\operatorname{sgn}_{{\bm{\tau}}}(B)=(4,2,1,3)$.

The rest of this section is devoted to showing the linear quotient property
with respect to the order $\prec$ introduced in 4.13. Let $A$ be a maximal
clique. Given Equation 1, to show that the quotient ideal
$\braket{{\bm{T}}_{B^{\complement}}:B\prec A}:{\bm{T}}_{A^{\complement}}$ is
linear, we show that for every maximal clique $B\prec A$, we can find $C\prec
A$ such that $\\#\operatorname{diff}(A,C)=1$ and
$\operatorname{diff}(A,C)\subseteq\operatorname{diff}(A,B)$. The following
technical lemma constructs the candidate maximal cliques that we will need in
the later proof.

######  Lemma 4.15.

Suppose that $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ and
$B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})$ are two different maximal cliques in the
same equivalence class $\mathcal{E}$ such that
$\operatorname{sgn}(A)=(s_{1},\dots,s_{n-1})$ and
$\operatorname{sgn}(B)=(t_{1},\dots,t_{n-1})$. Suppose that $s_{i}=t_{i}$ for
$i\in\\{1,2,\dots,k\\}\cup\\{\ell,\ell+1,\dots,n-1\\}$ and $s_{k+1}\neq
t_{k+1}$; we allow $\ell=n$ so that the part $\\{\ell,\ell+1,\dots,n-1\\}$
disappears. Then, we can find maximal cliques $C,D\in\mathcal{E}$ such that

$\operatorname{sgn}(C)=(s_{1},\dots,s_{k},s_{k+1},t_{k+1},p_{k+3},\dots,p_{\ell-1},s_{\ell},\dots,s_{n-1})$

and

$\operatorname{sgn}(D)=(s_{1},\dots,s_{k},t_{k+1},s_{k+1},q_{k+3},\dots,q_{\ell-1},s_{\ell},\dots,s_{n-1})$

for suitable $p_{i}$’s and $q_{i}$’s.

###### Proof.

Suppose that ${\bm{a}}^{k+1}=(a_{1}^{k+1},\dots,a_{n}^{k+1})$. Then

${\bm{a}}^{k+2}=(a_{1}^{k+1},\dots,a_{s_{k+1}-1}^{k+1},a_{s_{k+1}}^{k+1}-1,a_{s_{k+1}+1}^{k+1}+1,a_{s_{k+1}+2}^{k+1},\dots,a_{n}^{k+1}).$

Since ${\bm{a}}^{1}={\bm{b}}^{1}$ and $s_{i}=t_{i}$ for $i\in[k]$, we have
${\bm{b}}^{k+1}={\bm{a}}^{k+1}$ and consequently

${\bm{b}}^{k+2}=(a_{1}^{k+1},\dots,a_{t_{k+1}-1}^{k+1},a_{t_{k+1}}^{k+1}-1,a_{t_{k+1}+1}^{k+1}+1,a_{t_{k+1}+2}^{k+1},\dots,a_{n}^{k+1}).$

Without loss of generality, we can assume that $s_{k+1}<t_{k+1}$.

  1. a

Suppose that $s_{k+1}+1=t_{k+1}$. Let ${\bm{c}}^{k+3}$ be the tuple such that
$\Delta({\bm{a}}^{k+2},{\bm{c}}^{k+3})=[t_{k+1},t_{k+1}+1)$, namely,

${\bm{c}}^{k+3}=(a_{1}^{k+1},\dots,a_{s_{k+1}-1}^{k+1},a_{s_{k+1}}^{k+1}-1,a_{s_{k+1}+1}^{k+1},a_{s_{k+1}+2}^{k+1}+1,a_{s_{k+1}+3}^{k+1},\dots,a_{n}^{k+1}).$

Due to the existence of ${\bm{a}}^{k+2}$ and ${\bm{b}}^{k+2}$, it can be
verified that ${\bm{c}}^{k+3}\in V_{n,d}^{{\bm{\alpha}}}$. Furthermore,
$\Delta({\bm{c}}^{k+3},{\bm{a}}^{\ell})=\Delta({\bm{a}}^{k+1},{\bm{a}}^{\ell})\setminus[s_{k+1},s_{k+1}+2)$.
Whence,
${\bm{a}}^{k+2}>_{{\operatorname{lex}}}{\bm{c}}^{k+3}>_{{\operatorname{lex}}}{\bm{a}}^{\ell}$
is a clique in $\mathcal{G}$. It is then not difficult to see that
${\bm{a}}^{1}>_{{\operatorname{lex}}}\dots>_{{\operatorname{lex}}}{\bm{a}}^{k+2}>_{{\operatorname{lex}}}{\bm{c}}^{k+3}>_{{\operatorname{lex}}}{\bm{a}}^{\ell}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}$
is a clique, by 3.9. As $\Delta({\bm{a}}^{1},\dots,{\bm{a}}^{n})=[1,n)$, we
can complete it to a maximal clique, which must have the form
${\bm{a}}^{1}>_{{\operatorname{lex}}}\dots>_{{\operatorname{lex}}}{\bm{a}}^{k+2}>_{{\operatorname{lex}}}{\bm{c}}^{k+3}>_{{\operatorname{lex}}}{\bm{c}}^{k+4}>_{{\operatorname{lex}}}>\cdots>{\bm{c}}^{\ell-1}>_{{\operatorname{lex}}}{\bm{a}}^{\ell}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}$
by 3.10. We will take this as our expected maximal clique $C$. Now,
${\bm{a}}^{1}>_{{\operatorname{lex}}}\dots>_{{\operatorname{lex}}}{\bm{a}}^{k+1}>_{{\operatorname{lex}}}{\bm{b}}^{k+2}>_{{\operatorname{lex}}}{\bm{c}}^{k+3}>_{{\operatorname{lex}}}{\bm{c}}^{k+4}>_{{\operatorname{lex}}}\cdots>{\bm{c}}^{\ell-1}>_{{\operatorname{lex}}}{\bm{a}}^{\ell}>_{{\operatorname{lex}}}\cdots>_{{\operatorname{lex}}}{\bm{a}}^{n}$
is also a maximal clique, which will be our expected $D$. One can check
directly that they satisfy the requirements.

  2. b

Suppose that $s_{k+1}+1<t_{k+1}$. We can make a similar argument. ∎

Note that each equivalence class $\mathcal{E}$ is ordered with respect to the
total order $\prec$ in 4.13. We will divide it into subclasses, for the
convenience of our later argument.

######  Notation 4.16.

Let $(\mathcal{E},L)$ be a marked equivalence class with
$\operatorname{sgn}(L)={\bm{\tau}}$. Then, the _subclasses
$\mathcal{E}_{j_{1},\ldots,j_{k}}\subset\mathcal{E}$ of level $k$_ are defined
such that the following conditions are satisfied.

  1. a

If $k<n-1$, then
$\mathcal{E}_{j_{1},\dots,j_{k}}=\bigsqcup_{t=1}^{m}\mathcal{E}_{j_{1},\dots,j_{k},t}$
is the disjoint union of nonempty subclasses of level $k+1$, for some suitable
positive integer $m$.

  2. b

For any $A,B\in\mathcal{E}_{j_{1},\ldots,j_{k}}$ with
$\operatorname{sgn}_{{\bm{\tau}}}(A)=(p_{1},\ldots,p_{n-1})$ and
$\operatorname{sgn}_{{\bm{\tau}}}(B)=(q_{1},\ldots,q_{n-1})$, one has
$p_{i}=q_{i}$ for all $i=1,\ldots,k$.

  3. c

It follows from the previous two conditions that every subclass of level $n-1$
contains exactly one maximal clique. Now, if
$A\in\mathcal{E}_{j_{1},\ldots,j_{n-1}}$ and
$B\in\mathcal{E}_{\ell_{1},\ldots,\ell_{n-1}}$ such that $A\prec B$ (or
equivalently, the first nonzero entry of
$\operatorname{sgn}_{{\bm{\tau}}}(A)-\operatorname{sgn}_{{\bm{\tau}}}(B)$ is
negative), then the first nonzero entry of
$(j_{1},\ldots,j_{n-1})-(\ell_{1},\ldots,\ell_{n-1})$ must be negative.

As a quick example, the maximal clique $B$ near the end of 4.14 belongs to the
corresponding subclass $\mathcal{E}_{3,2,1,1}$ of level $4$.

######  Lemma 4.17.

Let $(\mathcal{E},L)$ be a marked equivalence class with
$\operatorname{sgn}(L)={\bm{\tau}}$ and consider a subclass
$\mathcal{E}_{j_{1},\dots,j_{k}}$ of level $k$ with $j_{k}>1$. Suppose that
$\\{s_{1},\dots,s_{k-1},s_{k,1},\dots,s_{k,j_{k}}\\}$ is a subset of $[n-1]$
and the signatures of the maximal cliques in
$\mathcal{E}_{j_{1},\dots,j_{k-1},\ell}$ have the form
$(s_{1},\dots,s_{k-1},s_{k,\ell},p_{k+1},\dots,p_{n-1})$ for each $\ell\leq
j_{k}$, where $p_{i}\in[n-1]\setminus\\{s_{1},\dots,s_{k-1},s_{k,\ell}\\}$ for
$i=k+1,\dots,n-1$. Besides, assume that $t$ belongs to
$[n-1]\setminus\\{s_{1},\dots,s_{k-1},s_{k,1},\dots,s_{k,j_{k}-1}\\}$ such
that $t$ precedes $s_{k,j_{k}}$ with respect to ${\bm{\tau}}$. Then, there is
no maximal clique $A$ in $\mathcal{E}$ such that $\operatorname{sgn}(A)$ has
the form $(s_{1},\dots,s_{k-1},s_{k,j_{k}},t,q_{k+2},\dots,q_{n-1})$, where
$q_{i}\in[n-1]\setminus\\{s_{1},\dots,s_{k-1},s_{k,j_{k}},t\\}$ for
$i=k+2,\dots,n-1$.

###### Proof.

Suppose for contradiction that there is a maximal clique $A$ in $\mathcal{E}$
such that $\operatorname{sgn}(A)$ has the form
$(s_{1},\dots,s_{k-1},s_{k,j_{k}},t,q_{k+2},\dots,q_{n-1})$ for suitable
$q_{i}$’s. Since ${\bm{\tau}}$ is a legitimate signature and $t$ precedes
$s_{k,j_{k}}$ with respect to ${\bm{\tau}}$, we don’t have
$s_{k,j_{k}}\,\triangleleft\,t$ with respect to the partial order in 4.8.
Consequently, $(s_{1},\dots,s_{k-1},t,s_{k,j_{k}},p_{k+2},\dots,p_{n-1})$ is a
legitimate signature within $\mathcal{E}$ by 4.10. Let
$\mathcal{E}_{j_{1},\dots,j_{k-1},\ell}$ be the subclass, in which the
signatures of the maximal cliques have the form
$(s_{1},\dots,s_{k-1},t,r_{k+1},\dots,r_{n-1})$ for suitable $r_{i}$’s. Since
$t$ precedes $s_{k,j_{k}}$ with respect to ${\bm{\tau}}$, we have $\ell<j_{k}$
by the condition c in our construction of subclasses. But this contradicts the
choice of $t$. ∎

The following proposition guarantees the linear quotients within an
equivalence class.

######  Proposition 4.18.

Suppose that $A$ and $B$ are two maximal cliques in an equivalence class
$\mathcal{E}$ such that $B\prec A$. Then, there exists a maximal clique
$D\in\mathcal{E}$ such that $D\prec A$, and the set difference $A\setminus D$
is a singleton set with $A\setminus D\subseteq A\setminus B$.

###### Proof.

Suppose that in the marked equivalence class $(\mathcal{E},L)$, one has
$\operatorname{sgn}(L)={\bm{\tau}}$. In addition, assume that
$A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ and
$B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})\in\mathcal{E}$. Recall that we previously
defined
$\operatorname{diff}(A,B)\coloneqq\Set{i:{\bm{a}}^{i}\neq{\bm{b}}^{i}}$.

We may further assume that $A\in\mathcal{E}_{j_{1},\dots,j_{k-1},j_{k}}$ and
$B\in\mathcal{E}_{j_{1},\dots,j_{k-1},j_{k}^{\prime}}$ with
$j_{k}^{\prime}<j_{k}$. Then $k+1=\min\operatorname{diff}(A,B)$ and it is
clear that $k\leq n-2$. Let us consider a set of maximal cliques

$\mathcal{D}\coloneqq\Set{F\in\mathcal{E}:\operatorname{diff}(A,F)\subseteq\operatorname{diff}(A,B)\setminus\\{k+1\\}}.$

Since $A\in\mathcal{D}$, the set $\mathcal{D}$ is not empty. Let $A^{\prime}$
be the first maximal clique in $\mathcal{D}$ with respect to $\prec$ and
suppose that $\operatorname{sgn}(A^{\prime})=(s_{1},\dots,s_{n-1})$.
Obviously, $A^{\prime}\in\mathcal{E}_{j_{1},\dots,j_{k}}$ and
$A^{\prime}\preceq A$. Furthermore, we have both
$\operatorname{diff}(A^{\prime},B)\subseteq\operatorname{diff}(A,B)$ and
$\operatorname{diff}(A,A^{\prime})\subseteq\operatorname{diff}(A,B)$. Let
$C=({\bm{c}}^{1},\dots,{\bm{c}}^{n})$ be the tuple of elements in
${\mathbb{Z}}^{n}$, such that ${\bm{c}}^{1}={\bm{a}}^{1}$ and
$\operatorname{sgn}(C)=(s_{1},\dots,s_{k-1},s_{k+1},s_{k},s_{k+2},\dots,s_{n-1})$.
By 4.5, $\operatorname{diff}(C,A^{\prime})=\\{k+1\\}$. In addition, we claim
that $C$ is a legitimate maximal clique in $\mathcal{E}$ and $C\prec
A^{\prime}$. With this, if $A=A^{\prime}$, then we take $D=C$ since
$\operatorname{diff}(A,B)\supseteq\operatorname{diff}(A,C)=\\{k+1\\}$. If
instead $A\neq A^{\prime}$, then we will replace $B$ by $A^{\prime}$. Our
proof will be done by induction on the cardinality
$\\#\operatorname{diff}(A,B)$, since
$\operatorname{diff}(A,A^{\prime})\subsetneq\operatorname{diff}(A,B)$ and
$A^{\prime}\prec A$.

It remains to prove the above claim about $C$. Since
$A\in\mathcal{E}_{j_{1},\dots,j_{k-1},j_{k}}$, we may assume that the
signatures of the maximal cliques in $\mathcal{E}_{j_{1},\dots,j_{k-1},\ell}$
have the form $(s_{1},\dots,s_{k-1},s_{k,\ell},p_{k+1},\dots,p_{n-1})$ for
each $\ell<j_{k}$ with suitable $p_{i}$’s. From 4.17 we derive that either
$s_{k}$ precedes $s_{k+1}$ with respect to ${\bm{\tau}}$, or
$s_{k+1}\in\\{s_{k,1},\dots,s_{k,j_{k}-1}\\}$.

  1. a

Suppose that $s_{k}$ precedes $s_{k+1}$ with respect to ${\bm{\tau}}$. Since
$B\in\mathcal{E}_{j_{1},\dots,j_{k-1},j_{k}^{\prime}}$ with
$j_{k}^{\prime}<j_{k}$, we can write
$\operatorname{sgn}(B)=(s_{1},\dots,s_{k-1},s_{k,j_{k}^{\prime}},p_{k+1},\dots,p_{n-1})$
with suitable $p_{i}$’s. Since $j_{k}^{\prime}<j_{k}$, $s_{k,j_{k}^{\prime}}$
precedes $s_{k}$ with respect to ${\bm{\tau}}$. As a result of our assumption
here, $s_{k,j_{k}^{\prime}}$ also precedes $s_{k+1}$ with respect to
${\bm{\tau}}$. Without loss of generality, we may assume that
$\operatorname{diff}(A^{\prime},B)=\\{k+1,k+2,\dots,r\\}$ is a “continuous”
segment. Applying 4.15 to $A^{\prime}$ and $B$, we can find some maximal
clique $A^{\prime\prime}$ in $\mathcal{E}$ such that
$\operatorname{diff}(A^{\prime},A^{\prime\prime})\subseteq\operatorname{diff}(A^{\prime},B)$
and
$\operatorname{sgn}(A^{\prime\prime})=(s_{1},\dots,s_{k},s_{k,j_{k}^{\prime}},r_{k+2},\dots,r_{n-1})$
for suitable $r_{i}$’s. In particular,
$k+1\notin\operatorname{diff}(A,A^{\prime\prime})$. Meanwhile, we observe that

$\operatorname{diff}(A,A^{\prime\prime})\subseteq\operatorname{diff}(A,A^{\prime})\cup\operatorname{diff}(A^{\prime},A^{\prime\prime})\subseteq\operatorname{diff}(A,B)\cup\operatorname{diff}(A^{\prime},B)=\operatorname{diff}(A,B).$

Thus, the maximal clique $A^{\prime\prime}$ belongs to the previously defined
set $\mathcal{D}$. But since $s_{k,j_{k}^{\prime}}$ precedes $s_{k+1}$ with
respect to ${\bm{\tau}}$ while
$\operatorname{sgn}(A^{\prime})=(s_{1},\dots,s_{n-1})$, this contradicts our
choice of $A^{\prime}$.

  2. b

Suppose instead that $s_{k+1}=s_{k,\ell}$ for some $\ell<j_{k}$. Then,
${\bm{c}}^{k+1}$ is a legitimate tuple by the existence of
$\mathcal{E}_{j_{1},\dots,j_{k-1},\ell}$. Meanwhile, notice that $A^{\prime}$
is a legitimate maximal clique such that
$\operatorname{diff}(C,A^{\prime})=\\{k+1\\}$. Consequently, $C$ is also a
legitimate maximal clique. Since $\ell<j_{k}$, the index $s_{k+1}$ precedes
$s_{k}$ with respect to ${\bm{\tau}}$. Thus, $C\prec A^{\prime}$, fully
confirming our claim about $C$. ∎

Next, we consider the linear quotients across equivalence classes.

######  Lemma 4.19.

Suppose that $\mathcal{E}$ is an equivalence class such that
$\operatorname{rank}(\mathcal{E})>0$. Let $\kappa_{1}$, $\kappa_{2}$, and $L$
be as introduced in 4.12. Then, we have $\kappa_{1}+1<\kappa_{2}-1$.

###### Proof.

Suppose for contradiction that $\kappa_{1}+1\geq\kappa_{2}-1$. Since
$\kappa_{1}<\kappa_{2}$, we obtain either $\kappa_{1}+1=\kappa_{2}$ or
$\kappa_{1}+1=\kappa_{2}-1$. Since $n\geq 3$, $\kappa_{1}\leq n-1$, and
$\kappa_{2}\geq 2$, we encounter the following four cases.

  1. i

Suppose that $\kappa_{1}=n-1$. Then ${\bm{a}}^{1}=(1,0,\dots,0,a_{n}^{1})$
with $0\leq a_{n}^{1}\leq\alpha_{n}-1$. Consequently,
${\bm{a}}^{n}=(0,\dots,0,a_{n}^{1}+1)$, which has to be ${\bm{\eta}}$.

  2. ii

Suppose that $\kappa_{2}=2$. Then
${\bm{a}}^{1}=(a_{1}^{1},\alpha_{2},\dots,\alpha_{n-1},\alpha_{n}-1)$ with
$a_{1}^{1}>1$. Consequently,
${\bm{a}}^{n}=(a_{1}^{1}-1,\alpha_{2},\dots,\alpha_{n})$, which has to be
${\bm{\eta}}$.

  3. iii

Suppose that $\kappa_{1}+1=\kappa_{2}$ and $2\leq\kappa_{1}\leq n-2$. Then
${\bm{a}}^{1}=(1,0,\dots,0,\alpha_{\kappa_{1}+1},\dots,\alpha_{n-1},\alpha_{n}-1)$.
Consequently,
${\bm{a}}^{n}=(0,\dots,0,\alpha_{\kappa_{1}+1},\dots,\alpha_{n})$, which has
to be ${\bm{\eta}}$.

  4. iv

Suppose that $\kappa_{1}+1=\kappa_{2}-1$ and $1\leq\kappa_{1}\leq n-2$. Then

${\bm{a}}^{1}=(1,0,\dots,0,a_{\kappa_{1}+1}^{1},\alpha_{\kappa_{1}+2},\dots,\alpha_{n-1},\alpha_{n}-1)$

with $0<a_{\kappa_{1}+1}^{1}<\alpha_{\kappa_{1}+1}$. Consequently,
${\bm{a}}^{n}=(0,\dots,0,a_{\kappa_{1}+1}^{1},\alpha_{\kappa_{1}+2},\dots,\alpha_{n})$,
which has to be ${\bm{\eta}}$.

In each case, we always have $\operatorname{rank}(\mathcal{E})=0$, which is a
contradiction. ∎

######  Proposition 4.20.

Let $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ be a maximal clique in the
equivalence class $\mathcal{E}$ such that $rA$ does not exist. Suppose that
$B\prec A$ is a maximal clique such that $B\notin\mathcal{E}$. Then, there
exists another maximal clique $D\in\mathcal{E}$ and some $j\in[n-1]$ such that
$D\prec A$ and $A\setminus D=\\{{\bm{a}}^{j+1}\\}\subseteq A\setminus B$.

###### Proof.

We will prove this by using the notation and arguments of 4.12. As
$\operatorname{rank}(\mathcal{E})>0$ by the existence of $B$, we showed in
4.19 that $\kappa_{1}+1<\kappa_{2}-1$, and the first maximal clique $L$ in
$\mathcal{E}$ satisfies

$\operatorname{sgn}(L)=(\tau_{1},\dots,\tau_{\kappa_{2}-\kappa_{1}-2},\underbrace{n-1,n-2,\dots,\kappa_{2}-1},\underbrace{1,2,\dots,\kappa_{1}}),$

for appropriate $\tau_{i}$’s.

Suppose that $\operatorname{sgn}(A)=(s_{1},\dots,s_{n-1})$ and let $W$ be the
set

$[n-1]\setminus(\\{n-1,n-2,\dots,\kappa_{2}-1\\}\sqcup\\{1,2,\dots,\kappa_{1}\\})=\\{\kappa_{1}+1,\dots,\kappa_{2}-2\\}.$

Since $\kappa_{1}+1<\kappa_{2}-1$, $W$ is not empty. Meanwhile, since $rA$
does not exist, $s_{1}=1$ or $n-1$ by 4.4, and $s_{1}\notin W$. In the
following, let $j\geq 1$ be the smallest such that $s_{j+1}\in W$. We can
construct a maximal clique $D$ in $\mathcal{E}$ such that
$\operatorname{sgn}(D)=(s_{1},\dots,s_{j-1},s_{j+1},s_{j},s_{j+2},\dots,s_{n-1})$.

To confirm the legitimacy of $D$, notice that $s_{j}\notin W$ while
$s_{j+1}\in W$. Since $s_{j+1}$ precedes $s_{j}$ in $\operatorname{sgn}(L)$
while $s_{j}$ precedes $s_{j+1}$ in $\operatorname{sgn}(A)$, these two indices
are not comparable in the poset of obstructions, i.e., they can exchange
positions in any legitimate signature. As $\operatorname{sgn}(A)$ is a
legitimate signature, so is $\operatorname{sgn}(D)$, namely, $D$ is a maximal
clique in $\mathcal{E}$.

Next, since $s_{j+1}$ precedes $s_{j}$ in $\operatorname{sgn}(L)$, we deduce
that $D\prec A$. From 4.5 we also have $A\setminus D=\\{{\bm{a}}^{j+1}\\}$. It
remains to show that this ${\bm{a}}^{j+1}\notin B$. Suppose for contradiction
that this is not true. Then, we can write
$B=({\bm{b}}^{1},\dots,{\bm{b}}^{n})$ and
${\bm{b}}^{j^{\prime}}={\bm{a}}^{j+1}$ for some $j^{\prime}$. Since $B\prec
A$, we must have $j^{\prime}\leq j+1$, by rank reason. At the same time, given
4.9, we can find $i_{1}\leq\kappa_{1}$ and $i_{2}\leq n-\kappa_{2}$ such that
$\\{s_{1},\dots,s_{j}\\}=\\{1,\dots,i_{1}\\}\sqcup\\{n-i_{2},\dots,n-1\\}$, by
the choice of $j$. Whence, we can write
${\bm{a}}^{j+1}=(\underbrace{0,\dots,0}_{i_{1}},a^{j+1}_{i_{1}+1},\dots,a^{j+1}_{n-i_{2}},\underbrace{\alpha_{n-i_{2}+1},\dots,\alpha_{n}}_{i_{2}})$.
Since ${\bm{b}}^{j^{\prime}}={\bm{a}}^{j+1}$, we obtain that
$1,2,\dots,i_{1},n-i_{2},\dots,n-1\notin\Delta({\bm{b}}^{j^{\prime}},{\bm{b}}^{n})$.
Thus, if $\operatorname{sgn}(B)=(q_{1},\dots,q_{n-1})$, then
$\\{1,\dots,i_{1},n-i_{2},\dots,n-1\\}\subseteq\\{q_{1},\dots,q_{j^{\prime}-1}\\}$,
forcing $j\leq j^{\prime}-1$. Therefore, $j^{\prime}=j+1$. It is now clear
that
$\\{q_{1},\dots,q_{j}\\}=\\{1,\dots,i_{1}\\}\sqcup\\{n-i_{2},\dots,n-1\\}$,
and $\Delta({\bm{b}}^{1},{\bm{b}}^{j+1})=\Delta({\bm{a}}^{1},{\bm{a}}^{j+1})$.
As ${\bm{b}}^{j+1}={\bm{a}}^{j+1}$, it follows that
${\bm{b}}^{1}={\bm{a}}^{1}$ and $B\in\mathcal{E}$ as well. This contradicts
the assumption that $B\notin\mathcal{E}$. ∎

Finally, we are ready to show the announced linear quotient result.

######  Theorem 4.21.

The total order $\prec$ of 4.13 induces a linear quotient order of the
monomial generating set $G(\operatorname{in}(J)^{\vee})$.

###### Proof.

Take arbitrary maximal cliques $A$ and $B$ such that $B\prec A$. Given
Equation 1, it suffices to find suitable maximal clique $D$ with $D\prec A$
such that $A\setminus D$ is a singleton set with $A\setminus D\subseteq
A\setminus B$. Suppose that $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ and
$A\in\mathcal{E}$. We have two cases.

  1. a

Assume that $B\in\mathcal{E}$. We apply 4.18 for the existence of such $D$.

  2. b

Assume that $B\notin\mathcal{E}$.

    1. i

If $rA$ exists, then $A\setminus rA=\\{{\bm{a}}^{1}\\}$. Note that
${\bm{a}}^{1}\notin B$ for rank reasons. So in this case we take $D=rA$.

    2. ii

Assume that $rA$ does not exist. We apply 4.20 for the existence of such $D$.
∎

##  5\. Applications

This section is devoted to two applications of the linear quotient structure
that we established earlier. Here, we continue to assume that
$\mathcal{A}_{d,{\bm{\alpha}}}$ is the Veronese type algebra of 2.3 and
${\bm{\eta}}$ is the tuple given in 3.3. Meanwhile, $J$ is the presentation
ideal so that $\mathcal{A}_{d,{\bm{\alpha}}}={\mathbb{K}}[{\bm{T}}]/J$.

###  5.1. Regularity of the algebra

First of all, we determine the Castelnuovo–Mumford regularity of the algebra
$\mathcal{A}_{d,{\bm{\alpha}}}$.

For each maximal clique $A$ in the graph
$\mathcal{G}=\mathcal{G}(d,{\bm{\alpha}})$, we will denote the minimal number
of generators of the linear quotient ideal
$\braket{{\bm{T}}_{B^{\complement}}:B\prec
A}:_{{\mathbb{K}}[{\bm{T}}]}{\bm{T}}_{A^{\complement}}$ by
$\omega_{{\bm{\alpha}}}(A)$, or $\omega(A)$ for short. By the proof of 4.21,
we have

$\omega(A)=\\#\Set{B\prec A:\operatorname{diff}(A,B)\text{ is a singleton
set}}.$ (2)

Furthermore, by 3.2, we have the following formula:

$\operatorname{pd}((\operatorname{in}(J))^{\vee})=\max\limits_{A}\omega(A).$
(3)

Since
$\operatorname{pd}((\operatorname{in}(J))^{\vee})=\operatorname{reg}(\mathcal{A}_{d,{\bm{\alpha}}})$
by 3.1, the task is now clear: find the largest $\omega(A)$. We start with a
quick estimate.

######  Lemma 5.1.

We have $\omega(A)\leq n-1$ for each maximal clique
$A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$.

###### Proof.

Since $\braket{{\bm{T}}_{B^{\complement}}:B\prec
A}:_{{\mathbb{K}}[{\bm{T}}]}{\bm{T}}_{A^{\complement}}$ is linear, it follows
from Equation 1 that

$\omega(A)=\\#\Set{{\bm{a}}^{i}:\text{there exists some $B\prec A$ with
$\\{{\bm{a}}^{i}\\}=A\setminus B$}}.$

Therefore, it suffices to show that there is no $B$ with $B\prec A$ such that
$\\{{\bm{a}}^{n}\\}=A\setminus B$. Suppose for contradiction that this is not
true. By 3.10, we have either
$B=({\bm{b}},{\bm{a}}^{1},{\bm{a}}^{2},\dots,{\bm{a}}^{n-1})$ or
$B=({\bm{a}}^{1},{\bm{a}}^{2},\dots,{\bm{a}}^{n-1},{\bm{b}})$ for some
suitable tuple ${\bm{b}}$. In the first case,
$\operatorname{rank}(B)=\operatorname{rank}(A)+1$, which contradicts the
assumption that $B\prec A$. In the second case, we have $B=A$ by 3.10, which
is also a contradiction. ∎

It is natural to ask: when do we have $\omega(A)=n-1$? Let us start with a
simple observation. In any equivalence class $\mathcal{E}$, every maximal
clique $A$ uniquely corresponds to the signature $\operatorname{sgn}(A)$,
which is a permutation in $\mathfrak{S}_{n-1}$. Thus, it is clear that
$\mathcal{E}$ contains at most $(n-1)!$ elements. In the following, we
classify when an equivalent class $\mathcal{E}$ contains exactly $(n-1)!$
elements.

######  Lemma 5.2.

Let $\mathcal{E}$ be an equivalence class such that every maximal clique in it
begins with ${\bm{a}}^{1}=(a_{1}^{1},\ldots,a_{n}^{1})$. Then, the following
are equivalent:

  1. a

the cardinality $\\#\mathcal{E}=(n-1)!$;

  2. b

the poset of obstructions in 4.8 is trivial for $\mathcal{E}$;

  3. c

one has $1\leq a_{1}^{1}\leq\alpha_{1}$, $1\leq a_{j}^{1}\leq\alpha_{j}-1$ for
all $2\leq j\leq n-1$, and $0\leq a_{n}^{1}\leq\alpha_{n}-1$.

###### Proof.

The cardinality $\\#\mathcal{E}=(n-1)!$ if and only if every permutation in
$\mathfrak{S}_{n-1}$ is the signature of some maximal clique in $\mathcal{E}$.
But the latter is equivalent to saying that the poset of obstructions in 4.8
is trivial for $\mathcal{E}$, namely, $1\leq a_{j}^{1}\leq\alpha_{j}-1$ for
all $2\leq j\leq n-1$. That $1\leq a_{1}^{1}\leq\alpha_{1}$ and $0\leq
a_{n}^{1}\leq\alpha_{n}-1$ is automatic for all such ${\bm{a}}^{1}$ in view of
3.10. ∎

In the following, we characterize when
$\operatorname{pd}((\operatorname{in}(J))^{\vee})$ is exactly $n-1$.

######  Proposition 5.3.

The following conditions are equivalent:

  1. a

the projective dimension
$\operatorname{pd}((\operatorname{in}(J))^{\vee})=n-1$;

  2. b

there exists a maximal clique $A$ such that $\omega(A)=n-1$;

  3. c

one has $n\leq d\leq\sum_{i=1}^{n}(\alpha_{i}-1)$;

  4. d

there exists a maximal clique $A=({\bm{a}}^{1},\ldots,{\bm{a}}^{n})$ with
${\bm{a}}^{1}=(a_{1}^{1},\ldots,a_{n}^{1})$ such that

$2\leq a_{1}^{1}\leq\alpha_{1},\quad 1\leq a_{j}^{1}\leq\alpha_{j}-1\text{ for
all }2\leq j\leq n-1,\quad\text{and}\quad 0\leq a_{n}^{1}\leq\alpha_{n}-2.$

###### Proof.

The equivalence of a and b is clear from the explanation before 5.2.

Next, we show the equivalence of c and d. Since $|{\bm{a}}^{1}|=d$, we can
easily deduce c from d. Conversely, if c is satisfied, we can easily find
suitable ${\bm{a}}^{1}=(a_{1}^{1},\ldots,a_{n}^{1})\in{\mathbb{N}}^{n}$ as in
d. Let $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ be the tuple of elements in
${\mathbb{Z}}^{n}$ such that $\operatorname{sgn}(A)=(1,2,\dots,n-1)$. It can
be verified directly that $A$ is a legitimate maximal clique. Thus, we get d.

In the following, we show the equivalence of b and d.

  1. b $\Leftarrow$ d:

Suppose that the condition in d is satisfied. Then, the equivalence class
$\mathcal{E}$ to which $A$ belongs has exactly $(n-1)!$ maximal cliques by
5.2, and every permutation in $\mathfrak{S}_{n-1}$ is legitimate as a
signature with respect to $\mathcal{E}$. Without loss of generality, we may
assume that $A$ is the very last maximal clique of $\mathcal{E}$ with
$\operatorname{sgn}(A)=(s_{1},\dots,s_{n-1})$. For each $k=2,3,\dots,n-1$, we
consider the maximal clique $B^{k}$ in $\mathcal{E}$ with
$\operatorname{sgn}(B^{k})=(s_{1},\dots,s_{k-2},s_{k},s_{k-1},s_{k+1},\dots,s_{n-1})$.
Then $B^{k}\prec A$ and $A\setminus B^{k}=\\{{\bm{a}}^{k}\\}$ by 4.5.
Meanwhile, since $a_{n}^{1}\leq\alpha_{n}-2$, it follows from 3.10 that
${\bm{a}}^{n}$ is not the tuple ${\bm{\eta}}$ of 3.3. In other words,
$\operatorname{rank}(\mathcal{E})>0$. Thus, $rA$ exists and $A\setminus
rA=\\{{\bm{a}}^{1}\\}$ by 4.4. In conclusion,
$\braket{{\bm{T}}_{C^{\complement}}:C\prec
A}:_{{\mathbb{K}}[{\bm{T}}]}{\bm{T}}_{A^{\complement}}=\braket{T_{{\bm{a}}^{1}},\dots,T_{{\bm{a}}^{n-1}}}$
is linear and has the maximal size by the proof of 5.1. In particular, b
holds.

  2. b $\Rightarrow$ d:

Suppose that the condition in b is satisfied. Then, there exists a maximal
clique $A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})$ in some equivalence class
$(\mathcal{E},L)$ such that the quotient ideal
$Q\coloneqq\braket{{\bm{T}}_{B^{\complement}}:B\prec
A}:_{{\mathbb{K}}[{\bm{T}}]}{\bm{T}}_{A^{\complement}}$ is linear with $n-1$
minimal monomial generators. In view of 5.1 and its proof, this implies that
$Q=\braket{T_{{\bm{a}}^{1}},T_{{\bm{a}}^{2}},\dots,T_{{\bm{a}}^{n-1}}}$. Since
$T_{{\bm{a}}^{1}}\in Q$, $rA$ must exist and
$\operatorname{rank}(\mathcal{E})>0$. Additionally, for each
$k\in\\{2,\dots,n-1\\}$, we have a maximal clique $B^{k}$ such that
$B^{k}\prec A$ and $A\setminus B^{k}=\\{{\bm{a}}^{k}\\}$. Since $B^{k}$
obviously starts with ${\bm{a}}^{1}$, this maximal clique belongs to
$\mathcal{E}$. Now, suppose that
$\operatorname{sgn}(A)=(s_{1},\dots,s_{n-1})$. It follows from 4.5 that
$\operatorname{sgn}(B^{k})=(s_{1},\dots,s_{k-2},s_{k},s_{k-1},s_{k+1},\ldots,s_{n-1})$.
Since $B^{k}\prec A$, we must have $s_{k}<s_{k-1}$ when considering the
lexicographical order at the end of 4.13c. Since this holds for any
$k\in\\{2,\dots,n-1\\}$, we conclude that $s_{n-1}<s_{n-2}<\cdots<s_{1}$ with
respect to this lexicographical order. Whence, $A$ is the last maximal clique
of $\mathcal{E}$ and $\operatorname{sgn}(L)=(s_{n-1},\dots,s_{1})$ is the
reverse of $\operatorname{sgn}(A)$. Consequently, the poset of obstructions
considered in 4.8 is trivial, and we have $0<a_{i}^{1}<\alpha_{i}$ for
$i\in\\{2,\dots,n-1\\}$ by 5.2.

Furthermore, since $A$ is legitimate, $1\leq a_{1}^{1}\leq\alpha_{1}$ and
$0\leq a_{n}^{1}\leq\alpha_{n}-1$ by 3.10. If $a_{1}^{1}=1$, then
$\operatorname{sgn}(L)$ takes the form $(\tau_{1},\dots,\tau_{n-2},1)$ by the
requirement in 4.12. Whence, $s_{1}=1$. But this implies that $rA$ does not
exist by 4.4, a contradiction. Similarly, we can prove that
$a_{n}^{1}\leq\alpha_{n}-2$. Thus, d holds. ∎

In what follows, we consider the case where the equivalent requirements of 5.3
are not satisfied. Before doing so, we introduce a reduction.

######  Remark 5.4.

Suppose that $I$ is an equigenerated monomial ideal with minimal monomial
generators ${\bm{x}}^{{\bm{a}}^{1}},\dots,{\bm{x}}^{{\bm{a}}^{t}}$ in
${\mathbb{K}}[x_{1},\dots,x_{n}]$. In addition, suppose that ${\bm{b}}$ is a
tuple in ${\mathbb{N}}^{n}$ such that
${\bm{b}}-{\bm{a}}^{i}\in{\mathbb{N}}^{n}$ for each $i$. Whence, we will call
$I^{[{\bm{b}}]}\coloneqq\braket{{\bm{x}}^{{\bm{b}}-{\bm{a}}^{1}},\dots,{\bm{x}}^{{\bm{b}}-{\bm{a}}^{t}}}$
the _generalized Newton dual of $I$ with respect to ${\bm{b}}$_. It follows
from [MR4221772, Theorem 3.1] that the algebra ${\mathbb{K}}[I]$ is isomorphic
to ${\mathbb{K}}[I^{[{\bm{b}}]}]$. Of course, we are only interested in the
case where $I=I_{d,{\bm{\alpha}}}$, and ${\bm{b}}={\bm{\alpha}}$. In this
case, we have

$\mathcal{A}_{d,{\bm{\alpha}}}={\mathbb{K}}[I]\cong{\mathbb{K}}[I^{[{\bm{\alpha}}]}]=\mathcal{A}_{|{\bm{\alpha}}|-d,{\bm{\alpha}}}.$
(4)

######  Proposition 5.5.

Suppose that either $n>d$ or $\sum_{i=1}^{n}(\alpha_{i}-1)<d$. Let
$d^{\prime}=\min(d,|{\bm{\alpha}}|-d)$. Then,
$\operatorname{pd}((\operatorname{in}(J))^{\vee})=\left\lfloor
n-\frac{n}{d^{\prime}}\right\rfloor$.

###### Proof.

It follows from the isomorphism in Equation (4) that we can assume that
$d^{\prime}=d$ and $n>d$. From this, we also deduce that
$2d\leq|{\bm{\alpha}}|$.

As the first step, we show that
$\operatorname{pd}((\operatorname{in}(J))^{\vee})\geq\left\lfloor
n-\frac{n}{d}\right\rfloor$. In the extremal case when $d=1$, since
$|{\bm{\eta}}|=d$, one obviously has ${\bm{\eta}}=(0,\dots,0,1)$ and
$I_{d,{\bm{\alpha}}}$ is the graded maximal ideal of $S$. Whence, the claimed
formula is guaranteed by [MR2955237, Theorem 4.2]. Therefore, in the
following, we will assume that $d\geq 2$. By Equation 3, we need to find a
maximal clique $A$ such that $\omega(A)\geq\left\lfloor
n-\frac{n}{d}\right\rfloor$. Suppose that $n-1=pd+q$ such that
$p=\left\lfloor\frac{n-1}{d}\right\rfloor$ and $0\leq q<d$. Then,
$\left\lfloor n-\frac{n}{d}\right\rfloor=n-1-p$. Let $\mathcal{E}$ be the
equivalence class of maximal cliques, all of which start with the vertex

${\bm{a}}^{1}\coloneqq(\underbrace{\underbrace{1,0,\dots,0}_{p},\dots,\underbrace{1,0,\dots,0}_{p}}_{d-q},\underbrace{\underbrace{1,0,\dots,0}_{p+1},\dots,\underbrace{1,0,\dots,0}_{p+1}}_{q},0)$

in $\mathcal{G}(d,{\bm{\alpha}})$. Thus, the maximal cliques in $\mathcal{E}$
all end with ${\bm{a}}^{n}$ such that
$\Delta({\bm{a}}^{1},{\bm{a}}^{n})=[1,n)$ by 3.10. It is clear that
${\bm{a}}^{n}=(0,a^{1}_{2},\ldots,a^{1}_{n-1},1)$. If $\alpha_{n}\geq 2$,
since ${\bm{\eta}}=(*,\dots,*,\alpha_{n})$, we have
${\bm{a}}^{n}\neq{\bm{\eta}}$. Therefore,
$\operatorname{rank}(\mathcal{E})>0$. If instead $\alpha_{n}=1$, then
${\bm{\alpha}}=(1,\dots,1)$. Whence, $2d\leq|{\bm{\alpha}}|=n$. We still have
$\operatorname{rank}(\mathcal{E})>0$. Otherwise, we will have

${\bm{a}}^{n}=(\underbrace{0,\dots,0}_{p},\underbrace{\underbrace{1,0,\dots,0}_{p},\dots,\underbrace{1,0,\dots,0}_{p}}_{d-q-1},\underbrace{\underbrace{1,0,\dots,0}_{p+1},\dots,\underbrace{1,0,\dots,0}_{p+1}}_{q},1)={\bm{\eta}}.$

Since $p\geq 1$, by the description of ${\bm{\eta}}$ in 3.3, the only
possibility is $q=0$ and $p=1$. Whence, $n=d+1$. But as $n\geq 3$ and $2d\leq
n$, this is impossible.

To simplify the following proof, we write accordingly

$(1,2,\dots,n-1)=(\underbrace{\underbrace{s_{1}^{1},\dots,s_{p}^{1}}_{p},\dots,\underbrace{s_{1}^{d-q},\dots,s_{p}^{d-q}}_{p}}_{d-q},\underbrace{\underbrace{s_{0}^{d-q+1},\dots,s_{p}^{d-q+1}}_{p+1},\dots,\underbrace{s_{0}^{d},\dots,s_{p}^{d}}_{p+1}}_{q}).$

Then, we have

$s_{i}^{\ell}\,\triangleleft\,s_{j}^{\ell}\qquad\text{for all $i<j$ and all
$\ell$}$ (5)

in the poset of obstructions defined in 4.8. Furthermore, we have

$\displaystyle s_{1}^{i+1}\,\triangleleft\,s_{p}^{i}\qquad\text{ if $1\leq
i\leq d-q-1$ and $\alpha_{s_{1}^{i+1}}=1$,}$ (6) and $\displaystyle
s_{0}^{j+1}\,\triangleleft\,s_{p}^{j}\qquad\text{ if $d-q\leq j\leq d-1$ and
$\alpha_{s_{0}^{j+1}}=1$,}$ (7)

in the poset of obstructions. Indeed, they are the generating relations of
that poset. Since the Castelnuovo–Mumford regularity of
$\mathcal{A}_{d,{\bm{\alpha}}}$ is independent of the rules we impose in
Section 4, we can further require that

$\displaystyle\operatorname{sgn}(L)\coloneqq(\underbrace{s_{0}^{d},\dots,s_{p-1}^{d}}_{p},$
$\displaystyle\overbrace{\underbrace{s_{0}^{d-1},\dots,s_{p}^{d-1}}_{p+1},\dots,\underbrace{s_{0}^{d-q+1},\dots,s_{p}^{d-q+1}}_{p+1}}^{q-1},$
$\displaystyle\qquad\qquad\underbrace{\underbrace{s_{1}^{d-q},\dots,s_{p}^{d-q}}_{p},\dots,\underbrace{s_{1}^{2},\dots,s_{p}^{2}}_{p}}_{d-q-1},s_{p}^{d},\underbrace{s_{1}^{1},\dots,s_{p}^{1}}_{p})$

when $q\geq 1$. If instead $q=0$, we then require that

$\operatorname{sgn}(L)\coloneqq(\underbrace{s_{1}^{d},\dots,s_{p-1}^{d}}_{p-1},\underbrace{\underbrace{s_{1}^{d-1},\dots,s_{p}^{d-1}}_{p},\dots,\underbrace{s_{1}^{2},\dots,s_{p}^{2}}_{p}}_{d-2},s_{p}^{d},\underbrace{s_{1}^{1},\dots,s_{p}^{1}}_{p}).$

In any case, the prescribed $\operatorname{sgn}(L)$ is a legitimate signature
by 4.10, since it satisfies the requirements of Equations (5), (6), (7), and
4.12. Now, let $A$ be the maximal clique starting from ${\bm{a}}^{1}$ such
that

$\operatorname{sgn}(A)\coloneqq(\underbrace{s_{0}^{d-q+1},s_{0}^{d-q+2},\dots,\framebox{$s_{0}^{d}$}}_{q},\underbrace{\underbrace{s_{1}^{1},s_{1}^{2},\dots,\framebox{$s_{1}^{d}$}}_{d},\dots,\underbrace{s_{p-1}^{1},s_{p-1}^{2},\dots,\framebox{$s_{p-1}^{d}$}}_{d}}_{p-1},\underbrace{s_{p}^{1},s_{p}^{d},s_{p}^{2},\dots,\framebox{$s_{p}^{d-1}$}}_{d}).$

Then $A$ is legitimate by 4.10, since it satisfies the requirements of
Equations (5), (6), and (7). Note that all end positions of the underbraced
segments in $\operatorname{sgn}(A)$ are boxed. Suppose that we also write
$\operatorname{sgn}(A)=(t_{1},\dots,t_{n-1})$. For each $k\in[n-2]$ such that
$t_{k}$ is not boxed, we can find a tuple
$B^{k}=({\bm{b}}_{1}^{k},\dots,{\bm{b}}_{n}^{k})$ of elements in
${\mathbb{Z}}^{n}$ such that ${\bm{b}}_{1}^{k}={\bm{a}}^{1}$ and

$\operatorname{sgn}(B^{k})=(t_{1},\dots,t_{k-1},t_{k+1},t_{k},t_{k+2},\dots,t_{n-1}).$

Note that $B^{k}$ is also a legitimate maximal clique in $\mathcal{E}$, since
it satisfies the requirements of Equations (5), (6), and (7). Moreover,
$B^{k}\prec A$ due to our choice of $\operatorname{sgn}(L)$, and
$\operatorname{diff}(A,B^{k})$ is a singleton set by 4.5. Consequently, we
have a natural lower bound for the minimal number of generators:

$\mu(\braket{{\bm{T}}_{B^{\complement}}:B\in\mathcal{E}\text{ and }B\prec
A}:_{{\mathbb{K}}[{\bm{T}}]}{\bm{T}}_{A^{\complement}})\geq\begin{cases}n-2-p,&\text{if
$q\neq 0$,}\\\ n-1-p,&\text{if $q=0$}\end{cases}$

by the first part of the proof of 4.21. Notice that $q=0$ if and only if
$\operatorname{sgn}(A)$ starts with $1$, if and only if $rA$ does not exist by
4.4. Thus,

$\omega(A)=\mu(\braket{{\bm{T}}_{B^{\complement}}:B\prec
A}:_{{\mathbb{K}}[{\bm{T}}]}{\bm{T}}_{A^{\complement}})\geq
n-1-{p}=\left\lfloor n-\frac{n}{d}\right\rfloor$

by the second part of the proof of 4.21. Therefore, we get
$\operatorname{pd}((\operatorname{in}(J))^{\vee})=\max\limits_{B}\omega(B)\geq\left\lfloor
n-\frac{n}{d}\right\rfloor$, as planned.

As the second step, we show that
$\operatorname{pd}((\operatorname{in}(J))^{\vee})\leq\left\lfloor
n-\frac{n}{d}\right\rfloor$. For this purpose, we introduce the new tuple
${\bm{\alpha}}^{\prime}=(d,\dots,d)$. Notice that the sets of maximal cliques
satisfy that
$\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}))\subseteq\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}^{\prime}))$.
For any fixed
$A=({\bm{a}}^{1},\dots,{\bm{a}}^{n})\in\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}))$,
let $\mathcal{E}({\bm{\alpha}})$ (resp. $\mathcal{E}({\bm{\alpha}}^{\prime})$)
be the equivalence class in $\mathcal{G}(d,{\bm{\alpha}})$ (resp.
$\mathcal{G}(d,{\bm{\alpha}}^{\prime})$) to which $A$ belongs. Let
${\bm{\eta}}$ (resp. ${\bm{\eta}}^{\prime}$) be the tuple given in 3.3 for
${\bm{\alpha}}$ (resp. ${\bm{\alpha}}^{\prime}$). It is clear that the post of
obstructions of $\mathcal{E}({\bm{\alpha}}^{\prime})$ is a subposet of
$\mathcal{E}({\bm{\alpha}})$. Let $\kappa_{1}$ and $\kappa_{2}$ (resp.
$\kappa_{1}^{\prime}$ and $\kappa_{2}^{\prime}$) be the index defined in 4.12
for ${\bm{\alpha}}$ (resp. ${\bm{\alpha}}^{\prime}$), then we have
$\kappa_{1}=\kappa_{1}^{\prime}$ by the definition. As for $\kappa_{2}$ and
$\kappa_{2}^{\prime}$, notice first that
$a^{1}_{n}\leq\alpha^{\prime}_{n}-1=d-1$ and $|{\bm{a}}^{1}|=d$. If
$a^{1}_{n}=d-1$, we must have ${\bm{a}}^{1}=(1,0,\ldots,0,d-1)$ and
${\bm{a}}^{n}=(0,\ldots,0,d)={\bm{\eta}}={\bm{\eta}}^{\prime}$. Whence,
$\mathcal{E}({\bm{\alpha}})=\mathcal{E}({\bm{\alpha}}^{\prime})$ has rank $0$
and contains exactly one maximal clique:

$A=((1,0,\ldots,0,d-1),(0,1,0,\ldots,0,d-1),\ldots,(0,\ldots,0,d)).$

In particular, $\omega_{\bm{\alpha}}(A)=0=\omega_{{\bm{\alpha}}^{\prime}}(A)$.
On the other hand, if $a^{1}_{n}<d-1$, then $\kappa_{2}^{\prime}$ does not
exist. As a result, the special $L$ we designate to
$\mathcal{E}({\bm{\alpha}})$ in 4.12 also works for the equivalence
$\mathcal{E}({\bm{\alpha}}^{\prime})$. Consequently, we have

$\Set{B\in\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}})):B\prec_{{\bm{\alpha}}}A}=\Set{B\in\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}^{\prime})):B\prec_{{\bm{\alpha}}^{\prime}}A}\cap\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}})),$

and $\omega_{{\bm{\alpha}}}(A)\leq\omega_{{\bm{\alpha}}^{\prime}}(A)$ by
Equation 2. Then it is easy to deduce that

$\displaystyle\operatorname{pd}((\operatorname{in}(J({\bm{\alpha}})))^{\vee})$
$\displaystyle=\max_{A\in\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}))}\omega_{{\bm{\alpha}}}(A)\leq\max_{A\in\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}))}\omega_{{\bm{\alpha}}^{\prime}}(A)$
$\displaystyle\leq\max_{A\in\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}^{\prime}))}\omega_{{\bm{\alpha}}^{\prime}}(A)=\operatorname{pd}((\operatorname{in}(J({\bm{\alpha}}^{\prime})))^{\vee}).$

Since
$\operatorname{pd}((\operatorname{in}(J({\bm{\alpha}}^{\prime})))^{\vee})=\operatorname{reg}(\mathcal{A}_{d,{\bm{\alpha}}^{\prime}})=\left\lfloor
n-\frac{n}{d}\right\rfloor$ by [MR2955237, Theorem 4.2], this completes the
proof. ∎

We can summarize the above results and state the first main theorem of this
section.

######  Theorem 5.6.

Let $\mathcal{A}_{d,{\bm{\alpha}}}$ be the Veronese type algebra in 2.3. Set
$d^{\prime}=\min(d,|{\bm{\alpha}}|-d)$. Then,
$\operatorname{pd}((\operatorname{in}(J))^{\vee})=\left\lfloor
n-\frac{n}{d^{\prime}}\right\rfloor$.

###### Proof.

Let $J$ be the presentation ideal of $\mathcal{A}_{d,{\bm{\alpha}}}$. From
2.5, [CV, Corollary 2.7] and [MR2724673, Proposition 8.1.10], we derive that
$\operatorname{reg}(\mathcal{A}_{d,{\bm{\alpha}}})=\operatorname{reg}({\mathbb{K}}[{\bm{T}}]/J)=\operatorname{reg}({\mathbb{K}}[{\bm{T}}]/\operatorname{in}(J))=\operatorname{pd}((\operatorname{in}(J))^{\vee})$.
The formulas then follow from Propositions 5.3 and 5.5. ∎

Recall that the _$\mathtt{a}$ -invariant_ of an algebra was introduced by Goto
and Watanabe in [MR494707, Definition 3.1.4]. Since the Veronese type algebra
$\mathcal{A}_{d,{\bm{\alpha}}}$ is Cohen–Macaulay by 2.5, we have

$\mathtt{a}(\mathcal{A}_{d,{\bm{\alpha}}})=\operatorname{reg}(\mathcal{A}_{d,{\bm{\alpha}}})-\operatorname{dim}(\mathcal{A}_{d,{\bm{\alpha}}})$
(8)

in view of the equivalent definition of Castelnuovo–Mumford regularity in
[MR676563, Definitions 1 and 3]. Notice that the dimension and the
Castelnuovo–Mumford regularity of $\mathcal{A}_{d,{\bm{\alpha}}}$ are known by
2.6 and 5.6 respectively. Therefore, we obtain the $\mathtt{a}$-invariant of
this algebra for free. Moreover, the _reduction number_ of the ideal
$I_{d,{\bm{\alpha}}}$, and the Castelnuovo–Mumford regularity of the algebra
$\mathcal{A}_{d,{\bm{\alpha}}}$ are equal by the following lemma. For the
definition and further discussion of the reduction numbers of ideals, see
[MR2266432, Section 8.2].

######  Lemma 5.7 ([CNPY, Proposition 6.6] or [MR3864202, Proposition 1.2]).

Let $I$ be an equigenerated monomial ideal in some polynomial ring over a
field ${\mathbb{K}}$. Assume that the algebra ${\mathbb{K}}[I]$ is
Cohen–Macaulay and the field ${\mathbb{K}}$ is infinite. Then $I$ has the
reduction number $\mathtt{r}(I)=\operatorname{reg}({\mathbb{K}}[I])$.

######  Corollary 5.8.

Let $\mathcal{A}_{d,{\bm{\alpha}}}={\mathbb{K}}[I_{d,{\bm{\alpha}}}]$ be the
Veronese type algebra in 2.3. Assume that ${\mathbb{K}}$ is an infinite field
and set $d^{\prime}=\min(d,|{\bm{\alpha}}|-d)$. Then,
$\mathtt{r}(I)=\left\lfloor n-\frac{n}{d^{\prime}}\right\rfloor$ and
$\mathtt{a}(\mathcal{A}_{d,{\bm{\alpha}}})=-\left\lceil\frac{n}{d^{\prime}}\right\rceil$.

###### Proof.

The algebra $\mathcal{A}_{d,{\bm{\alpha}}}$ is Cohen–Macaulay by 2.5. Thus,
the statements follow from 2.6, 5.6, 5.7, and Equation 8. ∎

###  5.2. Multiplicity bound of the algebra

We conclude this work with a reasonable upper bound on the multiplicity of the
Veronese type algebra $\mathcal{A}_{d,{\bm{\alpha}}}$. To begin with, we count
the number of generators of the ideal $I_{d,{\bm{\alpha}}}$, the number of
different equivalent classes of maximal cliques, and the number of equivalent
classes that have precisely $(n-1)!$ maximal cliques.

######  Lemma 5.9.

The dimension of the polynomial ring
${\mathbb{K}}[{\bm{T}}]\coloneqq{\mathbb{K}}[T_{\bm{a}}:{\bm{a}}\in
V_{n,d}^{{\bm{\alpha}}}]$ is given by

$\operatorname{dim}(\mathbb{K}[{\bm{T}}])=\sum_{i\geq
0}(-1)^{i}\sum_{\begin{subarray}{c}P\subseteq[n],\\\
\\#P=i\end{subarray}}\binom{d-\sum_{p\in P}(\alpha_{p}+1)+n-1}{n-1}.$

Moreover, there are

$\displaystyle G\coloneqq\sum_{i,j\geq
0}(-1)^{i+j}\sum_{\begin{subarray}{c}P\subseteq\\{2,3,\dots,n-1\\},\\\
\\#P=i\end{subarray}}\sum_{\begin{subarray}{c}Q\subseteq\\{1,n\\},\\\
\\#Q=j\end{subarray}}\binom{d-\sum_{p\in P}(\alpha_{p}+1)-\sum_{q\in
Q}\alpha_{q}+n-2}{n-1}$

different equivalent classes of maximal cliques in the graph
$\mathcal{G}(d,{\bm{\alpha}})$, and there are

$\displaystyle H\coloneqq\sum_{i,j\geq
0}(-1)^{i+j}\sum_{\begin{subarray}{c}P\subseteq\\{2,3,\dots,n-1\\},\\\
\\#P=i\end{subarray}}\sum_{\begin{subarray}{c}Q\subseteq\\{1,n\\},\\\
\\#Q=j\end{subarray}}\binom{d-\sum_{p\in P}(\alpha_{p}-1)-\sum_{q\in
Q}\alpha_{q}}{n-1}$

equivalent classes which have precisely $(n-1)!$ maximal cliques. In
particular, there exists at most $H\cdot(n-1)!+(G-H)\cdot(n-1)!/2$ different
maximal cliques.

###### Proof.

It is clear that
$\operatorname{dim}({\mathbb{K}}[{\bm{T}}])=\\#V_{n,d}^{{\bm{\alpha}}}$ is
equal to the number of ways to write $a_{1}+\cdots+a_{n}=d$ such that $0\leq
a_{i}\leq\alpha_{i}$. Furthermore, by 3.10 and 4.3, the number $G$ of
equivalent classes of maximal cliques is the number of ways to have
$a_{1}+\cdots+a_{n}=d$, under the conditions that $0\leq a_{i}\leq\alpha_{i}$
for $i=2,\ldots,n-1$, $1\leq a_{1}\leq\alpha_{1}$, and $0\leq
a_{n}\leq\alpha_{n}-1$. It is not hard to see that
$G=\\#V_{n,d-1}^{{\bm{\alpha}}^{\prime}}$, where
${\bm{\alpha}}^{\prime}=(\alpha_{1}-1,\alpha_{2},\alpha_{3},\dots,\alpha_{n-1},\alpha_{n}-1)$.
Similarly, by 5.2, finding the number $H$ is counting how many possible ways
one can write $a_{1}+\cdots+a_{n}=d$, subject to the conditions $1\leq
a_{i}\leq\alpha_{i}-1$ for $i=2,\ldots,n-1$, $1\leq a_{1}\leq\alpha_{1}$, and
$0\leq a_{n}\leq\alpha_{n}-1$. It is not difficult to see that
$H=\\#V_{n,d-(n-1)}^{{\bm{\alpha}}^{\prime\prime}}$, where
${\bm{\alpha}}^{\prime\prime}=(\alpha_{1}-1,\alpha_{2}-2,\alpha_{3}-2,\dots,\alpha_{n-1}-2,\alpha_{n}-1)$.
The three formulas given above then follow from the classical _stars and bars
method_ and the _inclusion-exclusion principle_ in combinatorics.

Notice that if an equivalence class $\mathcal{E}$ does not have $(n-1)!$
maximal cliques, then its poset of obstructions is not trivial by 5.2. Say, we
have $p\,\triangleleft\,q$ in this poset. Then, for any $A\in\mathcal{E}$, we
have $p$ preceding $q$ in $\operatorname{sgn}(A)$. Thus,

$\\#\mathcal{E}=\\#\Set{\operatorname{sgn}(A):A\in\mathcal{E}}\leq(n-1)!/2,$

namely, $\mathcal{E}$ contains at most $(n-1)!/2$ maximal cliques. The “in
particular” part then follows. ∎

For a homogeneous $\mathbb{K}$-algebra $R$, let $\mathtt{e}(R)$ denote its
_multiplicity_ with respect to its graded maximal ideal. This number is clear
in the squarefree case, by the work of Terai [MR1715588].

######  Lemma 5.10 ([MR1715588, Lemma 4.1]).

Let $\mathfrak{a}$ be a squarefree monomial ideal in a polynomial ring $A$.
Then $\mathtt{e}(A/\mathfrak{a})=\beta_{1,h_{1}}(A/\mathfrak{a}^{\vee})$,
where $h_{1}=\operatorname{indeg}(\mathfrak{a}^{\vee})$ is the initial degree
of the Alexander dual ideal $\mathfrak{a}^{\vee}$.

######  Corollary 5.11.

The multiplicity of $\mathcal{A}_{d,{\bm{\alpha}}}$ is equal to
$\\#\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}))$.

###### Proof.

Note that $\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})$ can be calculated from
the Hilbert series of
$\mathcal{A}_{d,{\bm{\alpha}}}\cong{\mathbb{K}}[{\bm{T}}]/J$. Meanwhile, the
Hilbert series of ${\mathbb{K}}[{\bm{T}}]/J$ and
${\mathbb{K}}[{\bm{T}}]/\operatorname{in}(J)$ coincide. Thus, thanks to 5.10,
in order to find $\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})$, we only need to
compute the minimal number of generators of the equigenerated squarefree
monomial ideal $(\operatorname{in}(J))^{\vee}$. This number is obviously the
number of maximal cliques of $\mathcal{G}$. ∎

In addition, Terai gave the following upper bound on multiplicity.

######  Lemma 5.12 ([MR1715588, Theorem 4.2]).

Let $R=A/\mathfrak{a}$ be a homogeneous $\mathbb{K}$-algebra of codimension
$g\geq 2$. Then

$\mathtt{e}(R)\leq\binom{\operatorname{reg}(R)+g}{g}-\binom{\operatorname{reg}(R)-\operatorname{indeg}(\mathfrak{a})+g}{g}.$

Relatedly, Eisenbud and Goto in [MR0741934] made a conjecture linking
Castelnuovo-Mumford regularity and multiplicity. Although a counterexample was
recently given by McCullough and Peeva in [MR3758150], the statement of the
original conjecture still holds in the Cohen-Macaulay case.

######  Lemma 5.13 ([MR2103875, Corollary 4.15]).

Suppose that $A$ is a polynomial ring over an algebraically closed field. If
$\mathfrak{a}$ is a nondegenerated homogeneous prime ideal in $A$ and
$A/\mathfrak{a}$ is Cohen–Macaulay, then

$\operatorname{reg}(A/\mathfrak{a})\leq\mathtt{e}(A/\mathfrak{a})-\operatorname{codim}(\mathfrak{a}).$

We are ready to state our final result regarding the multiplicity of
$\mathcal{A}_{d,{\bm{\alpha}}}$.

######  Theorem 5.14.

Suppose that $\mathcal{A}_{d,{\bm{\alpha}}}={\mathbb{K}}[I_{d,{\bm{\alpha}}}]$
is the Veronese type algebra of 2.3 whose presentation ideal $J$ is not zero.
Let $r\coloneqq\operatorname{reg}(\mathcal{A}_{d,{\bm{\alpha}}})$,
$t\coloneqq\operatorname{dim}({\mathbb{K}}[{\bm{T}}])$, $G$ and $H$ be the
numbers that we computed in 5.6 and 5.9. Furthermore, we write $d_{1}\coloneqq
d$ and $d_{2}\coloneqq\sum_{i=1}^{n}\alpha_{i}-d$. Then, we have

$\displaystyle r+t-n\leq\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})$
$\displaystyle\leq\min\Bigg{\\{}H\cdot(n-1)!+\frac{(G-H)\cdot(n-1)!}{2},\;d_{1}^{n-1},\;d_{2}^{n-1},\;$
$\displaystyle\qquad\qquad\qquad\binom{r+t-n}{t-n}-\binom{r-2+t-n}{t-n}\Bigg{\\}}.$

###### Proof.

The codimension of $J$ is $t-n$ by 2.6. Since we can replace ${\mathbb{K}}$ by
its algebraic closure, the first inequality follows from 5.13. As for the
second inequality, we apply first Lemmas 5.9 and 5.11. In addition, notice
that the multiplicity in the Veronese case is well-known:
$\mathtt{e}(\mathcal{A}_{d_{1},(d_{1},\ldots,d_{1})})=d_{1}^{n}$. Since
obviously
$\operatorname{MC}(\mathcal{G}(d,{\bm{\alpha}}))\subseteq\operatorname{MC}(\mathcal{G}(d_{1},(d_{1},\dots,d_{1})))$,
we have $\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})\leq d_{1}^{n-1}$ by 5.11.
Similarly, since
$\mathcal{A}_{d,{\bm{\alpha}}}\cong\mathcal{A}_{d_{2},{\bm{\alpha}}}$, we also
have $\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})\leq d_{2}^{n-1}$. As for the
remaining piece, we observe that the presentation ideal $J$ and its initial
ideal are quadratic by 2.5. Thus, when $\operatorname{codim}(J)\geq 2$, we can
apply 5.12. If instead $\operatorname{codim}(J)=1$, since
$\operatorname{in}(J)$ is height-unmixed, squarefree, and has the same height,
this initial ideal is the intersection of principal monomial prime ideals.
Consequently, the quadratic ideal $\operatorname{in}(J)$ is generated by a
squarefree monomial of degree $2$. In particular,
$\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})=\mathtt{e}({\mathbb{K}}[{\bm{T}}]/\operatorname{in}(J))=2$.
On the other hand,

$\binom{r+t-n}{t-n}-\binom{r-2+t-n}{t-n}=\binom{r+1}{1}-\binom{r-2+1}{1}=2,$

which means that we have equality in this case. ∎

######  Example 5.15.

Let ${\bm{\alpha}}=(1,4,4,5,7)$ and $d=7$. Using the notation in 5.14, we have
that $d_{2}^{4}=(21-7)^{4}=14^{4}=38416>d_{1}^{4}=7^{4}=2401$. By 5.9, we have
$t=171$, $G=75$, and $H=18$. Therefore $H\cdot(5-1)!+(G-H)\cdot(5-1)!/2=1116$.
By 5.6, we have
$r=\operatorname{reg}(\mathcal{F}(\operatorname{Sss}({\bm{\eta}})))=5-1=4$.
Thus, $r+t-n=4+171-5=170$ and

$\displaystyle\binom{r+t-n}{t-n}-\binom{r-2+t-n}{t-n}$
$\displaystyle=\binom{4+171-5}{171-5}-\binom{4-2+171-5}{171-5}$
$\displaystyle=33571342.$

It follows from 5.14 that we can obtain

$170\leq\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})\leq 1116.$

By directly enumerating the maximal cliques, we can check that
$\mathtt{e}(\mathcal{A}_{d,{\bm{\alpha}}})=960$ by 5.10.

######  Acknowledgment.

The authors are grateful to the software system Macaulay2 [M2], for serving as
an excellent source of inspiration. The second author is partially supported
by the “Anhui Initiative in Quantum Information Technologies” (No. AHY150200)
and the “Innovation Program for Quantum Science and Technology”
(2021ZD0302902).

## References