NON-SIMPLE POLYOMINOES OF K ONIG TYPE AND THEIR CANONICAL MODULE RODICA DINU AND FRANCESCO NAVARRA

2025-05-02 0 0 1.5MB 25 页 10玖币

侵权投诉

NON-SIMPLE POLYOMINOES OF K ˝

ONIG TYPE AND THEIR CANONICAL

MODULE

RODICA DINU AND FRANCESCO NAVARRA

Abstract. We study the K˝onig type property for non-simple polyominoes. We prove that, for closed path

polyominoes, the polyomino ideals are of K˝onig type, extending the results of Herzog and Hibi for simple

thin polyominoes. As an application of this result, we give a combinatorial interpretation for the canonical

module of the coordinate ring of a sub-class of closed paths, namely circle closed path polyominoes. In this

case, we compute also the Cohen-Macaulay type and we show that the coordinate ring is level.

1. Introduction

Polyominoes are plane ﬁgures obtained by joining unit squares along their edges. They raise many

combinatorial problems, such as tiling a given region or even the entire plane with polyominoes, which

are of interest to mathematicians and computer scientists. Even though problems like, for example,

the enumeration of pentominoes, have their origins in antiquity, polyominoes were formally deﬁned by

Golomb ﬁrst in 1953 and later, in 1996, in his monograph [15]. The study of polyominoes reveals many

connections to diﬀerent subjects. For instance, in algebraic languages there is a nice relation between

polyominoes and Dyck words and Motzkin words [12]. In statistical physics, polyominoes (and their

higher-dimensional analogs known in the literature as lattice animals) appear as models of branched

polymers and of percolation clusters [36].

A classic topic in commutative algebra is the study of determinantal ideals. These are the ideals generated

by the t-minors of a matrix whose entries are indeterminates; see for instance [1] and [33]. More generally,

ideals of t-minors of 2-sided ladders have been studied in [9], [10], [11], [16]. The concept of polyomino

ideal, alternatively known as the ideal generated by the so-called inner 2-minors of a m×nmatrix, widely

generalize the theory of determinantal ideals. Speciﬁcally, if Pis a polyomino, then the polyomino ideal IP

of Pis deﬁned as the ideal generated by those sets of 2-minors of the matrix that can be combinatorially

associated with the polyomino P. This type of ideal was introduced in 2012 by Qureshi [28]. Since then,

the study of the main algebraic properties of polyomino ideals and their quotient rings K[P], in terms

of the shape of P, has emerged as an exciting area of research. For instance, several mathematicians

have studied the primality of IP, see [2], [5], [6], [23], [24], [25], [26], [32]. Moreover, in [21] and [30],

the authors showed that K[P] is a normal Cohen-Macaulay domain if Pis a simple polyomino, i.e. a

polyomino without holes. In [19] the authors introduced graded ideals of K˝onig type with respect to a

monomial order <. These ideals Iare characterized by the existence of a sequence, whose length is the

same as the height of I, of homogeneous polynomials forming part of a minimal system of generators of

Iand of a monomial order <with respect to whom their initial monomials form a regular sequence. The

authors presented interesting consequences that may occur when working with a graded ideal with this

property. Moreover, in [18], Herzog and Hibi showed that if Pis a simple thin polyomino, where thin

means that the polyomino does not contain the square tetromino, then its polyomino ideal has the K˝onig

type property.

We are interested in understanding the K˝onig type property for non-simple polyominoes, following the

path initiated by Herzog and Hibi. We will focus on a speciﬁc class of non-simple thin polyominoes,

namely closed path polyominoes. In [18, Example 5.6], the authors provided an example of a closed path

whose polyomino ideal is of K˝onig type with respect to a particular monomial order. This motivated us

to study the K˝onig type property for the closed paths. However, the monomial order suggested by the

2010 Mathematics Subject Classiﬁcation. 05B50, 05E40.

Key words and phrases. Polyominoes, binomial ideals, Krull dimension, K˝onig type, canonical module.

arXiv:2210.12665v4 [math.AC] 6 Mar 2025

2 RODICA DINU AND FRANCESCO NAVARRA

authors is diﬀerent from the ones proposed in this paper. Several interesting results on the class of closed

path polyominoes can be found in [2], [4], [6], [7] and [8]. Since the ﬁrst draft of this work was posted on

