1 Introduction
Let
$S={\mathbb K}[x_{1},\dots ,x_{n}]$
be a polynomial ring over a field
${\mathbb K}$
with
$n\ge 2$
. Suppose that I is an ideal minimally generated by some monomials
$f_1,\ldots , f_u$
in S. The semigroup ring associated with 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
${\boldsymbol {\alpha }}=(\alpha _1,\ldots , \alpha _n)$
of integers with
$1\le \alpha _1 \le \cdots \leq \alpha _n\le d$
and
$d <\sum _{i=1}^n \alpha _i$
. Let
${\mathbb N}=\{0,1,2,\dots \}$
be the set of non-negative integers and
be an ideal of Veronese type. Related, let
${\mathcal {A}}_{d,{\boldsymbol {\alpha }}}={\mathbb K}[I_{d,{\boldsymbol {\alpha }}}]\subset S$
and call it an algebra of Veronese type. If
$\alpha _1=\cdots =\alpha _n$
, then
$I_{d,{\boldsymbol {\alpha }}}$
is a special strongly symmetric shifted ideal. Moreover, if
$\alpha _i=d$
for all i, then
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is the d-th Veronese subring of S. Algebras of Veronese type have been studied from various viewpoints (see [Reference Bărcănescu and Manolache4, Reference Bărcănescu5, Reference Sturmfels27]). De Negri and Hibi also classified the Gorensteinness of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
in [Reference De Negri and Hibi9, Theorem 2.4]. In addition, Costantini and Seceleanu studied algebras associated with strongly symmetric shifted ideals in [Reference Costantini and Seceleanu8]. In this article, we continue their work and compute the Castelnuovo–Mumford regularity and the multiplicity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
.
Recall that for a finitely generated graded module M over the polynomial ring S, the Castelnuovo–Mumford regularity of M, denoted by
$\mathrm {reg}(M)$
, is
$\max \{j-i : \beta _{i,j}\ne 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):=\mathrm {dim}_{{\mathbb K}}(M_k)$
is eventually a polynomial in k of degree
$\mathrm {dim}(M)-1$
. The leading coefficient of this polynomial is of form
$\mathtt {e}(M)/(\mathrm {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}[{\boldsymbol {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}[{\boldsymbol {T}}]\rightarrow {\mathbb K}[I]$
with
$\psi (T_{f_i})=f_i$
. Obviously, J is a prime ideal and we have
${\mathbb K}[{\boldsymbol {T}}]/J \cong {\mathbb K}[I]$
.
The study of algebra
${\mathbb K}[I]$
becomes more feasible if such a Gröbner basis of the presentation ideal J is known (see [Reference Biermann, O’Keefe and Van Tuyl2] for the case of chordal bipartite graphs, [Reference Nitsche25] for the d-th Veronese subring, and [Reference Lin and Shen23] for the case of three-dimensional Ferrers diagrams. This is because the invariants of the initial ideal and the original ideal are closely related (cf. [Reference Herzog and Hibi18, Section 3.3]. According to the work of Conca and Varbaro in [Reference Conca and Varbaro6], 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. [Reference Hoa and Stückrad20]).
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 [Reference Fröberg14]. The authors of the current article proved in [Reference Lin and Shen22] 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 [Reference Lin and Shen23]. 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 [Reference Sturmfels27] proved that the presentation ideal of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
has a quadratic Gröbner basis. More recently, Herzog et al. [Reference Herzog, Hibi and Moradi19] 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,{\boldsymbol {\alpha }}}$
in more detail. As a main result, we obtain the Castelnuovo–Mumford regularity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
explicitly in Theorem 5.6. This generalizes the result [Reference Bruns, Vasconcelos and Villarreal3, Corollary 2.12, Remark 2.13] of Bruns, Vasconcelos, and Villarreal and [Reference Nitsche25, 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,{\boldsymbol {\alpha }}}$
in Theorem 5.15. Notice that, the multiplicity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is actually the normalized volume of the Newton polytope of the ideal
$I_{d,{\boldsymbol {\alpha }}}$
, as it is an Ehrhart ring by [Reference Escobar, Villarreal and Yoshino13, Corollary 4.10].
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,{\boldsymbol {\alpha }}}$
. From the initial ideal of the presentation ideal J of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
, we introduce a structural graph
$\mathcal {G}_{d,{\boldsymbol {\alpha }}}$
and study its maximal cliques. As a result, we derive the generators of the Alexander dual of
$\mathrm {in}(J)$
in Corollary 3.11. In Section 4, we propose a carefully constructed order in Setting 4.13. With it, we show in Theorem 4.22 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 article, we fix a positive integer
$n\ge 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
-
(a) Let
${\boldsymbol {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
${\boldsymbol {a}}=(a_1,\dots ,a_n)\in {\mathbb Z}^n$
. Following this convention, if we encounter several tuples
${\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^t\in {\mathbb Z}^n$
, we will have
${\boldsymbol {a}}^i=(a_1^i,\dots ,a_n^i)$
for each
$i\in [t]$
. -
(b) Suppose that
${\boldsymbol {a}}\in {\mathbb N}^n$
. We will write
${\boldsymbol {x}}^{\boldsymbol {a}}$
for the monomial
$x_1^{a_1}\ldots x_n^{a_n}$
in S and define . -
(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 [Reference Sturmfels27, Chapter 14] a sorting operator for monomials of the same degree.
Definition 2.2 Let 
.
-
(i) Let
${\mathrm {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\ge 2$
: which is defined as follows. Suppose that
$$\begin{align*}\mathrm{sort}: \underbrace{{\mathrm{Mon}}_d\times \cdots \times {\mathrm{Mon}}_d}_{p\ \text{times}} \to \underbrace{{\mathrm{Mon}}_d\times \cdots \times {\mathrm{Mon}}_d}_{p\ \text{times}},\qquad (u_1,\dots,u_p)\mapsto (v_1,\dots,v_p), \end{align*}$$
$u_1\ldots u_p=x_{i_1}x_{i_2}\ldots x_{i_{pd}}$
with
$i_1\le i_2\le \cdots \le i_{pd}$
. Then, for
$k\in [p]$
. The sequence
$(u_1,\dots ,u_p)$
of monomials in
${\mathrm {Mon}}_d$
is called sorted if
$\mathrm {sort}(u_1,\dots ,u_p)=(u_1,\dots ,u_p)$
. A subset U of
$V_{n,d}$
is sortable if
$\mathrm {sort}(U\times U)\subseteq U\times U$
.
-
(ii) Since we have a natural correspondence between
${\boldsymbol {x}}^{{\boldsymbol {a}}}\in {\mathrm {Mon}}_d$
and
${\boldsymbol {a}}\in V_{n,d}$
, by abuse of notation, we also derive a sorting operator Similarly, we can also talk about whether a subset of
$$\begin{align*}\mathrm{sort}:V_{n,d}\times \cdots \times V_{n,d} \to V_{n,d} \times \cdots \times V_{n,d}. \end{align*}$$
$V_{n,d}$
is sortable.
for 
In this article, we always assume the following.
Setting 2.3 Suppose that
$n\ge 3$
. We fix a degree d and a sequence
${\boldsymbol {\alpha }}=(\alpha _1,\ldots , \alpha _n)$
of integers with
$1\le \alpha _1 \le \cdots \leq \alpha _n\le d$
and
$d <|{\boldsymbol {\alpha }}| $
. Let 
. Furthermore, let 
be the Veronese type ideal in S, and
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}=\mathbb{K}[I_{d,{\boldsymbol {\alpha }}}]$
be the Veronese type algebra.
Remark 2.4
-
(a) When
$n=2$
, it is not difficult to see that the Veronese type algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is isomorphic to a Veronese ring, up to a shift. -
(b) If
$d=|{\boldsymbol {\alpha }}|$
, then the Veronese type algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is generated principally by the monomial
${\boldsymbol {x}}^{{\boldsymbol {\alpha }}}$
. -
(c) The Krull dimension of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is n by [Reference De Negri and Hibi9, Corollary 2.2(4)].
Remark 2.5 Let
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
be the Veronese type algebra in Setting 2.3. Since
$V_{n,d}^{{\boldsymbol {\alpha }}}$
is sortable by [Reference Ene and Herzog12, Proposition 6.11], the set
is a Gröbner basis of the presentation ideal J of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
with respect to a term order such that the marked (underlined) monomials are the leading terms by [Reference Ene and Herzog12, Theorem 6.16]. In particular, J has a quadratic squarefree initial ideal. Consequently,
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is a Cohen–Macaulay–Koszul normal domain, by [Reference De Negri and Hibi9, Corollary 2.2], [Reference Ene and Herzog12, Theorems 5.16, 5.17, and 6.7], and [Reference Escobar, Villarreal and Yoshino13, Corollary 4.10].
3 Maximal cliques
Let
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
be the Veronese type algebra in Setting 2.3. In one of the main results of this article, we determine the Castelnuovo–Mumford regularity of the algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
. Recall that if
$\beta _{i,j}$
is the graded Betti number of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
considered as a
${\mathbb K}[{\boldsymbol {T}}]$
-module, then the Castelnuovo–Mumford regularity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is defined to be
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,{\boldsymbol {\alpha }}}$
generated by the set
$\mathscr {J}$
in Remark 2.5. Since
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is Cohen–Macaulay and
$\mathrm {in}(J)$
is squarefree by Remark 2.5, it follows from [Reference Conca and Varbaro6, Corollary 2.7] that the quotient ring
${\mathbb K}[{\boldsymbol {T}}]/\mathrm {in}(J)$
is Cohen–Macaulay. Let
$(\mathrm {in}(J))^\vee $
be the Alexander dual of the squarefree ideal
$\mathrm {in}(J)$
. By [Reference Conca and Varbaro6, Corollary 2.7] and [Reference Herzog and Hibi18, Proposition 8.1.10],
$\mathrm {reg}(\mathcal {A}_{d,{\boldsymbol {\alpha }}})=\mathrm {reg}({\mathbb K}[{\boldsymbol {T}}]/J) = \mathrm {reg}({\mathbb K}[{\boldsymbol {T}}]/\mathrm {in}(J))=\mathrm {pd}((\mathrm {in}(J))^\vee )$
.
Inspired by the above observation, we turn to find the projective dimension of
$(\mathrm {in}(J))^\vee $
. To do this, we proceed as follows. First, since
${\mathbb K}[{\boldsymbol {T}}]/\mathrm {in}(J)$
is Cohen–Macaulay,
$(\mathrm {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 Proposition 3.5. Then, in Section 4, we give a total order on the minimal monomial generating set
$G((\mathrm {in}(J))^\vee )$
and show that
$(\mathrm {in}(J))^\vee $
has linear quotients with respect to this order. Details of these quotients are important by the following lemma.
Lemma 3.2 [Reference Herzog and Hibi18, 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 
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
$\#\{i:\mu (Q_i)=p\}$
. In particular, the projective dimension of I is given by p.
Definition 3.3
-
(a) Recall that
$V_{n,d}$
is the set
$\{{\boldsymbol {a}}\in {\mathbb N}^n:|{\boldsymbol {a}}|=d\}$
. For any distinct
${\boldsymbol {a}}, {\boldsymbol {b}} \in V_{n,d}$
, we write
${\boldsymbol {a}}>_{{\mathrm {lex}}} {\boldsymbol {b}}$
if the leftmost nonzero entry of
${\boldsymbol {a}}-{\boldsymbol {b}}$
is positive. -
(b) Let
${\boldsymbol {\eta }} = (\eta _1,\dots ,\eta _n)$
be the smallest tuple in
$V_{n,d}^{{\boldsymbol {\alpha }}}$
with respect to
$>_{{\mathrm {lex}}}$
, namely, if
${\boldsymbol {a}} \in V_{n,d}^{{\boldsymbol {\alpha }}}$
, then
${\boldsymbol {a}} \ge _{{\mathrm {lex}}} {\boldsymbol {\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$
. -
(c) Let
$\mathcal {G}=\mathcal {G}(d,{\boldsymbol {\alpha }})$
be a simple graph on the set
$V_{n,d}^{{\boldsymbol {\alpha }}}$
, such that
$\{{\boldsymbol {a}},{\boldsymbol {b}}\}$
with
${\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}$
is an edge if and only if
$({\boldsymbol {a}},{\boldsymbol {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
$\mathrm {MC}(\mathcal {G})=\mathrm {MC}(\mathcal {G}(d,{\boldsymbol {\alpha }}))$
be the set of maximal cliques of
$\mathcal {G}$
.
Remark 3.4
-
(a) If
$({\boldsymbol {a}},{\boldsymbol {b}})$
is a sorted pair in
$V_{n,d}$
, then
${\boldsymbol {a}}\ge _{{\mathrm {lex}}}{\boldsymbol {b}}$
. -
(b) The fact (ii) before [Reference Sturmfels27, Theorem 14.2] can be restated as follows. Suppose that
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}} {\boldsymbol {a}}^2>_{{\mathrm {lex}}} \cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^s\}$
is a subset of
$V_{n,d}^{{\boldsymbol {\alpha }}}$
such that
$\mathrm {sort}({\boldsymbol {a}}^i,{\boldsymbol {a}}^j)=({\boldsymbol {a}}^i,{\boldsymbol {a}}^j)$
for all
$1\le i<j\le s$
. Then,
$\mathrm {sort}({\boldsymbol {a}}^1,{\boldsymbol {a}}^2,\dots , {\boldsymbol {a}}^s) =({\boldsymbol {a}}^1, {\boldsymbol {a}}^2, \dots , {\boldsymbol {a}}^s)$
. In other words, sorted subsets of
$V_{n,d}^{{\boldsymbol {\alpha }}}$
are precisely cliques in
$\mathcal {G}$
. -
(c) It follows from the description in Remark 2.5 and the fact just stated in (b) that the squarefree monomial ideal
$\mathrm {in}(J)$
is the edge ideal of the complement graph
$\mathcal {G}^{\complement}$
. Suppose that
$T_{{\boldsymbol {a}}^1}T_{{\boldsymbol {a}}^2}\ldots T_{{\boldsymbol {a}}^{m}}\in G(\mathrm {in}(J)^{\vee })$
is a minimal monomial generator of the Alexander dual ideal. This is equivalent to saying that
$\{{\boldsymbol {a}}^1, \dots , {\boldsymbol {a}}^m\}$
is a minimal vertex cover of the complement graph
$\mathcal {G}^{\complement}$
, by [Reference Herzog and Hibi18, Corollary 9.1.5]. In other words, the set complement
$\{{\boldsymbol {a}}^1, \dots , {\boldsymbol {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,{\boldsymbol {\alpha }}}$
is Cohen–Macaulay by Remark 2.5. In other words, the presentation ideal J is Cohen–Macaulay. Since
$\mathrm {in}(J)$
is squarefree, this implies that
$\mathrm {in}(J)$
is Cohen–Macaulay by [Reference Conca and Varbaro6, Corollary 2.7]. In particular,
$\mathrm {in}(J)$
is height unmixed. Notice that
$\mathrm {ht}(\mathrm {in}(J))=\mathrm {ht}(J)=\#{\boldsymbol {T}}-n$
by Remark 2.4, where
$\#{\boldsymbol {T}}$
is the number of variables in
${\mathbb K}[{\boldsymbol {T}}]$
, i.e., the dimension of this polynomial ring. Consequently, every minimal monomial generator of
$\mathrm {in}(J)^{\vee }$
has degree
$\#{\boldsymbol {T}} -n$
, and every maximal clique has size
$\#{\boldsymbol {T}}-(\#{\boldsymbol {T}} -n)=n$
by Remark 3.4(c).
We need more tools to describe these maximal cliques in detail.
Definition 3.6 Let
${\boldsymbol {a}},{\boldsymbol {b}}\in {\mathbb Z}^n$
be two tuples. Suppose that the following condition is satisfied.
-
(S): There exist
$1\le i_1<i_2<\cdots <i_{2k-1}<i_{2k}\le n$
such that
$b_{i_{2j-1}}=a_{i_{2j-1}}-1$
while
$b_{i_{2j}}=a_{i_{2j}}+1$
for
$1\le j\le 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 ({\boldsymbol {a}},{\boldsymbol {b}})$
of this pair is defined to be
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
$\mathrm {length}(\Delta ({\boldsymbol {a}},{\boldsymbol {b}}))$
.
From the definition, we can directly verify the following simple fact.
Remark 3.7 Let
${\boldsymbol {a}}$
and
${\boldsymbol {b}}$
be two tuples in
$V_{n,d}$
, and 
. Since
$\left |{\boldsymbol {a}}\right |=\left |{\boldsymbol {b}}\right |$
, the cardinality of P is even. Whence, we may assume that
$P=\{i_1<i_2<\cdots <i_{2k}\}$
. Suppose that
$\mathrm {sort}({\boldsymbol {a}},{\boldsymbol {b}})=({\boldsymbol {c}},{\boldsymbol {d}})$
. One can verify, using the definition of the sorting operator, that
$$\begin{align*}c_i=d_i=\frac{a_i+b_i}{2} \end{align*}$$
for
$i\notin P$
. Furthermore,
$$\begin{align*}c_{i_{2j-1}}=\frac{a_{2j-1}+b_{2j-1}+1}{2}, \quad d_{i_{2j-1}}=\frac{a_{2j-1}+b_{2j-1}-1}{2}, \quad c_{i_{2j}}=\frac{a_{2j}+b_{2j}-1}{2}, \quad d_{i_{2j}}=\frac{a_{2j}+b_{2j}+1}{2}, \end{align*}$$
for
$1\le j\le k$
.
Lemma 3.8 Let
${\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}$
be two tuples in
$V_{n,d}$
. Then,
$\mathrm {sort}({\boldsymbol {a}},{\boldsymbol {b}})=({\boldsymbol {a}},{\boldsymbol {b}})$
if and only if the condition (S) is satisfied.
Proof This follows directly from the observation in Remark 3.7.
The following are further important observations when using the sorting operator.
Lemma 3.9 If
$\{{\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}>_{{\mathrm {lex}}}{\boldsymbol {c}}\}$
is a sorted subset in
$V_{n,d}$
, then
$\Delta ({\boldsymbol {a}},{\boldsymbol {c}})=\Delta ({\boldsymbol {a}},{\boldsymbol {b}})\sqcup \Delta ({\boldsymbol {b}},{\boldsymbol {c}})$
.
Proof It suffices to show that
$\Delta ({\boldsymbol {a}},{\boldsymbol {b}}) \cap \Delta ({\boldsymbol {b}},{\boldsymbol {c}}) =\emptyset $
. Suppose for contradiction that
$\Delta ({\boldsymbol {a}},{\boldsymbol {b}}) \cap \Delta ({\boldsymbol {b}},{\boldsymbol {c}})$
is not empty. Then, we can find suitable intersecting 
and 
in the definition of
$\Delta ({\boldsymbol {a}},{\boldsymbol {b}})$
and
$\Delta ({\boldsymbol {b}}, {\boldsymbol {c}}),$
respectively. Let j and
$j'$
be the smallest such that this happens.
-
(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
$({\boldsymbol {a}},{\boldsymbol {c}})$
is a sorted pair by Lemma 3.8. -
(b) Suppose that
$i_{2j-1}<i_{2j^{\prime }-1}^{\prime }<i_{2j}$
. Now, we derive
$i_{2j^{\prime }-2}^{\prime }\le 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\le i_{2j-1}}a_k=\sum _{k\le i_{2j-1}}b_k=\sum _{k\le 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. -
(c) Suppose that
$i_{2j^{\prime }-1}^{\prime }<i_{2j-1}<i_{2j^{\prime }}^{\prime }$
. This case is similar to (b) above.
Lemma 3.10
-
(a) If
$\{{\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}>_{{\mathrm {lex}}}{\boldsymbol {d}}\}$
and
$\{{\boldsymbol {b}}>_{{\mathrm {lex}}}{\boldsymbol {c}}>_{{\mathrm {lex}}}{\boldsymbol {d}}\}$
are two cliques in
$\mathcal {G}$
, then
$\{{\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}>_{{\mathrm {lex}}}{\boldsymbol {c}} >_{{\mathrm {lex}}}{\boldsymbol {d}}\}$
is also a clique in
$\mathcal {G}$
. -
(b) Symmetrically, if
$\{{\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}>_{{\mathrm {lex}}}{\boldsymbol {c}}\}$
and
$\{{\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {c}}>_{{\mathrm {lex}}}{\boldsymbol {d}}\}$
are two cliques in
$\mathcal {G}$
, then
$\{{\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}>_{{\mathrm {lex}}}{\boldsymbol {c}} >_{{\mathrm {lex}}}{\boldsymbol {d}}\}$
is also a clique in
$\mathcal {G}$
.
Proof By symmetry, we will only consider the first case. Since
$\Delta ({\boldsymbol {a}},{\boldsymbol {b}})\cap \Delta ({\boldsymbol {b}},{\boldsymbol {d}})=\emptyset $
while
$\Delta ({\boldsymbol {b}},{\boldsymbol {c}})\subseteq \Delta ({\boldsymbol {b}},{\boldsymbol {d}})$
by Lemma 3.9, we have
$\Delta ({\boldsymbol {a}},{\boldsymbol {b}})\cap \Delta ({\boldsymbol {b}},{\boldsymbol {c}})=\emptyset $
. Then, we can apply Lemmas 3.8 and 3.9 to show that
$\mathrm {sort}({\boldsymbol {a}},{\boldsymbol {c}})=({\boldsymbol {a}},{\boldsymbol {c}})$
with
$\Delta ({\boldsymbol {a}},{\boldsymbol {c}}) =\Delta ({\boldsymbol {a}},{\boldsymbol {b}})\sqcup \Delta ({\boldsymbol {b}},{\boldsymbol {c}})$
. Whence,
$\{{\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}>_{{\mathrm {lex}}}{\boldsymbol {c}} >_{{\mathrm {lex}}}{\boldsymbol {d}}\}$
is a clique in
$\mathcal {G}$
.
We know from Proposition 3.5 that every maximal clique has cardinality n. Additional information can be drawn here.
Corollary 3.11 For each maximal clique
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}}\cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n\}$
in
$\mathcal {G}$
, we have
$\mathrm {length}(\Delta ({\boldsymbol {a}}^i,{\boldsymbol {a}}^j))=j-i$
when
$1\le i < j \le n$
. Furthermore,
$\Delta ({\boldsymbol {a}}^1,{\boldsymbol {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 ({\boldsymbol {a}}^1,{\boldsymbol {a}}^n)\subseteq [1,n)$
and
$\mathrm {length}(\Delta ({\boldsymbol {a}}^1,{\boldsymbol {a}}^n))\ge \sum _{i=1}^{n-1} \mathrm {length}(\Delta ({\boldsymbol {a}}^i, {\boldsymbol {a}}^{i+1}))\ge n-1$
by Lemma 3.9, the first two statements are clear. The last statement follows from the definition of the sorting signature set.
Corollary 3.12 Let
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}}{\boldsymbol {a}}^2>_{{\mathrm {lex}}}\cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n >_{{\mathrm {lex}}}{\boldsymbol {a}}^{n+1}\}$
be a set of vertices in
$\mathcal {G}$
. Suppose that
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}}{\boldsymbol {a}}^2 >_{{\mathrm {lex}}} \cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n\}$
is a maximal clique of
$\mathcal {G}$
and
$\Delta ({\boldsymbol {a}}^1,{\boldsymbol {a}}^2)=\Delta ({\boldsymbol {a}}^n,{\boldsymbol {a}}^{n+1})$
. Then,
$\{{\boldsymbol {a}}^2>_{{\mathrm {lex}}}\cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n >_{{\mathrm {lex}}} {\boldsymbol {a}}^{n+1}\}$
is also a maximal clique of
$\mathcal {G}$
.
Proof We have
$\Delta ({\boldsymbol {a}}^2,{\boldsymbol {a}}^n)\sqcup \Delta ({\boldsymbol {a}}^n,{\boldsymbol {a}}^{n+1})=\Delta ({\boldsymbol {a}}^2,{\boldsymbol {a}}^n)\sqcup \Delta ({\boldsymbol {a}}^1,{\boldsymbol {a}}^{2})=\Delta ({\boldsymbol {a}}^1,{\boldsymbol {a}}^n)=[1,n)$
by Corollary 3.11. Thus, we can verify by definition that
$\Delta ({\boldsymbol {a}}^2,{\boldsymbol {a}}^{n+1})=[1,n)$
. In particular,
$\{{\boldsymbol {a}}^2>_{{\mathrm {lex}}}{\boldsymbol {a}}^{n+1}\}$
is an edge of
$\mathcal {G}$
by Lemma 3.8. Now, as
$\{{\boldsymbol {a}}^2>_{{\mathrm {lex}}} \cdots >_{{\mathrm {lex}}} {\boldsymbol {a}}^n\}$
is a clique and
$\{{\boldsymbol {a}}^n>_{{\mathrm {lex}}} {\boldsymbol {a}}^{n+1}\}$
is an edge,
$\{{\boldsymbol {a}}^2>_{{\mathrm {lex}}}\cdots >_{{\mathrm {lex}}} {\boldsymbol {a}}^n>_{{\mathrm {lex}}}{\boldsymbol {a}}^{n+1}\}$
is also a maximal clique of
$\mathcal {G}$
by Lemma 3.10.
4 Linear quotients
In this section, we continue to assume that
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is the Veronese type algebra of Setting 2.3 and
${\boldsymbol {\eta }}$
is the tuple given in Definition 3.3. As explained at the beginning of Section 3, we intend to show that the Alexander dual ideal
$(\mathrm {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,{\boldsymbol {\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(\mathrm {in}(J)^\vee )$
, such that with respect to this order, the ideal
$\mathrm {in}(J)^\vee $
has linear quotients. Let
$\mathrm {MC}(\mathcal {G})$
be the set of maximal cliques of the graph
$\mathcal {G}=\mathcal {G}(d,{\boldsymbol {\alpha }})$
. As observed in Remark 3.4(c),
Thus, we will consider the corresponding total order, still denoted by
$\prec $
, on
$\mathrm {MC}(\mathcal {G})$
. By definition, we want to show that the quotient ideal 
is generated by some ring variables of
${\mathbb K}[{\boldsymbol {T}}]$
for each
$A\in \mathrm {MC}(\mathcal {G})$
. Notice that
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 Setting 4.13. Before that, we need to make some preparations.
Definition 4.1
-
(a) A priori, a maximal clique of the graph
$\mathcal {G}$
is a set of vertices. When we write a maximal clique
$A=({\boldsymbol {a}}^1, {\boldsymbol {a}}^2, \dots , {\boldsymbol {a}}^n)$
in the tuple form, we intend to indicate that
${\boldsymbol {a}}^1>_{\mathrm {lex}} {\boldsymbol {a}}^2>_{\mathrm {lex}} \cdots >_{\mathrm {lex}} {\boldsymbol {a}}^n$
. -
(b) Two maximal cliques
$A=({\boldsymbol {a}}^1,{\boldsymbol {a}}^2,\dots ,{\boldsymbol {a}}^n)$
and
$B=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^n)$
are called equivalent, if and only if
${\boldsymbol {a}}^1={\boldsymbol {b}}^1$
. It follows from Corollary 3.11 that this is also equivalent to saying that
${\boldsymbol {a}}^n={\boldsymbol {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. -
(c) The rank of a tuple
${\boldsymbol {a}}=(a_1,\dots ,a_n)\in V_{n,d}$
(with respect to the given tuple
${\boldsymbol {\eta }}$
) is defined to be It is clear that
$\mathrm {rank}({\boldsymbol {\eta }})=0$
. Furthermore, if
${\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}$
belong to some common maximal clique of
$\mathcal {G}$
, then it is easy to verify directly that
$\mathrm {rank}({\boldsymbol {a}})= \mathrm {rank}({\boldsymbol {b}})+ \mathrm {length}(\Delta ({\boldsymbol {a}},{\boldsymbol {b}}))$
.
-
(d) For each maximal clique
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
, we define the rank of
$\mathcal {E}_{A}$
to be
$\mathrm {rank}({\boldsymbol {a}}^n)$
. This is well-defined, since if
$B=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^n)$
and A are equivalent, then
${\boldsymbol {b}}^n={\boldsymbol {a}}^n$
. -
(e) Suppose that
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
, where
${\boldsymbol {a}}^i=(a_1^i,\dots ,a_n^i)\in {\mathbb Z}^n$
and
$\sum _ka_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 ({\boldsymbol {a}}^i,{\boldsymbol {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
$\mathrm {sgn}(A)$
. Of course, we are mostly interested in the case, where A is a maximal clique of
$\mathcal {G}$
. Whence, by Lemma 3.9 and Corollary 3.11, the signature of A must exist. -
(f) Let
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
be a maximal clique. If there exists a maximal clique
$B=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^n)$
such that
$({\boldsymbol {a}}^2,\dots ,{\boldsymbol {a}}^n)=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^{n-1})$
, then we will say that B is the root of A and write
$B=rA$
. It follows from Corollary 3.11 that if the root of A exists, then it is unique.
Remark 4.2
-
(a) For any
${\boldsymbol {a}}\in V_{n,d}^{\boldsymbol {\alpha }}$
, if
${\boldsymbol {a}}\ne {\boldsymbol {\eta }}$
, we can find
${\boldsymbol {b}}\in V_{n,d}^{\boldsymbol {\alpha }}$
such that
${\boldsymbol {a}}>_{{\mathrm {lex}}}{\boldsymbol {b}}\ge _{{\mathrm {lex}}} {\boldsymbol {\eta }}$
,
$\mathrm {sort}({\boldsymbol {a}},{\boldsymbol {b}})=({\boldsymbol {a}},{\boldsymbol {b}})$
, and
$\mathrm {length}({\boldsymbol {a}},{\boldsymbol {b}})=1$
. If we use this repeatedly, we can find by induction
${\boldsymbol {b}}^0,{\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^m\in V_{n,d}^{\boldsymbol {\alpha }}$
such that
${\boldsymbol {b}}^0={\boldsymbol {a}}$
,
${\boldsymbol {b}}^m={\boldsymbol {\eta }}$
and
$\mathrm {rank}({\boldsymbol {b}}^i)=\mathrm {rank}({\boldsymbol {b}}^{i+1})+1$
for each i. In particular,
$\mathrm {rank}({\boldsymbol {a}})=m\in {\mathbb N}$
. -
(b) For each maximal clique A, we have
$\mathrm {rank}(A)\in {\mathbb N}$
. -
(c) If
$B=rA$
, then
$\mathrm {rank}(A)=\mathrm {rank}(B)+1$
. -
(d) We have precisely one equivalence class
$\mathcal {E}_A$
such that
$\mathrm {rank}(\mathcal {E}_A)=0$
. If
$B=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^n)$
belongs to such
$\mathcal {E}_A$
, then
${\boldsymbol {b}}^n={\boldsymbol {\eta }}$
.
Here, is the converse of Corollary 3.11.
Lemma 4.3 Let
${\boldsymbol {a}}^1=(a_1^1,\dots ,a_n^1)$
be a tuple in
$V_{n,d}^{{\boldsymbol {\alpha }}}$
. Suppose that
$1 \le a_1^1$
while
$a_n^1 \le \alpha _n-1$
. Then, there exists a maximal clique in
$\mathcal {G}$
of the form
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}} \cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n\}$
.
Proof It is clear that 
belongs to
$V_{n,d}^{{\boldsymbol {\alpha }}}$
, by assumption. Notice that
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}}{\boldsymbol {a}}^n\}$
is a clique in
$\mathcal {G}$
and
$\Delta ({\boldsymbol {a}}^1, {\boldsymbol {a}}^n)=[1,n)$
. Thus, we can complete
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}} {\boldsymbol {a}}^n\}$
to a maximal clique. This maximal clique must have the form
$\{{\boldsymbol {a}}^1>_{{\mathrm {lex}}} \cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n\}$
, due to Proposition 3.5 and the rank reason given at the end of Definition 4.1(c).
Next, we describe a necessary and sufficient condition for a given maximal clique A with
$\mathrm {rank}(A)> 0$
and such that
$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=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
is a maximal clique such that
${\boldsymbol {a}}^1=(a_1^1,\dots ,a_n^1)$
and
$\mathrm {sgn}(A)=(s_1,\dots ,s_{n-1})$
. If
$\mathrm {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
${\boldsymbol {a}}^2=(a_1^2,\dots ,a_n^2)$
. Let
${\boldsymbol {a}}^{n+1}$
be the tuple such that
$\Delta ({\boldsymbol {a}}^2,{\boldsymbol {a}}^{n+1})=[1,n)$
. It is easy to see that
${\boldsymbol {a}}^{n+1}=(a_1^2-1,a_2^2,\dots ,a_{n-1}^2,a_n^2+1)$
and
$\Delta ({\boldsymbol {a}}^n,{\boldsymbol {a}}^{n+1})= [s_1,s_1+1)$
. Then,
$rA$
does not exist if and only if
${\boldsymbol {a}}^2,\dots ,{\boldsymbol {a}}^n,{\boldsymbol {a}}^{n+1}$
is not a legitimate maximal clique. By Corollary 3.12, the latter happens precisely when
${\boldsymbol {a}}^{n+1}\notin V_{n,d}^{{\boldsymbol {\alpha }}}$
, which means either
$a_1^2=0$
or
$a_n^2=\alpha _n$
.
-
(a) Suppose that
$a_1^2=0$
. We claim that
$s_1=1$
. Otherwise,
$s_{j}=1$
for some
$2\le j\le n-1$
. This implies that
${\boldsymbol {a}}^k=(a_1^2,\dots )$
for
$k=1,\dots ,j$
, and
${\boldsymbol {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$
. -
(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=({\boldsymbol {a}}^1,\ldots ,{\boldsymbol {a}}^n)$
and
$B=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^n)$
be two tuples of elements in
${\mathbb Z}^n$
such that
${\boldsymbol {a}}^1={\boldsymbol {b}}^1$
and
${\boldsymbol {a}}^n={\boldsymbol {b}}^n$
. Suppose that
$\mathrm {sgn}(A)= (s_1,\ldots ,s_{n-1})$
and
$\mathrm {sgn}(B)=(t_1,\ldots ,t_{n-1})$
. Then, the following conditions are equivalent for an index
$k\in [n-2]$
:
-
(a) the signature
$\mathrm {sgn}(B)$
takes the form
$(s_1, \ldots ,s_{k-1}, s_{k+1},s_{k}, s_{k+2},\dots ,s_{n-1})$
; -
(b) the difference set
is exactly
$\{k+1\}$
.
is exactly 
If in addition A and B are two maximal cliques in an equivalence class
$\mathcal {E}$
, then the following is an additional equivalent condition:
-
(c) the quotient ideal
is generated by
$T_{{\boldsymbol {a}}^{k+1}}$
.
is generated by 
Proof First, we show that (a)
$\Rightarrow $
(b). By assumption, we have
${\boldsymbol {a}}^1={\boldsymbol {b}}^1$
and
$s_i=t_i$
for
$i=1,2,\dots ,k-1$
. Since
$$\begin{align*}\Delta({\boldsymbol{a}}^{i},{\boldsymbol{a}}^{i+1})=[s_i,s_i+1)= [t_i,t_i+1)=\Delta({\boldsymbol{b}}^{i},{\boldsymbol{b}}^{i+1}), \end{align*}$$
by induction, we have
${\boldsymbol {a}}^j={y b}^j$
for
$j=1,2,\dots ,k$
. Similarly, we have
${y a}^n={\boldsymbol {b}}^n$
and
$s_i=t_i$
for
$i=n-1,n-2,\dots ,k+2$
by assumption. Thus, we also have
${\boldsymbol {a}}^j={\boldsymbol {b}}^j$
for
$j=n, n-1,\dots ,k+2$
. On the other hand, since
$s_k\ne t_k$
while
${\boldsymbol {a}}^k={\boldsymbol {b}}^k$
, we have
$$\begin{align*}\Delta({\boldsymbol{a}}^{k},{\boldsymbol{a}}^{k+1})=[s_k,s_k+1)\ne [t_k,t_k+1) = \Delta({\boldsymbol{b}}^{k},{\boldsymbol{b}}^{k+1}), \end{align*}$$
and hence
${\boldsymbol {a}}^{k+1}\neq {\boldsymbol {b}}^{k+1}$
. It is now clear that
$\mathrm {diff}(A,B)=\{k+1\}$
.
Secondly, we show that (b)
$\Rightarrow $
(a). By assumption, we have
${\boldsymbol {a}}^j={\boldsymbol {b}}^j$
whenever
$j\ne k+1$
. Since
$$\begin{align*}\bigsqcup_{j\le i}\,[s_j,s_j+1) = \Delta({\boldsymbol{a}}^1,{\boldsymbol{a}}^{i+1}) = \Delta({\boldsymbol{b}}^1,{\boldsymbol{b}}^{i+1}) = \bigsqcup_{j\le i}\,[t_j,t_j+1) \end{align*}$$
for all
$1\le i \le k-1$
, we must have
$s_i=t_i$
for each such i. Similarly, we have
$s_i=t_i$
when
$k+2\le i \le n-1$
, by looking at
$\Delta ({\boldsymbol {a}}^i,{\boldsymbol {a}}^{n})=\Delta ({\boldsymbol {b}}^i,{\boldsymbol {b}}^n)$
. Notice that
$\{s_1,\ldots ,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\ne 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 (c) is then clear from Equation (1).
We need tools to determine whether a potential maximal clique is really legitimate.
Definition 4.6 Suppose that
${\boldsymbol {a}}=(a_1,\dots ,a_n)\in V_{n,d}^{{\boldsymbol {\alpha }}}$
. If there exists some
${\boldsymbol {b}}\in V_{n,d}^{{\boldsymbol {\alpha }}}$
such that
$\Delta ({\boldsymbol {a}},{\boldsymbol {b}}) =[s,s+1)$
, we say that we apply an s-jump to
${\boldsymbol {a}}$
in order to get
${\boldsymbol {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=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
is a maximal clique and
$\mathrm {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
${\boldsymbol {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
${\boldsymbol {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
${\boldsymbol {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
$\underline{(i-1) \, \triangleleft \, i}$
. -
• Likewise, if
$a_{i+1}^1=\alpha _{i+1}$
and
$i+1<n$
, then we require that
$\underline{(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 Definition 4.8 is well-defined. Furthermore, suppose that
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
is a maximal clique in
$\mathcal {E}$
and
$\mathrm {sgn}(A) =(s_1, \dots ,s_{n-1})$
. Then, the following condition is satisfied:
-
(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
${\boldsymbol {a}}^i$
in order to get
${\boldsymbol {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 Definition 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 Definition 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
${\boldsymbol {s}}=(s_1,\dots ,s_{n-1})$
be a permutation of in
$\mathfrak {S}_{n-1}$
. Suppose that the condition (PO) is satisfied by
${\boldsymbol {s}}$
. Then,
${\boldsymbol {s}}$
is a legitimate signature with respect to
$\mathcal {E}$
, namely, there exists some
$A\in \mathcal {E}$
such that
$\mathrm {sgn}(A)={\boldsymbol {s}}$
.
Proof Suppose that the maximal cliques in
$\mathcal {E}$
all start with
${\boldsymbol {a}}^1$
and end with
${\boldsymbol {a}}^n$
. It suffices to construct
${\boldsymbol {a}}^2,\dots ,{\boldsymbol {a}}^{n-1}\in V_{n,d}^{{\boldsymbol {\alpha }}}$
, such that
$\Delta ({\boldsymbol {a}}^{i-1},{\boldsymbol {a}}^{i}) =[s_{i-1}, s_{i-1}+1)$
when
$i\ge 2$
. We do this by induction on i. The degenerate base case when
$i=1$
is trivial. Next, assume that
${\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^{i-1}$
have been constructed and
$2\le i\le n-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
${\boldsymbol {a}}^{i-1}$
to get a tuple
${\boldsymbol {a}}^{i}\in V_{n,d}^{{\boldsymbol {\alpha }}}$
. Certainly,
$\Delta ({\boldsymbol {a}}^{i-1},{\boldsymbol {a}}^i)= [s_{i-1},s_{i-1}+1)$
. -
(b) Suppose that
$a_{s_{i-1}}^{i-1}= 0$
. As
$a_{s_{i-1}}^1\ge 0$
, we deduce that
$a_{s_{i-1}}^{i-1}\ne a_{s_{i-1}}^1+1$
. Since
${\boldsymbol {s}}$
is a permutation, we cannot apply the
$s_{i-1}$
-jump before
${\boldsymbol {a}}^{i-1}$
. Thus, it follows from Remark 4.7 that we cannot use the
$(s_{i-1}-1)$
-jump before
${\boldsymbol {a}}^{i-1}$
.-
(i) Suppose that
$s_{i-1}=1$
. Whence,
$s_k\ne 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\ge 1$
. -
(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 Definition 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
${\boldsymbol {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 Remark 4.7 that the
$s_{i-1}$
-jump is applied before
${\boldsymbol {a}}^{i-1}$
, again a contradiction.
-
-
(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.
-
(i) In
$\mathcal {E}$
, we will take a maximal clique
$L=L(\mathcal {E})$
as follows. When
$a_1^1>1$
, we assume that
$\kappa _1=0$
. If instead
$a_1^1=1$
, then let
$\kappa _1$
be the largest integer such that
$\kappa _1\le 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\ge 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 Definition 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 Remark 4.11. Thus, we can choose an L in
$\mathcal {E}$
such that 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. A priori, the
$\mathrm {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 Lemma 4.10.
-
(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 article, we will simply write
$(\mathcal {E},L)$
as
$\mathcal {E}$
. -
(iii) Suppose that
. Now, take any
$A\in \mathcal {E}$
and assume that
$\mathrm {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
${\boldsymbol {\tau }}$
(or equivalently, with respect to L) is . Obviously,
$\mathrm {sgn}_{\boldsymbol {\tau }}(L)=(1,2,\dots ,n-1)$
.
. Now, take any 
. Obviously, 
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
$\mathrm {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
$\mathrm {MC}(\mathcal {G})$
satisfying the following conditions.
-
(a) If
$\mathrm {rank}(B)<\mathrm {rank}(A)$
, then
$B\prec A$
. -
(b) Suppose that
$\mathrm {rank}(B)=\mathrm {rank}(A)$
,
$\mathcal {E}_A\ne \mathcal {E}_B$
, and
$B\prec A$
. Then, for any
$A'\in \mathcal {E}_A$
and
$B'\in \mathcal {E}_B$
, we have
$B'\prec A'$
. Therefore,
$\prec $
also induces a total order on the set of equivalence classes. -
(c) Let
$\mathcal {E}$
be an equivalence class and L be the special maximal clique we chose in Definition 4.12. Suppose that . 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
$\mathrm {sgn}_{{\boldsymbol {\tau }}}(B)-\mathrm {sgn}_{{\boldsymbol {\tau }}}(A)$
is negative.
. The restriction of 
Such a total order
$\prec $
exists, but in general, it is not unique. In the rest of this article, 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 Setting 4.13. Consider
$n=5$
,
$d=8$
, and
${\boldsymbol {\alpha }}=(2,2,2,3,3)$
. Let
$\mathcal {E}$
be the equivalence containing
$$\begin{align*}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)). \end{align*}$$
Write
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^5)$
. Note that
$rA$
does not exist. This is because if
$\Delta ({\boldsymbol {a}}^2,{\boldsymbol {a}}^{5+1})=[1,5)$
, then
${\boldsymbol {a}}^{5+1}= (-1,2,1,3,3)$
, which does not belong to
$V_{n,d}^{{\boldsymbol {\alpha }}}$
. Using the notation in Definition 4.12, we have
$\kappa _1=1$
and
$\kappa _2=4$
. Consequently, we choose a maximal clique L with 
. Since
${\boldsymbol {a}}^1$
is given, we have
$$\begin{align*}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)) \end{align*}$$
for our equivalence class
$\mathcal {E}$
.
The poset of obstructions, defined in Definition 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
${\boldsymbol {\tau }}$
.
Table 1 Ordered maximal cliques in an equivalence class.
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
${\boldsymbol {a}}^1=(1, 1, 1, 3, 2)$
, the maximal clique B satisfying
$\mathrm {sgn}(B)=(1, 4, 2, 3)$
is
$$\begin{align*}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)). \end{align*}$$
We can then check that
$\mathrm {sgn}_{{\boldsymbol {\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 Setting 4.13. Let A be a maximal clique. Given Equation (1), to show that the quotient ideal 
is linear, we show that for every maximal clique
$B\prec A$
, we can find
$C\prec A$
such that
$\#\mathrm {diff}(A,C)=1$
and
$\mathrm {diff}(A,C)\subseteq \mathrm {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=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
and
$B=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^n)$
are two different maximal cliques in the same equivalence class
$\mathcal {E}$
such that
$\mathrm {sgn}(A)=(s_1,\dots ,s_{n-1})$
and
$\mathrm {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}\ne 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
$$\begin{align*}\mathrm{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}) \end{align*}$$
and
$$\begin{align*}\mathrm{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}) \end{align*}$$
for suitable
$p_i$
’s and
$q_i$
’s.
Proof Suppose that
${\boldsymbol {a}}^{k+1}=(a_1^{k+1},\dots ,a_n^{k+1})$
. Then,
$$\begin{align*}{\boldsymbol{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}). \end{align*}$$
Since
${\boldsymbol {a}}^1={\boldsymbol {b}}^1$
and
$s_i=t_i$
for
$i\in [k]$
, we have
${\boldsymbol {b}}^{k+1}={\boldsymbol {a}}^{k+1}$
and consequently
$$\begin{align*}{\boldsymbol{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}). \end{align*}$$
Without loss of generality, we can assume that
$s_{k+1}<t_{k+1}$
.
-
(a) Suppose that
$s_{k+1}+1=t_{k+1}$
. Let
${\boldsymbol {c}}^{k+3}$
be the tuple such that
$\Delta ({\boldsymbol {a}}^{k+2},{\boldsymbol {c}}^{k+3})=[t_{k+1},t_{k+1}+1)$
, namely, Due to the existence of
$$\begin{align*}{\boldsymbol{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}). \end{align*}$$
${\boldsymbol {a}}^{k+2}$
and
${\boldsymbol {b}}^{k+2}$
, it can be verified that
${\boldsymbol {c}}^{k+3}\in V_{n,d}^{{\boldsymbol {\alpha }}}$
. Furthermore,
$\Delta ({\boldsymbol {c}}^{k+3}, {\boldsymbol {a}}^\ell )=\Delta ({\boldsymbol {a}}^{k+1},{\boldsymbol {a}}^{\ell }) \setminus [s_{k+1}, s_{k+1}+2)$
. Whence,
${\boldsymbol {a}}^{k+2}>_{{\mathrm {lex}}} {\boldsymbol {c}}^{k+3} >_{{\mathrm {lex}}}{\boldsymbol {a}}^\ell $
is a clique in
$\mathcal {G}$
. It is then not difficult to see that
${\boldsymbol {a}}^1>_{{\mathrm {lex}}} \dots >_{{\mathrm {lex}}}{\boldsymbol {a}}^{k+2} >_{{\mathrm {lex}}}{\boldsymbol {c}}^{k+3}>_{{\mathrm {lex}}} {\boldsymbol {a}}^\ell >_{{\mathrm {lex}}}\cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n$
is a clique, by Lemma 3.10. As
$\Delta ({\boldsymbol {a}}^1, \dots , {\boldsymbol {a}}^n) =[1,n)$
, we can complete it to a maximal clique, which must have the form
${\boldsymbol {a}}^1>_{{\mathrm {lex}}}\dots >_{{\mathrm {lex}}}{\boldsymbol {a}}^{k+2}>_{{\mathrm {lex}}} {\boldsymbol {c}}^{k+3} >_{{\mathrm {lex}}}{\boldsymbol {c}}^{k+4} >_{{\mathrm {lex}}}>\cdots > {\boldsymbol {c}}^{\ell -1} >_{{\mathrm {lex}}} {\boldsymbol {a}}^\ell >_{{\mathrm {lex}}} \cdots >_{{\mathrm {lex}}}{\boldsymbol {a}}^n$
by Corollary 3.11. We will take this as our expected maximal clique C. Now,
${\boldsymbol {a}}^1>_{{\mathrm {lex}}}\dots >_{{\mathrm {lex}}} {\boldsymbol {a}}^{k+1} >_{{\mathrm {lex}}}{\boldsymbol {b}}^{k+2}>_{{\mathrm {lex}}} {\boldsymbol {c}}^{k+3}>_{{\mathrm {lex}}}{\boldsymbol {c}}^{k+4} >_{{\mathrm {lex}}} \cdots >{\boldsymbol {c}}^{\ell -1}>_{{\mathrm {lex}}}{\boldsymbol {a}}^\ell >_{{\mathrm {lex}}}\cdots >_{{\mathrm {lex}}} {\boldsymbol {a}}^n$
is also a maximal clique, which will be our expected D. One can check directly that they satisfy the requirements.
-
(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 Setting 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
$\mathrm {sgn}(L)={\boldsymbol {\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.
-
(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. -
(b) For any
$A,B\in \mathcal {E}_{j_1,\ldots ,j_k}$
with
$\mathrm {sgn}_{{\boldsymbol {\tau }}}(A)=(p_1,\ldots ,p_{n-1})$
and
$\mathrm {sgn}_{{\boldsymbol {\tau }}}(B)=(q_1,\ldots , q_{n-1})$
, one has
$p_i=q_i$
for all
$i=1,\ldots ,k$
. -
(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
$\mathrm {sgn}_{{\boldsymbol {\tau }}}(A)-\mathrm {sgn}_{{\boldsymbol {\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.
Example 4.17 Let us return to the equivalence class
$\mathcal {E}$
containing the maximal clique
$$\begin{align*}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)) \end{align*}$$
in Example 4.14. The equivalence class
$\mathcal {E}$
contains
$12$
different maximal cliques, which we list in Table 2 in order. The subclasses of level
$4$
containing them, together with their relative signatures, are also provided. In this case, we have
$\mathcal {E}_{1,1}=\{A_1,A_2\}$
and
$\mathcal {E}_{3}=\{A_{10},A_{11},A_{12}\}$
. They are subclasses of level
$2$
and
$1,$
respectively.
Table 2 Subclasses of an equivalence class.
Lemma 4.18 Let
$(\mathcal {E},L)$
be a marked equivalence class with
$\mathrm {sgn}(L)={\boldsymbol {\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 \le 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
${\boldsymbol {\tau }}$
. Then, there is no maximal clique A in
$\mathcal {E}$
such that
$\mathrm {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
$\mathrm {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
${\boldsymbol {\tau }}$
is a legitimate signature and t precedes
$s_{k,j_k}$
with respect to
${\boldsymbol {\tau }}$
, we don’t have
$s_{k,j_k} \,\triangleleft \, t$
with respect to the partial order in Definition 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 Lemma 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
${\boldsymbol {\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.19 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
$\mathrm {sgn}(L)={\boldsymbol {\tau }}$
. In addition, assume that
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
and
$B=({\boldsymbol {b}}^1,\dots ,{\boldsymbol {b}}^n)\in \mathcal {E}$
. Recall that we previously defined 
.
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'}$
with
$j_k'<j_k$
. Then,
$k+1=\min \mathrm {diff}(A,B)$
and it is clear that
$k\le n-2$
. Let us consider a set of maximal cliques
Since
$A\in \mathcal {D}$
, the set
$\mathcal {D}$
is not empty. Let
$A'$
be the first maximal clique in
$\mathcal {D}$
with respect to
$\prec $
and suppose that
$\mathrm {sgn}(A')=(s_1, \dots , s_{n-1})$
. Obviously,
$A'\in \mathcal {E}_{j_1, \dots , j_k}$
and
$A'\preceq A$
. Furthermore, we have both
$\mathrm {diff}(A', B)\subseteq \mathrm {diff}(A, B)$
and
$\mathrm {diff}(A, A')\subseteq \mathrm {diff}(A, B)$
. Let
$C=({\boldsymbol {c}}^{1}, \dots , {\boldsymbol {c}}^n)$
be the tuple of elements in
${\mathbb Z}^n$
, such that
${\boldsymbol {c}}^1={\boldsymbol {a}}^1$
and
$\mathrm {sgn}(C)=(s_1, \dots , s_{k-1}, s_{k+1}, s_k, s_{k+2}, \dots , s_{n-1})$
. By Lemma 4.5,
$\mathrm {diff}(C, A')=\{k+1\}$
. In addition, we claim that C is a legitimate maximal clique in
$\mathcal {E}$
and
$C\prec A'$
. With this, if
$A=A'$
, then we take
$D=C$
since
$\mathrm {diff}(A, B)\supseteq \mathrm {diff}(A, C)=\{k+1\}$
. If instead
$A\ne A'$
, then we will replace B by
$A'$
. Our proof will be done by induction on the cardinality
$\#\mathrm {diff}(A, B) $
, since
$\mathrm {diff}(A, A') \subsetneq \mathrm {diff}(A, B)$
and
$A'\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 Lemma 4.18, we derive that either
$s_k$
precedes
$s_{k+1}$
with respect to
${\boldsymbol {\tau }}$
, or
$s_{k+1}\in \{s_{k,1},\dots ,s_{k,j_k-1}\}$
.
-
(a) Suppose that
$s_k$
precedes
$s_{k+1}$
with respect to
${\boldsymbol {\tau }}$
. Since
$B\in \mathcal {E}_{j_1, \dots , j_{k-1}, j_k'}$
with
$j_k'<j_k$
, we can write
$\mathrm {sgn}(B)=(s_1, \dots , s_{k-1}, s_{k, j_k'}, p_{k+1}, \dots , p_{n-1})$
with suitable
$p_i$
’s. Since
$j_k'<j_k$
,
$s_{k, j_k'}$
precedes
$s_k$
with respect to
${\boldsymbol {\tau }}$
. As a result of our assumption here,
$s_{k, j_k'}$
also precedes
$s_{k+1}$
with respect to
${\boldsymbol {\tau }}$
. Without loss of generality, we may assume that
$\mathrm {diff}(A',B)=\{k+1,k+2,\dots ,r\}$
is a “continuous” segment. Applying Lemma 4.15 to
$A'$
and B, we can find some maximal clique
$A"$
in
$\mathcal {E}$
such that
$\mathrm {diff}(A', A")\subseteq \mathrm {diff}(A', B)$
and
$\mathrm {sgn}(A")=(s_1, \dots , s_k, s_{k, j_k'}, r_{k+2}, \dots , r_{n-1})$
for suitable
$r_i$
’s. In particular,
$k+1\notin \mathrm {diff}(A, A")$
. Meanwhile, we observe that Thus, the maximal clique
$$\begin{align*}\mathrm{diff}(A, A")\subseteq \mathrm{diff}(A, A') \cup \mathrm{diff}(A', A") \subseteq \mathrm{diff}(A,B)\cup \mathrm{diff}(A',B) = \mathrm{diff}(A,B). \end{align*}$$
$A"$
belongs to the previously defined set
$\mathcal {D}$
. But since
$s_{k,j_k'}$
precedes
$s_{k+1}$
with respect to
${\boldsymbol {\tau }}$
while
$\mathrm {sgn}(A')=(s_1,\dots ,s_{n-1})$
, this contradicts our choice of
$A'$
.
-
(b) Suppose instead that
$s_{k+1}=s_{k, \ell }$
for some
$\ell <j_k$
. Then,
${\boldsymbol {c}}^{k+1}$
is a legitimate tuple by the existence of
$\mathcal {E}_{j_1, \dots , j_{k-1}, \ell }$
. Meanwhile, notice that
$A'$
is a legitimate maximal clique such that
$\mathrm {diff}(C, A')= \{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
${\boldsymbol {\tau }}$
. Thus,
$C\prec A'$
, fully confirming our claim about C.
Next, we consider the linear quotients across equivalence classes.
Lemma 4.20 Suppose that
$\mathcal {E}$
is an equivalence class such that
$\mathrm {rank}(\mathcal {E})>0$
. Let
$\kappa _1$
,
$\kappa _2$
, and L be as introduced in Definition 4.12. Then, we have
$\kappa _1+1<\kappa _2-1$
.
Proof Suppose for contradiction that
$\kappa _1+1\ge \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\ge 3$
,
$\kappa _1\le n-1$
, and
$\kappa _2\ge 2$
, we encounter the following four cases.
-
(i) Suppose that
$\kappa _1=n-1$
. Then,
${\boldsymbol {a}}^1=(1, 0, \dots , 0, a_n^1)$
with
$0\le a_n^1\le \alpha _n-1$
. Consequently,
${\boldsymbol {a}}^n=(0, \dots , 0, a_n^1+1)$
, which has to be
${\boldsymbol {\eta }}$
. -
(ii) Suppose that
$\kappa _2=2$
. Then,
${\boldsymbol {a}}^1=(a_1^1,\alpha _2,\dots ,\alpha _{n-1},\alpha _n-1)$
with
$a_1^1>1$
. Consequently,
${\boldsymbol {a}}^n=(a_1^1-1,\alpha _2,\dots ,\alpha _n)$
, which has to be
${\boldsymbol {\eta }}$
. -
(iii) Suppose that
$\kappa _1+1=\kappa _2$
and
$2\le \kappa _1\le n-2$
. Then,
${\boldsymbol {a}}^1=(1, 0, \dots , 0, \alpha _{\kappa _1+1}, \dots , \alpha _{n-1}, \alpha _n-1)$
. Consequently,
${\boldsymbol {a}}^n= (0, \dots , 0, \alpha _{\kappa _1+1}, \dots , \alpha _n)$
, which has to be
${\boldsymbol {\eta }}$
. -
(iv) Suppose that
$\kappa _1+1=\kappa _2-1$
and
$1\le \kappa _1\le n-2$
. Then, with
$$\begin{align*}{\boldsymbol{a}}^1=(1, 0, \dots, 0, a_{\kappa_1+1}^1, \alpha_{\kappa_1+2}, \dots, \alpha_{n-1}, \alpha_n-1) \end{align*}$$
$0<a_{\kappa _1+1}^1<\alpha _{\kappa _1+1}$
. Consequently,
${\boldsymbol {a}}^n=(0, \dots , 0, a_{\kappa _1+1}^1, \alpha _{\kappa _1+2}, \dots , \alpha _{n})$
, which has to be
${\boldsymbol {\eta }}$
.
In each case, we always have
$\mathrm {rank}(\mathcal {E})=0$
, which is a contradiction.
Proposition 4.21 Let
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {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=\{{\boldsymbol {a}}^{j+1}\}\subseteq A\setminus B$
.
Proof We will prove this by using the notation and arguments of Definition 4.12. As
$\mathrm {rank}(\mathcal {E})>0$
by the existence of B, we showed in Lemma 4.20 that
$\kappa _1+1<\kappa _2-1$
, and the first maximal clique L in
$\mathcal {E}$
satisfies
$$\begin{align*}\mathrm{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}), \end{align*}$$
for appropriate
$\tau _i$
’s.
Suppose that
$\mathrm {sgn}(A)=(s_1, \dots , s_{n-1})$
and let W be the set
$$\begin{align*}[n-1] \setminus (\{n-1, n-2, \dots, \kappa_2-1\}\sqcup \{1, 2, \dots, \kappa_1\})= \{\kappa_1+1, \dots, \kappa_2-2\}. \end{align*}$$
Since
$\kappa _1+1<\kappa _2-1$
, W is not empty. Meanwhile, since
$rA$
does not exist,
$s_1=1$
or
$n-1$
by Lemma 4.4, and
$s_1\notin W$
. In the following, let
$j\ge 1$
be the smallest such that
$s_{j+1}\in W$
. We can construct a maximal clique D in
$\mathcal {E}$
such that
$\mathrm {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
$\mathrm {sgn}(L)$
while
$s_j$
precedes
$s_{j+1}$
in
$\mathrm {sgn}(A)$
, these two indices are not comparable in the poset of obstructions, i.e., they can exchange positions in any legitimate signature. As
$\mathrm {sgn}(A)$
is a legitimate signature, so is
$\mathrm {sgn}(D)$
, namely, D is a maximal clique in
$\mathcal {E}$
.
Next, since
$s_{j+1}$
precedes
$s_j$
in
$\mathrm {sgn}(L)$
, we deduce that
$D\prec A$
. From Lemma 4.5, we also have
$A\setminus D=\{{\boldsymbol {a}}^{j+1}\}$
. It remains to show that this
${\boldsymbol {a}}^{j+1}\notin B$
. Suppose for contradiction that this is not true. Then, we can write
$B=({\boldsymbol {b}}^1, \dots , {\boldsymbol {b}}^n)$
and
${\boldsymbol {b}}^{j'}={\boldsymbol {a}}^{j+1}$
for some
$j'$
. Since
$B\prec A$
, we must have
$j'\le j+1$
, by rank reason. At the same time, given Lemma 4.9, we can find
$i_1\le \kappa _1$
and
$i_2\le 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
${\boldsymbol {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
${\boldsymbol {b}}^{j'}= {\boldsymbol {a}}^{j+1}$
, we obtain that
$1, 2, \dots , i_1, n-i_2, \dots , n-1\notin \Delta ({\boldsymbol {b}}^{j'}, {\boldsymbol {b}}^n)$
. Thus, if
$\mathrm {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'-1}\}$
, forcing
$j\le j'-1$
. Therefore,
$j'=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 ({\boldsymbol {b}}^1, {\boldsymbol {b}}^{j+1})= \Delta ({\boldsymbol {a}}^1, {\boldsymbol {a}}^{j+1})$
. As
${\boldsymbol {b}}^{j+1}={\boldsymbol {a}}^{j+1}$
, it follows that
${\boldsymbol {b}}^1={\boldsymbol {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.22 The total order
$\prec $
of Setting 4.13 induces a linear quotient order of the monomial generating set
$G(\mathrm {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=({\boldsymbol {a}}^1, \dots , {\boldsymbol {a}}^n)$
and
$A\in \mathcal {E}$
. We have two cases.
-
(a) Assume that
$B\in \mathcal {E}$
. We apply Proposition 4.19 for the existence of such D. -
(b) Assume that
$B\notin \mathcal {E}$
.-
(i) If
$rA$
exists, then
$A\setminus rA=\{{\boldsymbol {a}}^1\}$
. Note that
${\boldsymbol {a}}^1\notin B$
for rank reasons. So in this case, we take
$D=rA$
. -
(ii) Assume that
$rA$
does not exist. We apply Proposition 4.21 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,{\boldsymbol {\alpha }}}$
is the Veronese type algebra of Setting 2.3 and
${\boldsymbol {\eta }}$
is the tuple given in Definition 3.3. Meanwhile, J is the presentation ideal so that
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}={\mathbb K}[{\boldsymbol {T}}]/J$
.
5.1 Regularity of the algebra
First of all, we determine the Castelnuovo–Mumford regularity of the algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
.
For each maximal clique A in the graph
$\mathcal {G}=\mathcal {G}(d,{\boldsymbol {\alpha }})$
, we will denote the minimal number of generators of the linear quotient ideal 
by
$\omega _{{\boldsymbol {\alpha }}}(A)$
, or
$\omega (A)$
for short. By the proof of Theorem 4.22, we have
$$ \begin{align} \omega(A)= \# \{B\prec A: \mathrm{diff}(A,B)\text{ is a singleton set}\}. \end{align} $$
Furthermore, by Lemma 3.2, we have the following formula:
$$ \begin{align} \mathrm{pd}((\mathrm{in}(J))^\vee)=\max\limits_{A} \omega(A). \end{align} $$
Since
$\mathrm {pd}((\mathrm {in}(J))^\vee ) =\mathrm {reg} (\mathcal {A}_{d,{\boldsymbol {\alpha }}})$
by Observation 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)\le n-1$
for each maximal clique
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n)$
.
Proof Since 
is linear, it follows from Equation (1) that
$$\begin{align*}\omega(A)=\#\{{\boldsymbol{a}}^i:\text{there exists some } B\prec A \text{with} \{{\boldsymbol{a}}^i\}=A\setminus B\}. \end{align*}$$
Therefore, it suffices to show that there is no B with
$B\prec A$
such that
$\{{\boldsymbol {a}}^n\}=A\setminus B$
. Suppose for contradiction that this is not true. By Corollary 3.11, we have either
$B=({\boldsymbol {b}},{\boldsymbol {a}}^1,{\boldsymbol {a}}^2,\dots ,{\boldsymbol {a}}^{n-1})$
or
$B=({\boldsymbol {a}}^1,{\boldsymbol {a}}^2,\dots ,{\boldsymbol {a}}^{n-1},{\boldsymbol {b}})$
for some suitable tuple
${\boldsymbol {b}}$
. In the first case,
$\mathrm {rank}(B)=\mathrm {rank}(A)+1$
, which contradicts the assumption that
$B\prec A$
. In the second case, we have
$B=A$
by Corollary 3.11, 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
$\mathrm {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
${\boldsymbol {a}}^1=(a_1^1,\ldots ,a_n^1)$
. Then, the following are equivalent:
-
(a) the cardinality
$\#\mathcal {E}=(n-1)!$
; -
(b) the poset of obstructions in Definition 4.8 is trivial for
$\mathcal {E}$
; -
(c) one has
$1 \le a_1^1\le \alpha _1$
,
$1\le a_j^1\le \alpha _j-1$
for all
$2\le j\le n-1$
, and
$0\le a_n^1\le \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 Definition 4.8 is trivial for
$\mathcal {E}$
, namely,
$1\le a_j^1\le \alpha _j-1$
for all
$2\le j\le n-1$
. That
$1 \le a_1^1\le \alpha _1$
and
$0\le a_n^1\le \alpha _n-1$
is automatic for all such
${\boldsymbol {a}}^1$
in view of Corollary 3.11.
In the following, we characterize when
$\mathrm {pd} ((\mathrm {in}(J))^\vee )$
is exactly
$n-1$
.
Proposition 5.3 The following conditions are equivalent:
-
(a) the projective dimension
$\mathrm {pd} ((\mathrm {in}(J))^\vee )=n-1$
; -
(b) there exists a maximal clique A such that
$\omega (A)=n-1$
; -
(c) one has
$n\le d \le \sum _{i=1}^n(\alpha _i-1)$
; -
(d) there exists a maximal clique
$A=({\boldsymbol {a}}^1,\ldots ,{\boldsymbol {a}}^n)$
with
${\boldsymbol {a}}^1=(a_1^1,\ldots ,a_n^1)$
such that
$$\begin{align*}2\le a_1^1 \le \alpha_1, \quad 1\le a_j^1\le \alpha_j-1\text{ for all } 2\le j\le n-1, \quad \text{and}\quad 0\le a_n^1\le \alpha_n-2. \end{align*}$$
Proof The equivalence of (a) and (b) is clear from the explanation before Lemma 5.2.
Next, we show the equivalence of (c) and (d). Since
$|{\boldsymbol {a}}^1|=d$
, we can easily deduce (c) from (d). Conversely, if (c) is satisfied, we can easily find suitable
${\boldsymbol {a}}^1 =(a_1^1,\ldots ,a_n^1) \in {\mathbb N}^n$
as in (d). Let
$A=({\boldsymbol {a}}^1, \dots , {\boldsymbol {a}}^n)$
be the tuple of elements in
${\mathbb Z}^n$
such that
$\mathrm {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).
-
(b) ⇐ (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 Lemma 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
$\mathrm {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
$\mathrm {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=\{{\boldsymbol {a}}^{k}\}$
by Lemma 4.5. Meanwhile, since
$a_n^1\le \alpha _n-2$
, it follows from Corollary 3.11 that
${\boldsymbol {a}}^n$
is not the tuple
${\boldsymbol {\eta }}$
of Definition 3.3. In other words,
$\mathrm {rank}(\mathcal {E})>0$
. Thus,
$rA$
exists and
$A\setminus rA=\{{\boldsymbol {a}}^1\}$
by Lemma 4.4. In conclusion, is linear and has the maximal size by the proof of Lemma 5.1. In particular, (b) holds. -
(b) ⇒ (d): Suppose that the condition in (b) is satisfied. Then, there exists a maximal clique
$A=({\boldsymbol {a}}^1, \dots , {\boldsymbol {a}}^{n})$
in some equivalence class
$(\mathcal {E},L)$
such that the quotient ideal is linear with
$n-1$
minimal monomial generators. In view of Lemma 5.1 and its proof, this implies that . Since
$T_{{\boldsymbol {a}}^1}\in Q$
,
$rA$
must exist and
$\mathrm {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=\{{\boldsymbol {a}}^{k}\}$
. Since
$B^k$
obviously starts with
${\boldsymbol {a}}^1$
, this maximal clique belongs to
$\mathcal {E}$
. Now, suppose that
$\mathrm {sgn}(A)=(s_1, \dots , s_{n-1})$
. It follows from Lemma 4.5 that
$\mathrm {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 Setting 4.13(c). 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
$\mathrm {sgn}(L)=(s_{n-1},\dots ,s_1)$
is the reverse of
$\mathrm {sgn}(A)$
. Consequently, the poset of obstructions considered in Definition 4.8 is trivial, and we have
$0<a_i^1<\alpha _i$
for
$i\in \{2,\dots ,n-1\}$
by Lemma 5.2.Furthermore, since A is legitimate,
$1\le a_1^1\le \alpha _1$
and
$0\le a_n^1\le \alpha _n-1$
by Corollary 3.11. If
$a_1^1=1$
, then
$\mathrm {sgn}(L)$
takes the form
$(\tau _1, \dots , \tau _{n-2}, 1)$
by the requirement in Definition 4.12. Whence,
$s_1=1$
. But this implies that
$rA$
does not exist by Lemma 4.4, a contradiction. Similarly, we can prove that
$a_n^1\le \alpha _n-2$
. Thus, (d) holds.
is linear and has the maximal size by the proof of Lemma 
is linear with 
. Since 
In what follows, we consider the case, where the equivalent requirements of Proposition 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
${\boldsymbol {x}}^{{\boldsymbol {a}}^1}, \dots , {\boldsymbol {x}}^{{\boldsymbol {a}}^t}$
in
${\mathbb K}[x_1, \dots , x_n]$
. In addition, suppose that
${\boldsymbol {b}}$
is a tuple in
${\mathbb N}^n$
such that
${\boldsymbol {b}}-{\boldsymbol {a}}^i\in {\mathbb N}^n$
for each i. Whence, we will call 
the generalized Newton dual of I with respect to
${\boldsymbol {b}}$
. It follows from [Reference Ansaldi, Lin and Shen1, Theorem 3.1] that the algebra
${\mathbb K}[I]$
is isomorphic to
${\mathbb K}[I^{[{\boldsymbol {b}}]}]$
. Of course, we are only interested in the case, where
$I=I_{d,{\boldsymbol {\alpha }}}$
, and
${\boldsymbol {b}}={\boldsymbol {\alpha }}$
. In this case, we have
$$ \begin{align} \mathcal{A}_{d,{\boldsymbol{\alpha}}}= {\mathbb K}[I] \cong {\mathbb K}[I^{[{\boldsymbol{\alpha}}]}]= \mathcal{A}_{|{\boldsymbol{\alpha}}|-d,{\boldsymbol{\alpha}}}. \end{align} $$
Proposition 5.5 Suppose that either
$n>d$
or
$\sum _{i=1}^n(\alpha _i-1)<d$
. Let
$d'= \min (d,|{\boldsymbol {\alpha }}|-d)$
. Then,
$\mathrm {pd} ((\mathrm {in}(J))^\vee )=\left \lfloor n-\frac {n}{d'} \right \rfloor $
.
Proof It follows from the isomorphism in Equation (4) that we can assume that
$d'=d$
and
$n>d$
. From this, we also deduce that
$2d\le |{\boldsymbol {\alpha }}|$
.
As the first step, we show that
$\mathrm {pd} ((\mathrm {in}(J))^\vee )\ge \left \lfloor n-\frac {n}{d} \right \rfloor $
. In the extremal case, when
$d=1$
, since
$|{\boldsymbol {\eta }}|=d$
, one obviously has
${\boldsymbol {\eta }}=(0,\dots ,0,1)$
and
$I_{d,{\boldsymbol {\alpha }}}$
is the graded maximal ideal of S. Whence, the claimed formula is guaranteed by [Reference Nitsche25, Theorem 4.2]. Therefore, in the following, we will assume that
$d\ge 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\le 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
in
$\mathcal {G}(d,{\boldsymbol {\alpha }})$
. Thus, the maximal cliques in
$\mathcal {E}$
all end with
${\boldsymbol {a}}^n$
such that
$\Delta ({\boldsymbol {a}}^1,{\boldsymbol {a}}^n)=[1,n)$
by Corollary 3.11. It is clear that
${\boldsymbol {a}}^n= (0, a^1_2, \ldots , a^1_{n-1},1)$
. If
$\alpha _n\ge 2$
, since
${\boldsymbol {\eta }}=(*,\dots ,*,\alpha _n)$
, we have
${\boldsymbol {a}}^n\ne {\boldsymbol {\eta }}$
. Therefore,
$\mathrm {rank}(\mathcal {E})>0$
. If instead
$\alpha _n=1$
, then
${\boldsymbol {\alpha }}=(1,\dots ,1)$
. Whence,
$2d\le |{\boldsymbol {\alpha }}|=n$
. We still have
$\mathrm {rank}(\mathcal {E})>0$
. Otherwise, we will have
$$\begin{align*}{\boldsymbol{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)={\boldsymbol{\eta}}. \end{align*}$$
Since
$p\ge 1$
, by the description of
${\boldsymbol {\eta }}$
in Definition 3.3, the only possibility is
$q=0$
and
$p=1$
. Whence,
$n=d+1$
. But as
$n\ge 3$
and
$2d\le n$
, this is impossible.
To simplify the following proof, we write accordingly
$$\begin{align*}(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}). \end{align*}$$
Then, we have
$$ \begin{align} s_i^{\ell} \, \triangleleft\, s_{j}^{\ell} \qquad \text{for all } i<j \text{ and all } \ell \end{align} $$
in the poset of obstructions defined in Definition 4.8. Furthermore, we have
$$ \begin{align} &s_1^{i+1} \, \triangleleft\, s_{p}^i \qquad \text{if } 1 \le i \le d-q-1 \text{ and } \alpha_{s_1^{i+1}}=1, \end{align} $$
and
$$ \begin{align} & s_0^{j+1} \, \triangleleft\, s_{p}^{j} \qquad \text{if } d-q\le j \le d-1 \text{ and } \alpha_{s_0^{j+1}}=1, \end{align} $$
in the poset of obstructions. Indeed, they are the generating relations of that poset. Since the Castelnuovo–Mumford regularity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is independent of the rules we impose in Section 4, we can further require that
when
$q \ge 1$
. If instead
$q=0$
, we then require that
In any case, the prescribed
$\mathrm {sgn}(L)$
is a legitimate signature by Lemma 4.10, since it satisfies the requirements of Equations (5)–(7), and Definition 4.12. Now, let A be the maximal clique starting from
${\boldsymbol {a}}^1$
such that
Then, A is legitimate by Lemma 4.10, since it satisfies the requirements of Equations (5)–(7). Note that all end positions of the underbraced segments in
$\mathrm {sgn}(A)$
are boxed. Suppose that we also write
$\mathrm {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=({\boldsymbol {b}}_1^k,\dots ,{\boldsymbol {b}}_n^k)$
of elements in
${\mathbb Z}^n$
such that
${\boldsymbol {b}}_1^k={\boldsymbol {a}}^1$
and
$$\begin{align*}\mathrm{sgn}(B^k)=(t_1,\dots,t_{k-1},t_{k+1},t_{k},t_{k+2},\dots,t_{n-1}). \end{align*}$$
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
$\mathrm {sgn}(L)$
, and
$\mathrm {diff}(A,B^k)$
is a singleton set by Lemma 4.5. Consequently, we have a natural lower bound for the minimal number of generators:
by the first part of the proof of Theorem 4.22. Notice that
$q=0$
if and only if
$\mathrm {sgn}(A)$
starts with
$1$
, if and only if
$rA$
does not exist by Lemma 4.4. Thus,
by the second part of the proof of Theorem 4.22. Therefore, we get
$\mathrm {pd} ((\mathrm {in}(J))^\vee )=\max \limits _{B} \omega (B)\ge \left \lfloor n-\frac {n}{d} \right \rfloor $
, as planned.
As the second step, we show that
$\mathrm {pd} ((\mathrm {in}(J))^\vee )\le \left \lfloor n-\frac {n}{d} \right \rfloor $
. For this purpose, we introduce the new tuple
${\boldsymbol {\alpha }}^{\prime }=(d,\dots ,d)$
. Notice that the sets of maximal cliques satisfy that
$\mathrm {MC}(\mathcal {G}(d,{\boldsymbol {\alpha }}))\subseteq \mathrm {MC}(\mathcal {G}(d,{\boldsymbol {\alpha }}^{\prime }))$
. For any fixed
$A=({\boldsymbol {a}}^1,\dots ,{\boldsymbol {a}}^n) \in \mathrm {MC}(\mathcal {G}(d,{\boldsymbol {\alpha }}))$
, let
$\mathcal {E}({\boldsymbol {\alpha }})$
(resp.
$\mathcal {E}({\boldsymbol {\alpha }}^{\prime })$
) be the equivalence class in
$\mathcal {G}(d,{\boldsymbol {\alpha }})$
(resp.
$\mathcal {G}(d,{\boldsymbol {\alpha }}^{\prime })$
) to which A belongs. Let
${\boldsymbol {\eta }}$
(resp.
${\boldsymbol {\eta }}^{\prime }$
) be the tuple given in Definition 3.3 for
${\boldsymbol {\alpha }}$
(resp.
${\boldsymbol {\alpha }}^{\prime }$
). It is clear that the post of obstructions of
$\mathcal {E}({\boldsymbol {\alpha }}^{\prime })$
is a subposet of
$\mathcal {E}({\boldsymbol {\alpha }})$
. Let
$\kappa _1$
and
$\kappa _2$
(resp.
$\kappa _1'$
and
$\kappa _2'$
) be the index defined in Definition 4.12 for
${\boldsymbol {\alpha }}$
(resp.
${\boldsymbol {\alpha }}^{\prime }$
), then we have
$\kappa _1=\kappa _1'$
by the definition. As for
$\kappa _2$
and
$\kappa _2'$
, notice first that
$a^1_n\le \alpha ^{\prime }_n-1=d-1$
and
$|{\boldsymbol {a}}^1|=d$
. If
$a^1_n=d-1$
, we must have
${\boldsymbol {a}}^1=(1,0,\ldots ,0,d-1)$
and
${\boldsymbol {a}}^n=(0,\ldots ,0,d)={\boldsymbol {\eta }}={\boldsymbol {\eta }}^{\prime }$
. Whence,
$\mathcal {E}({\boldsymbol {\alpha }})=\mathcal {E}({\boldsymbol {\alpha }}^{\prime })$
has rank
$0$
and contains exactly one maximal clique:
$$\begin{align*}A=((1,0,\ldots,0,d-1),(0,1,0,\ldots,0,d-1),\ldots,(0,\ldots,0,d)). \end{align*}$$
In particular,
$\omega _{\boldsymbol {\alpha }}(A)=0=\omega _{{\boldsymbol {\alpha }}^{\prime }}(A)$
. On the other hand, if
$a^1_n< d-1$
, then
$\kappa _2'$
does not exist. As a result, the special L we designate to
$\mathcal {E}({\boldsymbol {\alpha }})$
in Definition 4.12 also works for the equivalence
$\mathcal {E}({\boldsymbol {\alpha }}^{\prime })$
. Consequently, we have
$$\begin{align*}\{B\in \mathrm{MC}(\mathcal{G}(d,{\boldsymbol{\alpha}})):B\prec_{{\boldsymbol{\alpha}}} A\}=\{B\in \mathrm{MC}(\mathcal{G}(d,{\boldsymbol{\alpha}}^{\prime})):B\prec_{{\boldsymbol{\alpha}}^{\prime}}A\} \cap \mathrm{MC}(\mathcal{G}(d,{\boldsymbol{\alpha}})), \end{align*}$$
and
$\omega _{{\boldsymbol {\alpha }}}(A)\le \omega _{{\boldsymbol {\alpha }}^{\prime }}(A)$
by Equation (2). Then, it is easy to deduce that
$$ \begin{align*} \mathrm{pd} ((\mathrm{in}(J({\boldsymbol{\alpha}})))^\vee) &= \max_{A\in \mathrm{MC}(\mathcal{G}(d,{\boldsymbol{\alpha}}))} \omega_{{\boldsymbol{\alpha}}}(A) \le \max_{A\in \mathrm{MC}(\mathcal{G}(d,{\boldsymbol{\alpha}}))} \omega_{{\boldsymbol{\alpha}}^{\prime}}(A) \\ &\le \max_{A\in \mathrm{MC}(\mathcal{G}(d,{\boldsymbol{\alpha}}^{\prime}))} \omega_{{\boldsymbol{\alpha}}^{\prime}}(A) = \mathrm{pd} ((\mathrm{in}(J({\boldsymbol{\alpha}}^{\prime})))^\vee). \end{align*} $$
Since
$\mathrm {pd} ((\mathrm {in}(J({\boldsymbol {\alpha }}^{\prime })))^\vee )= \mathrm {reg}(\mathcal {A}_{d,{\boldsymbol {\alpha }}^{\prime }})=\left \lfloor n-\frac {n}{d} \right \rfloor $
by [Reference Nitsche25, 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,{\boldsymbol {\alpha }}}$
be the Veronese type algebra in Setting 2.3. Set
$d'=\min (d,|{\boldsymbol {\alpha }}|-d)$
. Then,
$\mathrm {reg} (\mathcal {A}_{d,{\boldsymbol {\alpha }}})=\left \lfloor n-\frac {n}{d'} \right \rfloor $
.
Proof Let J be the presentation ideal of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
. From Remark 2.5, [Reference Conca and Varbaro6, Corollary 2.7] and [Reference Herzog and Hibi18, Proposition 8.1.10], we derive that
$\mathrm {reg}(\mathcal {A}_{d,{\boldsymbol {\alpha }}}) =\mathrm {reg}({\mathbb K}[{\boldsymbol {T}}]/J) =\mathrm {reg}({\mathbb K}[{\boldsymbol {T}}]/\mathrm {in}(J)) =\mathrm {pd} ((\mathrm {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 [Reference Goto and Watanabe16, Definition 3.1.4]. Since the Veronese type algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is Cohen–Macaulay by Remark 2.5, we have
$$ \begin{align} \mathtt{a}(\mathcal{A}_{d,{\boldsymbol{\alpha}}})=\mathrm{reg}(\mathcal{A}_{d,{\boldsymbol{\alpha}}})-\mathrm{dim}(\mathcal{A}_{d,{\boldsymbol{\alpha}}}) \end{align} $$
in view of the equivalent definition of Castelnuovo–Mumford regularity in [Reference Ooishi26, Definitions 1 and 3]. Notice that the dimension and the Castelnuovo–Mumford regularity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
are known by Remark 2.4 and Theorem 5.6, respectively. Therefore, we obtain the
$\mathtt {a}$
-invariant of this algebra for free. Moreover, the reduction number of the ideal
$I_{d,{\boldsymbol {\alpha }}}$
, and the Castelnuovo–Mumford regularity of the algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
are equal by the following lemma. For the definition and further discussion of the reduction numbers of ideals (see [Reference Huneke and Swanson21, Section 8.2].
Lemma 5.7 [Reference Corso, Nagel, Petrović and Yuen7, Proposition 6.6] or [Reference Garrousian, Simis and Tohăneanu15, 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) = \mathrm {reg}({\mathbb K}[I])$
.
Corollary 5.8 Let
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}={\mathbb K}[I_{d,{\boldsymbol {\alpha }}}]$
be the Veronese type algebra in Setting 2.3. Assume that
${\mathbb K}$
is an infinite field and set
$d'=\min (d,|{\boldsymbol {\alpha }}|-d)$
. Then,
$ \mathtt {r}(I)= \left \lfloor n-\frac {n}{d'} \right \rfloor $
and
$\mathtt {a}(\mathcal {A}_{d,{\boldsymbol {\alpha }}})= -\left \lceil \frac {n}{d'} \right \rceil $
.
Proof The algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is Cohen–Macaulay by Remark 2.5. Thus, the statements follow from Remark 2.4, Theorem 5.6, Lemma 5.7, and Equation (8).
Remark 5.9 The
$\mathtt {a}$
-invariant of the Rees algebra
$R[I_{d,{\boldsymbol {\alpha }}}t]$
of a Veronese type ideal
$I_{d,{\boldsymbol {\alpha }}}$
is known in [Reference Villarreal29, Corollary 12.6.6] when
$2\leq d\leq n$
. Its proof builds on the normality of the Rees algebra. Since the
$\mathtt {a}$
-invariant of the squarefree Veronese case is known, and equals the
$\mathtt {a}$
-invariant of the Veronese case, one can use the “squeeze theorem” method to obtain the
$\mathtt {a}$
-invariant the Rees algebra
$R[I_{d,{\boldsymbol {\alpha }}}t]$
of a general Veronese type ideal
$I_{d,{\boldsymbol {\alpha }}}$
.
However, this approach does not apply when we deal with the regularity (or equivalently, the
$\mathtt {a}$
-invariant) of the Veronese type algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
, which is the special fiber ring of the Veronese type ideal
$I_{d,{\boldsymbol {\alpha }}}$
. Although the algebra
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is still normal, the regularity of the d-th squarefree Veronese subring and the regularity of the d-th Veronese subring are different in general. For example, we can take
$n=10$
,
$d=8$
, and
${\boldsymbol {\alpha }}=(1,\ldots ,1,2,2)$
with
$|{\boldsymbol {\alpha }}|=12$
. According to our formula, the regularity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is
$7$
, the regularity of the d-th squarefree Veronese subring is 5, and the regularity of the d-th Veronese subring is
$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,{\boldsymbol {\alpha }}}$
. To begin with, we count the number of generators of the ideal
$I_{d,{\boldsymbol {\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.10 The dimension of the polynomial ring 
is given by
$$\begin{align*}\mathrm{dim} (\mathbb{K}[{\boldsymbol{T}}])=\sum_{i\geq 0} (-1)^i\sum_{\substack{P\subseteq [n],\\ \#P=i}}\binom{d-\sum_{p\in P}(\alpha_{p}+1)+n-1}{n-1}. \end{align*}$$
Moreover, there are
different equivalent classes of maximal cliques in the graph
$\mathcal {G}(d,{\boldsymbol {\alpha }})$
, and there are
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
$\mathrm {dim}({\mathbb K}[{\boldsymbol {T}}])=\# V_{n,d}^{{\boldsymbol {\alpha }}}$
is equal to the number of ways to write
$a_1+\cdots +a_n=d$
such that
$0\le a_i \le \alpha _i$
. Furthermore, by Corollary 3.11 and Lemma 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\le a_i \le \alpha _i$
for
$i=2,\ldots ,n-1$
,
$1 \le a_1 \le \alpha _1$
, and
$0\le a_n \le \alpha _n-1$
. It is not hard to see that
$G = \# V_{n,d-1}^{{\boldsymbol {\alpha }}^{\prime }}$
, where
${\boldsymbol {\alpha }}^{\prime }=(\alpha _1-~1,\alpha _2,\alpha _3,\dots ,\alpha _{n-1},\alpha _n-1)$
. Similarly, by Lemma 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 \le a_i \le \alpha _i-1$
for
$i=2,\ldots ,n-1$
,
$1\le a_1 \le \alpha _1$
, and
$0 \le a_n \le \alpha _n-1$
. It is not difficult to see that
$H = \# V_{n,d-(n-1)}^{{\boldsymbol {\alpha }}^{\prime \prime }}$
, where
${\boldsymbol {\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 Lemma 5.2. Say, we have
$p \,\triangleleft \, q$
in this poset. Then, for any
$A\in \mathcal {E}$
, we have p preceding q in
$\mathrm {sgn}(A)$
. Thus,
$$\begin{align*}\# \mathcal{E} = \# \{\mathrm{sgn}(A):A\in \mathcal{E}\} \le (n-1)!/2, \end{align*}$$
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 [Reference Terai28].
Lemma 5.11 [Reference Terai28, 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=\mathrm {indeg}(\mathfrak {a}^\vee )$
is the initial degree of the Alexander dual ideal
$\mathfrak {a}^{\vee }$
.
Corollary 5.12 The multiplicity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
is equal to
$\#\mathrm {MC}(\mathcal {G}(d,{\boldsymbol {\alpha }}))$
.
Proof Note that
$\mathtt {e}(\mathcal {A}_{d,{\boldsymbol {\alpha }}})$
can be calculated from the Hilbert series of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}\cong {\mathbb K}[{\boldsymbol {T}}]/J$
. Meanwhile, the Hilbert series of
${\mathbb K}[{\boldsymbol {T}}]/J$
and
${\mathbb K}[{\boldsymbol {T}}]/\mathrm {in}(J)$
coincide. Thus, thanks to Lemma 5.11, in order to find
$\mathtt {e}(\mathcal {A}_{d,{\boldsymbol {\alpha }}})$
, we only need to compute the minimal number of generators of the equigenerated squarefree monomial ideal
$(\mathrm {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.13 [Reference Terai28, Theorem 4.2]
Let
$R=A/\mathfrak {a}$
be a homogeneous
$\mathbb{K}$
-algebra of codimension
$g \geq 2$
. Then,
$$\begin{align*}\mathtt{e}(R)\le \binom{\mathrm{reg}(R)+g}{g}-\binom{\mathrm{reg}(R)-\mathrm{indeg}(\mathfrak{a})+g}{g}. \end{align*}$$
Relatedly, Eisenbud and Goto in [Reference Eisenbud and Goto11] made a conjecture linking Castelnuovo–Mumford regularity and multiplicity. Although a counterexample was recently given by McCullough and Peeva in [Reference McCullough and Peeva24], the statement of the original conjecture still holds in the Cohen–Macaulay case.
Lemma 5.14 [Reference Eisenbud10, 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
$$\begin{align*}\mathrm{reg}(A/\mathfrak{a}) \le \mathtt{e}(A/\mathfrak{a})-\mathrm{codim}(\mathfrak{a}). \end{align*}$$
We are ready to state our final result regarding the multiplicity of
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}$
.
Theorem 5.15 Suppose that
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}={\mathbb K}[I_{d,{\boldsymbol {\alpha }}}]$
is the Veronese type algebra of Setting 2.3 whose presentation ideal J is not zero. Let 
, 
, G and H be the numbers that we computed in Theorem 5.6 and Lemma 5.10. Furthermore, we write 
and 
. Then, we have
$$ \begin{align*} r+t-n \le \mathtt{e}(\mathcal{A}_{d,{\boldsymbol{\alpha}}}) &\le \min\Bigg\{ H\cdot(n-1)!+\frac{(G-H)\cdot(n-1)!}{2},\; d_1^{n-1},\; d_2^{n-1}, \; \\ & \qquad \qquad \qquad \binom{r+t-n}{t-n}-\binom{r-2+t-n}{t-n} \Bigg\}. \end{align*} $$
Proof The codimension of J is
$t-n$
by Remark 2.4. Since we can replace
${\mathbb K}$
by its algebraic closure, the first inequality follows from Lemma 5.14. As for the second inequality, we apply first Lemmas 5.10 and 5.12. 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
$\mathrm {MC}(\mathcal {G}(d,{\boldsymbol {\alpha }}))\subseteq \mathrm {MC}(\mathcal {G}(d_1,(d_1,\dots ,d_1)))$
, we have
$\mathtt {e}(\mathcal {A}_{d,{\boldsymbol {\alpha }}})\le d_1^{n-1}$
by Corollary 5.12. Similarly, since
$\mathcal {A}_{d,{\boldsymbol {\alpha }}}\cong \mathcal {A}_{d_2,{\boldsymbol {\alpha }}}$
, we also have
$\mathtt {e}(\mathcal {A}_{d,{\boldsymbol {\alpha }}})\le d_2^{n-1}$
. As for the remaining piece, we observe that the presentation ideal J and its initial ideal are quadratic by Remark 2.5. Thus, when
$\mathrm {codim}(J)\ge 2$
, we can apply Lemma 5.13. If instead
$\mathrm {codim}(J)=1$
, since
$\mathrm {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
$\mathrm {in}(J)$
is generated by a squarefree monomial of degree
$2$
. In particular,
$\mathtt {e}(\mathcal {A}_{d,{\boldsymbol {\alpha }}}) =\mathtt {e}({\mathbb K}[{\boldsymbol {T}}]/\mathrm {in}(J))=2$
. On the other hand,
$$\begin{align*}\binom{r+t-n}{t-n}-\binom{r-2+t-n}{t-n}= \binom{r+1}{1}-\binom{r-2+1}{1}=2, \end{align*}$$
which means that we have equality in this case.
Example 5.16 Let
${\boldsymbol {\alpha }}=(1,4,4,5,7)$
and
$d=7$
. Using the notation in Theorem 5.15, we have that
$d_2^4=(21-7)^4=14^4=38416>d_1^4=7^4=2401$
. By Lemma 5.10, we have
$t=171$
,
$G=75$
, and
$H=18$
. Therefore,
$H\cdot (5-1)!+(G-H)\cdot (5-1)!/2=1116$
. By Theorem 5.6, we have
$r=\mathrm {reg}(\mathcal {F}(\mathrm {Sss}({\boldsymbol {\eta }})))=5-1=4$
. Thus,
$r+t-n=4+171-5=170$
and
$$ \begin{align*} \binom{r+t-n}{t-n}-\binom{r-2+t-n}{t-n} & = \binom{4+171-5}{171-5}-\binom{4-2+171-5}{171-5}\\ &=33571342. \end{align*} $$
It follows from Theorem 5.15 that we can obtain
$$\begin{align*}170\le \mathtt{e}(\mathcal{A}_{d,{\boldsymbol{\alpha}}})\le 1116. \end{align*}$$
By directly enumerating the maximal cliques, we can check that
$\mathtt {e}(\mathcal {A}_{d,{\boldsymbol {\alpha }}})=960$
by Lemma 5.11.
Acknowledgments
It is our pleasure to thank Rafael Villarreal for helpful suggestions. We sincerely thank the patient reviewer for the very helpful and constructive suggestions that greatly improve the presentation of this manuscript. We are also grateful to the software system Macaulay2 [Reference Grayson and Stillman17], for serving as an excellent source of inspiration.
Open access