arxiv in October 2022, two interesting results have been obtained on polyomino ideals of closed paths. In

[8] it is given a complete description of the minimal primes of the polyomino ideal of a closed path and

in [4] it is proved that the coordinate ring of a closed path is always Cohen-Macaulay.

However, not all polyomino ideals are of K˝onig type and there is no known classiﬁcation of the polyominoes

that have this property. In particular, parallelogram polyominoes give a class of simple polyominoes for

which this property does not hold. Indeed, this follows by [29, Proposition 2.3], where the authors showed

that parallelogram polyominoes are simple planar distributive lattices, and by using the classiﬁcation of

distributive lattices of K˝onig type provided in [18, Theorem 4.1]. In addition, we found an example of a

non-simple thin polyomino that cannot be of K˝onig type (see Remark 4.1).

The paper is organized as follows. In Section 2, we present a detailed introduction to polyominoes and

polyomino ideals, and in Lemma 2.1 we prove that, if Pis a closed path polyomino, then its number

of vertices is twice the number of its cells, a fact that will be useful in the next sections. In order to

study closed path polyominoes of K˝onig type, a combinatorial formula to compute the height of IPis

needed. Section 3 is devoted to this scope. In Theorem 3.5, we give a combinatorial formula for the

Krull dimension of K[P] and prove it using the simplicial complexes theory. The fact that Pcontains

some speciﬁc conﬁgurations as shown in [2, Section 6] plays a crucial role in our proof. Consequently, in

Corollary 3.6, we prove that the height of IPis the number of cells of the closed path polyomino. We

conjecture that this formula holds for any non-simple polyomino. Furthermore, the polyominoes discussed

in [13] and [22] aﬃrmatively support this conjecture. Additionally, in [20, Theorem 1.1], an intriguing

suﬃcient condition for this conjecture is provided. Section 4 is devoted to the proof of the K˝onig type

property of any closed path polyomino (see Theorem 4.8). Unfortunately, the monomial order used to

prove Theorem 3.5 does not guarantee the K˝onig type property for all closed paths as shown in Remark

4.2. In Deﬁnition 4.4, we deﬁne a suitable order on the vertices of the closed path polyomino Pfor whom

the desired property holds. There are two cases to be examined: either Pcontains a conﬁguration of

four cells (treated in Proposition 4.5) or Phas an L-conﬁguration in every change of direction (treated

in Proposition 4.7). In addition, we present a concrete example to illustrate our procedure. In Section 5,

we study the canonical module of the coordinate ring for a sub-class of closed path polyominoes, called

circle closed path polyominoes (see Deﬁnition 5.1). Actually, the canonical module of coordinate rings of

polyominoes has never been studied; just recently, in [31], the authors have studied the levelness property

for the special class of simple paths. In our case, we show that the canonical module can be obtained

from two ideals: a binomial ideal J(P), which is given by the K˝onig type property (see Proposition 4.7),

and a monomial ideal K(P), which is intimately related to the combinatorics of the polyomino. The

binomial ideal coming from the K˝onig type property will play an important role: J(P)⊂IPis a complete

intersection ideal, radical and it has the same height as the polyomino ideal associated to a closed path, by

Lemma 5.7. These properties allow us to use a result from linkage theory, Proposition 5.5, which was ﬁrst

observed in [27]. To compute the colon ideal J(P) : IP, we use another result, namely Proposition 5.6,

determining all the minimal prime ideals of J(P). Finally we give our main result from this section

(Theorem 5.4), where we determine explicitly the canonical module of K[P] for any circle closed path

polyomino P. As a consequence, we compute the Cohen-Macaulay type of K[P] in Corollary 5.17, and

we show that K[P] is a level ring.

2. Basics on polyominoes and polyomino ideals

Let (i, j),(k, l)∈Z2. We say that (i, j)≤(k, l) if i≤kand j≤l. Consider a= (i, j) and b= (k, l) in Z2

with a≤b. The set [a, b] = {(m, n)∈Z2:i≤m≤k, j ≤n≤l}is called an interval of Z2. Moreover, if

i<kand j < l, then [a, b] is a proper interval. In this case, we say aand bare the diagonal corners of

[a, b], and c= (i, l) and d= (k, j) are the anti-diagonal corners of [a, b]. If j=l(or i=k), then aand b

are in horizontal (or vertical)position. We denote by ]a, b[ the set {(m, n)∈Z2:i<m<k, j<n<l}.

A proper interval C= [a, b] with b=a+ (1,1) is called a cell of Z2; moreover, the elements a,b,cand

dare called respectively the lower left,upper right,upper left and lower right corners of C. The set of

vertices of Cis V(C) = {a, b, c, d}and the set of edges of Cis E(C) = {{a, c},{c, b},{b, d},{a, d}}. Let

NON-SIMPLE POLYOMINOES OF K ˝

ONIG TYPE AND THEIR CANONICAL MODULE 3

Sbe a non-empty collection of cells in Z2. Then V(S) = SC∈S V(C) and E(S) = SC∈S E(C), while the

rank of Sis the number of cells belonging to S. If Cand Dare two distinct cells of S, then a walk from

Cto Din Sis a sequence C:C=C1, . . . , Cm=Dof cells of Z2such that Ci∩Ci+1 is an edge of Ci

and Ci+1 for i= 1, . . . , m −1. Moreover, if Ci̸=Cjfor all i̸=j, then Cis called a path from Cto D.

Moreover, if we denote by (ai, bi) the lower left corner of Cifor all i= 1, . . . , m, then Chas a change of

direction at Ckfor some 2 ≤k≤m−1 if ak−1̸=ak+1 and bk−1̸=bk+1. In addition, a path can change

direction in one of the following ways:

(1) North, if (ai+1 −ai, bi+1 −bi) = (0,1) for some i= 1, . . . , m −1;

(2) South, if (ai+1 −ai, bi+1 −bi) = (0,−1) for some i= 1, . . . , m −1;

(3) East, if (ai+1 −ai, bi+1 −bi) = (1,0) for some i= 1, . . . , m −1;

(4) West, if (ai+1 −ai, bi+1 −bi)=(−1,0) for some i= 1, . . . , m −1.

We say that Cand Dare connected in Sif there exists a path of cells in Sfrom Cto D. A polyomino P

is a non-empty, ﬁnite collection of cells in Z2where any two cells of Pare connected in P. For instance,

see Figure 1.

Figure 1. A polyomino.

Let Pbe a polyomino. A sub-polyomino of Pis a polyomino whose cells belong to P. We say that Pis

simple if for any two cells Cand Dnot in Pthere exists a path of cells not in Pfrom Cto D. A ﬁnite

collection of cells Hnot in Pis a hole of Pif any two cells of Hare connected in Hand His maximal

with respect to set inclusion. For example, the polyomino in Figure 1 is not simple. Obviously, each hole

of Pis a simple polyomino, and Pis simple if and only if it has no hole. A polyomino is said to be thin

if it does not contain the square tetromino, which is a square obtained as a union of four distinct cells.

The rank of a polyomino, rank(P), is given by the number of its cells. Consider two cells Aand Bof Z2

with a= (i, j) and b= (k, l) as the lower left corners of Aand Bwith a≤b. A cell interval [A, B] is the

set of the cells of Z2with lower left corner (r, s) such that i⩽r⩽kand j⩽s⩽l. If (i, j) and (k, l) are

in horizontal (or vertical) position, we say that the cells Aand Bare in horizontal (or vertical)position.

Let Pbe a polyomino. Consider two cells Aand Bof Pin vertical or horizontal position. The cell interval

[A, B], containing n > 1 cells, is called a block of Pof rank n if all cells of [A, B] belong to P. The cells

Aand Bare called extremal cells of [A, B]. Moreover, a block Bof Pis maximal if there does not exist

any block of Pwhich properly contains B. It is clear that an interval of Z2identiﬁes a cell interval of Z2

and vice versa, hence we can associate to an interval Iof Z2the corresponding cell interval denoted by

PI. A proper interval [a, b] is called an inner interval of Pif all cells of P[a,b]belong to P. We denote by

I(P) the set of all inner intervals of P. An interval [a, b] with a= (i, j), b= (k, j) and i < k is called a

horizontal edge interval of Pif the sets {(ℓ, j),(ℓ+ 1, j)}are edges of cells of Pfor all ℓ=i, . . . , k −1. In

addition, if {(i−1, j),(i, j)}and {(k, j),(k+ 1, j)}do not belong to E(P), then [a, b] is called a maximal

horizontal edge interval of P. We deﬁne similarly a vertical edge interval and a maximal vertical edge

interval.

Following [25], we call a zig-zag walk of Pa sequence W:I1, . . . , Iℓof distinct inner intervals of Pwhere,

for all i= 1, . . . , ℓ, the interval Iihas either diagonal corners vi,ziand anti-diagonal corners ui,vi+1, or

anti-diagonal corners vi,ziand diagonal corners ui,vi+1, such that:

(1) I1∩Iℓ={v1=vℓ+1}and Ii∩Ii+1 ={vi+1}, for all i= 1, . . . , ℓ −1;

(2) viand vi+1 are on the same edge interval of P, for all i= 1, . . . , ℓ;

(3) for all i, j ∈ {1, . . . , ℓ}with i̸=j, there exists no inner interval Jof Psuch that zi,zjbelong to

4 RODICA DINU AND FRANCESCO NAVARRA

According to [2], we recall the deﬁnition of a closed path polyomino, and the conﬁguration of cells char-

acterizing its primality. We say that a polyomino Pis a closed path if there exists a sequence of cells

A1, . . . , An, An+1,n > 5, such that:

(1) A1=An+1;

(2) Ai∩Ai+1 is a common edge, for all i= 1, . . . , n;

(3) Ai̸=Aj, for all i̸=jand i, j ∈ {1, . . . , n};

(4) For all i∈ {1, . . . , n}and for all j /∈ {i−2, i −1, i, i + 1, i + 2}, we have V(Ai)∩V(Aj) = ∅, where

A−1=An−1,A0=An,An+1 =A1and An+2 =A2.

Figure 2. An example of two closed paths.

A path of ﬁve cells C1, C2, C3, C4, C5of Pis called an L-conﬁguration if the two sequences C1, C2, C3

and C3, C4, C5go in two orthogonal directions. A set B={Bi}i=1,...,n of maximal horizontal (or vertical)

blocks of rank at least two, with V(Bi)∩V(Bi+1) = {ai, bi}and ai̸=bifor all i= 1, . . . , n −1, is called a

ladder of nsteps if [ai, bi] is not on the same edge interval of [ai+1, bi+1] for all i= 1, . . . , n −2. We recall

that a closed path has no zig-zag walks if and only if it contains an L-conﬁguration or a ladder of at least

three steps (see [2, Section 6]). For instance, in Figure 2 there is presented on the left side a closed path

whose polyomino ideal is prime (so it does not contain zig-zag walks), and on the right side a closed path

with zig-zag walks.

Lemma 2.1. Let Pbe a closed path polyomino. Then |V(P)|= 2 rank(P).

Proof. From [2, Lemma 3.3], Pcontains a block Bof rank at least three. We may assume that Bis in

horizontal position and we may label the cells of Ptaking An−1, Anand A1in Bas shown in Figure 3 (A).

We want to inductively assign a pair of vertices of Pto every cell of P. Let us start to attach to A1the

lower and the upper right corners of A1. Let i≥1 and consider the set Bi={Ai−1, Ai, Ai+1}. If Biis as

in Figure 3 (B), up to rotations, then we attach to Ai+1 the two vertices of Pmarked in red. Otherwise,

if Bihas the shape as in Figure 3 (C), up to rotations or reﬂections, then we attach to Ai+1 the two blue

vertices of P. This procedure ends after n−1 steps, considering the set Bn−1={An−2, An−1, An}and

attaching to Anthe lower and the upper right corners of An. Therefore, we can attach to every cell of P

two distinct vertices as deﬁned before, and in conclusion, we get that |V(P)|= 2 rank(P).

(a) (b) (c)

Figure 3. Changes of directions in a closed path.

□

NON-SIMPLE POLYOMINOES OF K ˝

ONIG TYPE AND THEIR CANONICAL MODULE 5

Let Pbe a polyomino. We set SP=K[xv:v∈V(P)], where Kis a ﬁeld. If [a, b] is an inner interval

of P, with a,band c,drespectively diagonal and anti-diagonal corners, then the binomial xaxb−xcxd

is called an inner 2-minor of P. We deﬁne IPas the ideal in SPgenerated by all the inner 2-minors

of Pand we call it the polyomino ideal of P. We set also K[P] = SP/IP, which is the coordinate ring of P.

3. Krull dimension of closed path polyominoes

In this section we compute the Krull dimension of the coordinate ring attached to a closed path polyomino.

We recall some basic facts on simplicial complexes. A ﬁnite simplicial complex ∆ on the vertex set

[n] = {1, . . . , n}is a collection of subsets of [n] satisfying the following two conditions:

(1) if F′∈∆ and F⊆F′then F∈∆;

(2) {i} ∈ ∆ for all i= 1, . . . , n.

The elements of ∆ are called faces, and the dimension of a face is one less than its cardinality. An edge

of ∆ is a face of dimension 1, while a vertex of ∆ is a face of dimension 0. The maximal faces of ∆

with respect to the set inclusion are called facets. The dimension of ∆ is given by sup{dim(F) : F∈∆}.

We say that a simplicial complex ∆ is pure if all the facets have the same dimension. If ∆ is pure, then

the dimension of ∆ is given trivially by the dimension of a facet of ∆. Let ∆ be a simplicial complex

on [n] and R=K[x1, . . . , xn] be the polynomial ring in nvariables over a ﬁeld K. To every collection

F={i1, . . . , ir}of rdistinct vertices of ∆, we associate a monomial xFin Rwhere xF=xi1. . . xir.The

monomial ideal generated by all monomials xFsuch that Fis not a face of ∆ is called Stanley-Reisner

ideal and it is denoted by I∆. The face ring of ∆, denoted by K[∆], is deﬁned to be the quotient ring

R/I∆. It follows from [35, Corollary 6.3.5], if ∆ is a simplicial complex on [n] of dimension d, then

dim K[∆] = d+ 1 = max{s:xi1. . . xis/∈I∆, i1<· · · < is}.

Deﬁnition 3.1. A polyomino Ris called Γ-path with middle cell Dand hooking vertex wif it consists

of a maximal horizontal block B1= [C1, B1] of rank greater than three and a maximal vertical block

B2= [B2, C2] of rank greater than three such that there is a cell Dnot belonging to B1∪ B2and

V(B1)∩V(B2) = {w}where wis the upper left corner of D. This is illustrated in Figure 4 (A). With

reference to Figure 4, we deﬁne τ-paths, W-paths and ζ-paths in a similar way.

(a) Γ-path (b) τ-path (c) W-path (d) ζ-path

Figure 4. Some conﬁgurations in a closed path with zig-zag walks.

Moreover, we say that a pair (F,G) of the previous polyominoes is compatible if Fis a Γ-path (τ-path or

W-path or ζ-path) and Gis one of the other paths.

Deﬁnition 3.2. A polyomino Sis called a LU-skew path with hooking vertices a, b if it is made up of

two maximal blocks B1= [C1, D1] and B2= [C2, D2], both of them having rank greater than three, with

V(B1)∩V(B2) = {a, b}where a, b are the left and right upper corners of D1, respectively. For instance,

see Figure 5 (A). With reference to Figure 5, we can deﬁne LD-skew, DU -skew and UD-skew paths in a

similar way.

Let Pbe a closed path and (F,G) be a pair of two sub-polyominoes of Pas in Deﬁnition 3.1. Without

loss of generality, we may assume that the middle cell of Fis A1and the middle cell of Gis Akwith

k∈[n−1]. Then a sub-polyomino Qof Pas in Deﬁnition 3.2 is said to be between Fand Gif Qis

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

NON-SIMPLEPOLYOMINOESOFK˝ONIGTYPEANDTHEIRCANONICALMODULERODICADINUANDFRANCESCONAVARRAAbstract.WestudytheK˝onigtypepropertyfornon-simplepolyominoes.Weprovethat,forclosedpathpolyominoes,thepolyominoidealsareofK˝onigtype,extendingtheresultsofHerzogandHibiforsimplethinpolyominoes.Asanapplicationofthisre...

展开>> 收起<<

NON-SIMPLE POLYOMINOES OF K ONIG TYPE AND THEIR CANONICAL MODULE RODICA DINU AND FRANCESCO NAVARRA.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

NON-SIMPLE POLYOMINOES OF K ONIG TYPE AND THEIR CANONICAL MODULE RODICA DINU AND FRANCESCO NAVARRA

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: