We present a conjecture about the reduced Hilbert series of the coordinate ring of a simple polyomino in terms of particular arrangements of non-attacking rooks that can be placed on the polyomino. By using a computational approach, we prove that the above conjecture holds for all simple polyominoes up to rank $11$. In addition, we prove that the conjecture holds true for the class of parallelogram polyominoes, by looking at those as simple planar distributive lattices. Finally, we give a combinatorial interpretation of the Gorensteinnes of parallelogram polyominoes.

§ INTRODUCTION

Polyominoes are two dimensional objects obtained by joining  squares of the same size edge to edge. They are originally rooted in recreational mathematics and combinatorics and have been widely discussed in connection with tiling and enumeration problem, see <cit.>. Certain special classes of polyominoes are also related to algebraic languages. In <cit.>, the relation of polyominoes with Dyck words and Motzkin words is beautifully elaborated.

In 2012, the first author introduced a  quadratic binomial ideal associated to polyominoes, the polyomino ideal $I_\PP$, see <cit.>. Let $K$ be a field and $X$ be a $m \times n$ matrix of indeterminates. The polyomino ideals are generated by quite general sets of 2-minors of $X$, and they include some other well known classes of binomial ideals such as the ideals generated by 2-minors of ladders and the join-meet ideals of distributive lattices. The motivation of building such a connection between polyominoes and binomial ideal is to facilitate the study of the binomial ideals and to translate their algebraic properties in combinatorial aspects of polyominoes. Let $I_{\Pc}$ be the polyomino ideal associated to a polyomino $\Pc$ and $K[\Pc]$ be the associated coordinate ring $K[\Pc]$ (see <cit.>). An open and challenging task  is to characterize all polyominoes (in terms of their shape) whose associated coordinate ring is a domain. In <cit.>, authors proved that if $K[\Pc]$ is a domain then $\Pc$ must avoid the “zig-zag walks". The converse of this statement is an open question. It is known from <cit.> that the associated coordinate rings of simple polyominoes are domains. Roughly speaking, simple polyominoes are polyominoes without holes.

The contents of this paper are arranged as follows: in Section <ref>, we recall basic notion and definitions related to polyominoes and distributive lattice. In Subsection <ref>, the relationship between polyominoes and distributive lattices is explored. In particular, in Proposition <ref>, we prove that the parallelogram polyominoes are simple planar distributive lattices. The parallelogram polyominoes are widely discussed in combinatorics (see <cit.> for problems related to enumeration and the computation of  the total area),  and they are defined by two lattice paths that use north and east unit steps, and intersect only at their origin and extremity. Let $L$ be a distributive lattice. Given any pair of incomparable elements $\alpha, \beta \in L$,  let $f_{\alpha\beta}$ be the binomial $z_{\alpha \vee \beta}z_{\alpha \wedge \beta}-z_\alpha z_\beta$ in the polynomial ring $K[z_\alpha : \alpha \in L]$. The ideal generated by all such binomial $f_{\alpha\beta}$ is called the join-meet ideal of $L$, and is denoted by $I_L$. Moreover,  $K[L]=K[z_\alpha : \alpha \in L]/I_L$ is known as the Hibi ring of $L$. The Hibi rings are well understood and possess several nice algebraic and homological properties. It is known from <cit.> that Hibi rings are Cohen-Macaulay domains and the generators of $I_L$ form the reduced Gröbner basis with respect to reverse lexicographical order. Moreover, the Hilbert series of Hibi rings is described in <cit.>. The Hibi ring of simple planar distributive lattice coincide with its coordinate ring as a polyomino. In particular, the join-meet ideal and polyomino ideal of a simple planar distributive lattice is same, see Remark <ref>.  This  identification allows us to use the existing knowledge on Hibi rings arising from simple planar distributive lattices and translate it in terms of their structure as coordinate rings of parallelogram polyominoes. Moreover, from <cit.> it is known that the polyomino ideals of $L$-convex polyominoes can be interpreted as polyomino ideals of  certain Ferrer diagrams. The Ferrer diagrams are a special subclass of parallelogram polyominoes. Therefore, the results provided in subsequent sections hold for $L$-convex polyominoes, which in general, do not have a structure of a simple planar distributive lattice.

In Section <ref>, we study the Hilbert series of parallelogram polyominoes. A polyomino can be viewed as a pruned chessboard. With this point of view, in combinatorics the rook polynomial of polyominoes is a well studied topic, for example see  <cit.>. A rook polynomial $\sum_{i=1}^n r_ix^i$ is a polynomial whose coefficients $r_i$ represents the number of distinct ways of arranging $i$ rooks on squares of $\Pc$ in non-attacking positions.  In <cit.> and <cit.>, the authors linked the Castelnuovo-Mumford regularity of $K[\Pc]$ to the maximum number of non-attacking rooks that can be placed on the polyomino, for the classes of $L$-convex polyominoes and simple thin polyominoes. For the latter class, in <cit.>, the authors proved that the polynomial $h(t)$ of the reduced Hilbert series $h(t)/(1-t)^d$ of $K[\Pc]$ coincides with the rook polynomial of $\Pc$. This result in <cit.> motivated us to study the relation between the Hilbert series and the rook polynomial for simple non-thin polyominoes.  Recently, another paper in this direction has been written by Kummini and Veer <cit.>. In Section <ref>, we introduce an equivalence relation on the rook complex of a simple polyomino $\Pc$. We conjecture that the number of equivalence classes of $k$ non-attacking rooks arrangements coincides with the coefficient $h_k$ of the polynomial $h(t)$ in the reduced Hilbert series. We prove that Conjecture <ref> holds true for the class of parallelogram polyominoes. Moreover, by using a computational approach, we prove that Conjecture <ref> holds true for any simple polyomino having at most 11 cells. In <cit.>, we provide an implementation in  <cit.> and Java for such computations.

The Gorensteinness of the coordinate ring of some classes of polyominoes has been studied by many authors, for example see <cit.>, <cit.> and <cit.>.
Even though the Gorenstein ladder determinantal rings and the Gorenstein Hibi rings are completely characterized, in Section <ref> we give a combinatorial characterization of Gorenstein parallelogram polyominoes that is analogous to the characterizations given in <cit.> and <cit.> for $L$-convex and simple thin polyominoes, respectively. Such characterization involves the intersections of the maximal rectangles of the parallelogram polyominoes. It is well-known that every parallelogram polyomino can be uniquely represented as a Motzkin path  and a Motzkin word. In Corollary <ref>, we give a characterization of the Motzkin paths which represent Gorenstein parallelogram polyominoes.

§ DISTRIBUTIVE LATTICES AND POLYOMINOES

§.§ Polyominoes and polyomino ideals

In this subsection, we recall general definitions and notation on polyominoes.

Let $a = (i, j), b = (k, \ell) \in \NN^2$, with $i	\leq k$ and $j\leq\ell$. The set $[a, b]=\{(r,s) \in \NN^2 : i\leq r \leq k \text{ and } j \leq s \leq \ell\}$ is called an interval of $\NN^2$. Moreover, if $i<k$ and $j < \ell$, then $[a,b]$ is called a proper interval, and the elements $a,b,c,d$ are called corners of $[a,b]$, where $c=(i,\ell)$ and $d=(k,j)$. In particular, $a,b$ are the diagonal corners and $c,d$ are the anti-diagonal corners of $[a,b]$. The corner $a$ (resp. $c$) is also called the left lower (resp. upper) corner of $[a,b]$, and $d$ (resp. $b$) is the right lower (resp. upper) corner of $[a,b]$. A proper interval of the form $C = [a, a + (1, 1)]$ is called a cell. The corners of $C$ are called the vertices of $C$. The set of vertices of $C$ is denoted by $V(C)$. The edge set of $C$, denoted by $E(C)$, is

\[
\{\{a,a+(1,0)\}, \{a,a+(0,1)\},\{a+(1,0),a+(1,1)\},\{a+(0,1),a+(1,1)\} \}.
\]

We denote by $\ell (C)$, the left lower corner of a cell $C$.

Let $\PP$ be a finite collection of cells of $\NN^2$, and let $C$ and $D$ be two cells of $\PP$. Then $C$ and $D$ are said to be connected, if there is a sequence of cells $C = C_1,\ldots, C_m = D$ of $\PP$ such that $C_i\cap C_{i+1}$ is an edge of $C_i$
for $i = 1,\ldots, m - 1$. In addition, if $C_i \neq C_j$ for all $i \neq j$, then $C_1,\dots, C_m$ is called a path (connecting $C$ and $D$). A collection of cells $\PP$ is called a polyomino if any two cells of $\PP$ are connected. We denote by $V(\PP)=\cup _{C\in \PP} V(C)$ the vertex set of $\PP$ and by $E(\PP)=\cup _{C\in \PP} E(C)$ the edge set of $\PP$. In particular, a polyomino could be also seen as a connected bipartite graph. Note that, if $a,b\in V(\PP)$, then $a$ and $b$ are connected in $V(\PP)$ by a path of edges. More precisely,  one can find  a sequence of vertices $a=a_1,\ldots, a_{n}=b$ such that $\{a_i, a_{i+1}\} \in E(\PP)$, for all $i=1, \ldots, n-1$.  The number of cells of $\PP$ is called the rank of $\PP$, and we denote it by $\rk \PP$. We also define the lower left corner of $\PP$ as $\ell (\PP)= \min \{ \ell (C) : C \in \PP \}$. Each proper interval  $[(i,j),(k,l)] $ in $\NN^2$ can be identified as a polyomino and it is referred to as rectangular polyomino, or simply as rectangle. If $s=k-i$ and $t=l-j$ we say that the rectangle has size $s \times t$. In particular, given a rectangle of $\PP$ we call diagonal cells the cells $A,B$ such that $\ell(A)=(i,j)$ and $\ell(B)=(k-1,l-1)$ and antidiagonal cells the cells $C,D$ such that $\ell(C)=(i,l-1)$ and $\ell(D)=(k-1,j)$.

A polyomino $\PP$ is called a subpolyomino of $\PP'$, if all cells of $\PP$ are contained in $\PP'$. Given a polyomino $\PP$, the smallest rectangle (with respect to its size) containing $\PP$ as a subpolyomino, is called the bounding box of $\PP$.

A proper interval $[a,b]$ is called an inner interval of $\PP$ if all cells of $[a,b]$ belong to $\PP$.
We say that a polyomino $\PP$ is simple if for any two cells $C$ and $D$ of $\NN^2$ not belonging to $\PP$, there exists a path $C=C_{1},\dots,C_{m}=D$ such that $C_i \notin \PP$ for any $i=1,\dots,m$. Roughly speaking, a polyomino without a “hole” is called a simple polyomino.
An interval $[a,b]$ with $a = (i,j)$ and $b = (k, \ell)$ is called a horizontal edge interval of $\PP$ if $j =\ell$ and the sets $\{(r, j), (r+1, j)\}$ for
$r = i, \dots, k-1$ are edges of cells of $\PP$. If a horizontal edge interval of $\PP$ is not strictly contained in any other horizontal edge interval of $\PP$, then we call it maximal horizontal edge interval. Similarly, one defines vertical edge intervals and maximal vertical edge intervals of $\PP$.

A polyomino $\PP$ is called row convex if for any two of its cells with lower left corners $a=(i,j)$ and $b=(k,j)$, with $k>i$, all cells with lower left corners $(l,j)$ with $i\leq l \leq k$ are cells of $\PP$. Similarly,  $\PP$ is called column convex if for any two of its cells with lower left corners $a=(i,j)$ and $b=(i,k)$, with $k>j$, all cells with lower left corners $(i,l)$ with $j\leq l \leq k$ are cells of $\PP$. If a polyomino $\Pc$ is simultaneously row and column convex then $\Pc$ is called convex. Let $\mathcal{C}:C_1, C_2, \ldots, C_m$ be a path of cells and $(i_k, j_k)$ be the lower left corner of $C_k$ for $1 \leq k \leq m$. Then $\mathcal{C}$ has a change of direction at $C_k$ for some $2 \leq k \leq m-1$ if $i_{k-1}\neq i_{k+1}$ and $j_{k-1} \neq j_{k+1}$.
A convex polyomino $\Pc$ is called $k$-convex if any two cells in $\Pc$ can be connected by a path of cells in $\Pc$ with at most $k$ change of directions. The $1$-convex polyominoes are referred to as $L$-convex polyominoes and 2-convex polyominoes are referred to as $Z$-convex polyominoes in literature. Figure <ref> shows three examples of polyominoes that are non-simple, $L$-convex and $2$-convex respectively.

[thick] (0,1) –  (0,3);
[thick] (1,1) –  (1,5);
[thick] (2,1) –  (2,5);
[thick] (3,0) –  (3,5);
[thick] (4,0) –  (4,2);

[thick] (0,1) –  (4,1);
[thick] (0,2) –  (4,2);
[thick] (0,3) –  (3,3);
[thick] (1,4) –  (3,4);
[thick] (1,5) –  (3,5);
[thick] (3,0) –  (4,0);

[fill=gray, fill opacity=0.2] (0,1) – (0,3)– (1,3) – (1,1);
[fill=gray, fill opacity=0.2] (2,1) – (2,5)– (3,5) – (3,1);
[fill=gray, fill opacity=0.2] (1,3) – (1,5)– (2,5) – (2,3);
[fill=gray, fill opacity=0.2] (3,0) – (3,2)– (4,2) – (4,0);
[fill=gray, fill opacity=0.2] (1,1) – (1,2)– (2,2) – (2,1);

[thick] (-1,1) –  (-1,2);
[thick] (0,1) –  (0,3);
[thick] (1,0) –  (1,5);
[thick] (2,0) –  (2,5);
[thick] (3,0) –  (3,4);
[thick] (4,1) –  (4,2);

[thick] (-1,1) –  (4,1);
[thick] (-1,2) –  (4,2);
[thick] (0,3) –  (3,3);
[thick] (1,4) –  (3,4);
[thick] (1,5) –  (2,5);
[thick] (1,0) –  (3,0);

[fill=gray, fill opacity=0.2] (1,2) – (2,2)– (2,3) – (1,3);
[fill=gray, fill opacity=0.2] (0,1) – (0,3)– (1,3) – (1,1);
[fill=gray, fill opacity=0.2] (2,0) – (2,4)– (3,4) – (3,0);
[fill=gray, fill opacity=0.2] (1,3) – (1,5)– (2,5) – (2,3);
[fill=gray, fill opacity=0.2] (3,1) – (3,2)– (4,2) – (4,1);
[fill=gray, fill opacity=0.2] (1,1) – (1,2)– (2,2) – (2,1);
[fill=gray, fill opacity=0.2] (1,0) – (2,0)– (2,1) – (1,1);
[fill=gray, fill opacity=0.2] (-1,1) – (0,1)– (0,2) – (-1,2);

[thick] (-1,1) –  (-1,2);
[thick] (0,1) –  (0,3);
[thick] (1,0) –  (1,5);
[thick] (2,0) –  (2,5);
[thick] (3,0) –  (3,4);
[thick] (4,3) –  (4,4);

[thick] (-1,1) –  (3,1);
[thick] (-1,2) –  (3,2);
[thick] (0,3) –  (4,3);
[thick] (1,4) –  (4,4);
[thick] (1,5) –  (2,5);
[thick] (1,0) –  (3,0);

[fill=gray, fill opacity=0.2] (1,2) – (2,2)– (2,3) – (1,3);
[fill=gray, fill opacity=0.2] (0,1) – (0,3)– (1,3) – (1,1);
[fill=gray, fill opacity=0.2] (2,0) – (2,4)– (3,4) – (3,0);
[fill=gray, fill opacity=0.2] (1,3) – (1,5)– (2,5) – (2,3);
[fill=gray, fill opacity=0.2] (3,3) – (3,4)– (4,4) – (4,3);
[fill=gray, fill opacity=0.2] (1,1) – (1,2)– (2,2) – (2,1);
[fill=gray, fill opacity=0.2] (1,0) – (2,0)– (2,1) – (1,1);
[fill=gray, fill opacity=0.2] (-1,1) – (0,1)– (0,2) – (-1,2);

From left to right: a non-simple polyomino, an $L$-convex polyomino and a $2$-convex polyomino

Let $\PP$ be a polyomino and define the polynomial ring $R = K[x_v \ | \ v \in V(\PP)]$ over a field $K$. The binomial $x_a x_b - x_c x_d\in R$ is called an inner 2-minor of $\PP$ if $[a,b]$ is an inner interval of $\PP$, where $c,d$ are the anti-diagonal corners of $[a,b]$. The ideal $I_\PP\subset R$ generated by all of the inner $2$-minors of $\PP$ is called the polyomino ideal of $\PP$. The quotient ring $K [\PP] = R/I_\PP$ is called the co-ordinate ring of $\Pc$. It is known from <cit.> and <cit.> that if $\PP$ is a simple polyomino then $K[\PP]$ is a normal Cohen-Macaulay domain. Combining this with <cit.>, one obtains the following

Let $\PP$ be a simple polyomino. Then $K[\PP]$ is a Koszul, normal Cohen-Macaulay domain of Krull dimension $|V(\PP)|-\rk \PP$.

§.§ Distributive lattices and join-meet ideals

Let $P$ be a poset with partial order relation $<$. A chain of $P$ is a totally ordered subset of $P$. The length of a chain $\mathfrak{c}$, denoted by $\mathrm{length}(\mathfrak{c})$,  is $|\mathfrak{c}|-1$. Given $a \in P$, the rank of $a$ in $P$, denoted by $\rank(a)$, is the  supremum of length of chains in $P$ that descends from $a$. The rank of $P$, denoted by $\rank (P)$, is the supremum of length of chains of $P$. An  order ideal of $P$ is a subset $I$ of P with the following property:  if $a \in I$ then $b \in I$ for all $b \in P$ with $b <a$. Two element $a,b \in P$ are called incomparable if $ a \not<b$ and $b \not<a$.

Let $L$ be a distributive lattice with unique minimal element $\min(L)$ and unique maximal element $\max(L)$. An element $a \in L$ is called join-irreducible if $a \neq \min(L)$ and $a \neq b \vee c$ for any $b,c \in L\setminus \{a\}$. Let $P$ be the set consisting of all join-irreducible elements of $L$. Then $P$ is a poset with partial order inherited from $L$.  Let $I(P)$ be the set consisting of all order ideals of $P$, ordered by inclusion. In particular, $\emptyset, P \in I(P)$ and $I(P)$ is a distributive lattice with $\min(I(P)) = \emptyset$ and $\max(I(P))=P$. It is known by Birkhoff's fundamental theorem  of finite distributive lattices <cit.> that $L \iso I(P)$. Moreover, $\rank(L)=|P|$. We refer to <cit.> for the basic definitions and notation in lattice theory.

at (1,0)[anchor=north]$\varnothing$;
(0,1) circle () node [anchor=east]{1};
(2,1) circle () node [anchor=west]{2};
(3,2) circle () node [anchor=west]{2,3};
at (1,2)[anchor=west]$\{1,2\}$;
at (2,3)[anchor=west]{1,2,3};
(0,3) circle () node [anchor=east]{1,2,4};
at (1,4)[anchor=south]{1,2,3,4};

(0,0) circle () node [anchor=north]1;
(0,2) circle () node [anchor=south]4;
(2,0) circle () node [anchor=north]2;
(2,2) circle () node [anchor=south]3;

A poset and its ideals lattice $I(P)$.

Let $L$ be finite distributive lattice and $S=K[x_a : a \in L]$. The join-meet ideal $I_L\subset S$ of $L$ is the ideal generated by binomials $x_ax_b-x_{a\vee b} x_{a\wedge b}$, where $a$ and $b$ are incomparable elements in $L$.  It is known from <cit.> that $K[L]=S/I_L$ is a normal, Cohen-Macaulay domain.

Now we recall some basic properties of planar distributive lattice. Consider the natural partial order on $\NN^2$ defined as follows: for any $(i,j), (k,l) \in \NN^2$, we have $(i,j) \leq (k,l)$ if and only if $i\leq k$ and $j \leq l$. With this natural partial order, $\NN^2$ is an infinite distributive lattice. Let $L$ be a finite sublattice of $\NN^2$. Then $L$ is called a planar distributive lattice if $(0,0) \in L$ and for any $(i,j), (k,l) \in L$ with$(i,j)< (k,l)$ , there exists a chain in $L$ of the form $(i,j)=(i_0,j_0)< (i_1, j_1)< \ldots < (i_s,j_s)=(k,l)$ such that $i_{k+1}+j_{k+1}= i_k+j_k+1$ for all $k$. The condition $i_{k+1}+j_{k+1}= i_k+j_k+1$ yields that either $(i_{k+1},j_{k+1})=(i_k,j_k)+(0,1)$ or  $(i_{k+1},j_{k+1})=(i_k,j_k)+(1,0)$. A planar distributive lattice $L$ is called simple if, for all $0 <r<\rank(L)$, there exist at least two elements in $L$ with rank $r$. Equivalently,  $L$ is simple if there is no $a \in L$ with the property that for every $b\in L$ either $a \leq b$ or $b \leq a$.

§.§ The relationship between polyominoes and distributive lattices

In this section, we talk about the polyominoes arising from simple planar distributive lattices. Note that any simple planar distributive lattice $L$ can be identified as a convex polyomino.

Let $\Pc$ be a convex polyomino with bounding box $[(0,0), (m,n)]$. If $(0,0), (m,n) \in V(\Pc)$, then $V(\Pc)$ determines a simple planar distributive lattice.

First we show that $V(\Pc)$ is a sublattice of $\NN^2$. Let $a,b \in V(\Pc)$ be two incomparable elements. We need to show that $a \vee b$ and $a\wedge b$ belong to $V(\Pc)$. Let $a=(i,j)$ and $b=(k,l)$. Since $a$ and $b$ are incomparable, we may assume that $i<k$ and $j>l$. Then $a \vee b=(k,j)$ and $a\wedge b=(i,l)$.  First we claim that $a\wedge b=(i,l) \in V(\Pc)$. On the contrary, suppose that $a\wedge b=(i,l) \notin V(\Pc)$. By using the convexity of $\Pc$ and applying <cit.>, it follows that $(i,p), (q,l) \notin V(\Pc)$, for any $p \leq l$ and $q \leq i$. Since, $\Pc$ is a polyomino, and hence connected, there must exist a path in $V(\Pc)$ from $(0,0)$ to $(i,j)$. However, any possible path in $V(\Pc)$ from $(0,0)$ to $(i,j)$ must either contain a vertex $(i,p)$ with  $p \leq l$ or a vertex  $ (q,l)$ with $q \leq i$, a contradiction. This yields $a\wedge b=(i,l) \in V(\Pc)$. A similar argument can be applied to conclude that $a \vee b=(k,j) \in V(\Pc)$. Moreover, the assertion that $\Pc$ is simple and planar as a distributive lattice, follows directly from the definition of polyominoes.

If a polyomino $\PP$ admits a structure of a distributive lattice on $V(\PP)$, then instead of $V(\PP)$, we refer to $\PP$ as a distributive lattice.
Let $(a,b) \in \NN\times \NN$. The edge $\{(a,b), (a+1,b)\}$ is called an east step and the edge $\{(a,b), (a,b+1)\}$ is called a north step in  $\NN\times \NN$. A sequence of vertices $\mathcal{S}:(a_0,b_0), (a_1,b_1) \ldots (a_k,b_k)$ in $\NN \times \NN$ is called a north-east path in $\NN \times \NN$, if $\{(a_i,b_i), (a_{i+1},b_{i+1})\}$ is either an east or a north step for each $i$. The vertices $(a_0,b_0)$ and $(a_k,b_k)$ are called the endpoints of $\mathcal{S}$.

Let $\mathcal{S}_1:(a_0,b_0), (a_1,b_1), \ldots , (a_k,b_k)$ and $\mathcal{S}_2:(c_0,d_0), (c_1,d_1), \ldots , (c_k,d_k)$ be two north-east paths in $\NN\times \NN$ such that $(a_0,b_0)=(c_0,d_0)$ and $(a_k,b_k)=(c_k,d_k)$.  If for all $1 \leq i \leq k-1$ we have $b_i > d_i$ whenever $a_i=c_i$, then  $\mathcal{S}_1$ is said to “lie above" $\mathcal{S}_2$. The parallelogram polyomino $\Pc$ determined by $(\mathcal{S}_1,\mathcal{S}_2)$, where $\mathcal{S}_1$ lies above $\mathcal{S}_2$, is the region bounded above by $\mathcal{S}_1$ and bounded below by $\mathcal{S}_2$.  We refer to the path $S_1$ as the upper path of $\Pc$ and the path $\SS_2$ as the lower path of $\Pc$.  We will denote a parallelogram polyomino as $\Pc=(\SS_1, \SS_2)$ when we need to emphasize on its upper and lower paths.  In Figure <ref>, a parallelogram polyomino is shown. The thick line in Figure <ref> represents the upper path of $\Pc$ and the dashed line represents the lower path of $\Pc$. An equivalent way to describe parallelogram polyomino is the following property: a polyomino such that its intersection with every line perpendicular to the main diagonal is a connected segment (see <cit.>).

[dashed] (0,0)–(2,0)–(2,2)–(3,2)–(3,3)–(5,3)–(5,5)–(6,5)–(6,8)–(8,8)–(8,9)–(9,9)–(9,10);

[ultra thick] (0,0)–(0,2)–(1,2)–(1,3)–(2,3)–(2,5)–(3,5)–(3,8)–(4,8)–(4,9)–(6,9)–(6,10)–(9,10);

(1,0)–(1,2);(2,2)–(2,3);(3,3)–(3,5);(4,3)–(4,8);(5,5)–(5,9);(6,8)–(6,9);(7,8)–(7,10); (8,9)–(8,10);

A parallelogram polyomino

A parallelogram polyomino that is also $L$-convex is known as a Ferrer diagram. In <cit.> the authors prove that the coordinate ring of any  $L$-convex polyomino is isomorphic to the coordinate ring of a Ferrer diagram.

One can observe that every parallelogram polyomino $\Pc$ is a simple planar distributive lattice, as shown in the following proposition.

A finite collection of cells $\Pc$ is a parallelogram polyomino if and only if $\Pc$ is a simple planar distributive lattice.

Let $\Pc=(\SS_1, \SS_2)$ be a parallelogram polyomino. By a shift co-ordinate, we may assume that $\SS_1$ and $\SS_2$ meet at $(0,0)$ and $(m,n)$.  The definition of parallelogram polyomino together with Proposition <ref> yields that $\Pc$ is a simple planar distributive lattice.

To show that converse, assume that $\Pc$ is a simple planar distributive lattice with bounding box $[(0,0), (m,n)]$. It follows from the definition of simple planar distributive lattice  that $\PP$ is convex polyomino. Note that $\rank(\Pc)=m+n$. Let $\mm_0: x_0<x_1<\cdots<x_{m_n-1}< x_{m+n}$ be the maximal chain of $\Pc$ with $x_t=(i_t,j_t)$ for all
$0\leq t\leq m+n$ satisfying the following property: $(i_0,j_0)=(0,0)$, $(i_{d+1},j_{d+1})=(m,n)$, and for any $(k,\ell)\in V(\PP)$ with $k=i_t$ for some $t,$ if $l \geq j_t$ then $(k,l)=(i_s,j_s)$ for some $s\geq t$. We call such an $\mm_0$  the uppermost chain of $\Pc$. Similarly, one can define the lower most chain $\mm'_0$ of $\Pc$. Then it can be easily seen that $\Pc$ is a parallelogram polyomino determined by $(\mm_0, \mm'_0)$.

The following remark plays a vital role in subsequent text.

Let $L$ be a simple planar distributive lattice and $a,b \in L$ be two incomparable elements in $L$. Let $c=a\vee b$ and $d=a \wedge b$. Then $[a,b]$ determines an inner interval in $L$ with diagonal corners $c$ and $d$ and antidiagonal corners $a$ and $b$. Therefore, a typical generator $f_{ab}=x_ax_b-x_{a\vee b}x_{a\wedge b}= x_ax_b-x_cx_d$ of the join-meet ideal of $L$ is also an inner 2-minor of $L$. Similarly, any inner 2-minor of $L$ can be interpreted as a relation arising from two incomparable elements and their meet and join. This shows that the join-meet ideal and polyomino ideals of $L$ coincide.

§ HILBERT SERIES AND ROOK COMPLEX OF SIMPLE POLYOMINOES

In this section, we give a conjecture about the Hilbert series of the coordinate ring of simple polyominoes in terms of some rook arrangements on the cells of the parallelogram polyominoes. We first recall the definition of Hilbert function and Hilbert series (see also <cit.>).

Let $R$ be a standard graded ring and $I$ be a homogeneous ideal. The Hilbert function $\H_{R/I} : \mathbb{N} \rightarrow \mathbb{N}$ is defined by

\[
\H_{R/I} (k) := \dim_K (R/I)_k
\]

where $(R/I)_k$ is the $k$-degree component of the gradation of $R/I$, while the
Hilbert-Poincaré series of $R/I$ is

\[
\HS_{R/I} (t) := \sum_{k \in \NN} \H_{R/I}(k) t^k.
\]

By the Hilbert-Serre theorem, the Hilbert-Poincaré series of $R/I$ is a rational function. In particular, by reducing this rational function we get

\[
\HS_{R/I}(t) = \frac{h(t)}{(1-t)^d}.
\]

for some $h(t) \in \mathbb{Z}[t]$, where $d$ is the Krull dimension of $R/I$. The degree of $\HS_{R/I}(t)$ as a rational function, namely $\deg h(t)-d$, is called a-invariant of $R/I$, denoted by $a(R/I)$. It is known that whenever $R/I$ is Cohen-Macaulay we have $a(R/I)=\reg R/I-\depth R/I$, that is $\reg R/I=\deg h(t)$. In the latter $\reg R/I$ denotes the Castelnuovo-Mumford regularity of $R/I$.

The well-known “rook problem” is the problem of enumerating the number of ways of placing $k$ non-attacking rooks on a pruned chessboard. Every simple polyomino $\PP$ can be viewed as a pruned chessboard. Given a simple polyomino $\PP$, recall that $k$ rooks placed on the cells of $\PP$ are said to be non-attacking if they do not lie on the same row or the same column of cells of $\PP$, pairwise.  The maximum number of non-attacking rooks that can be placed on $\PP$, is called the rook number of $\PP$. By abuse of notation, one identifies the rooks that can be placed on $\PP$ with the cells of $\PP$. We observe that for any cell $C \in \PP$, the set $\{C\}$ is a $1$ non-attacking rook. Moreover, for any set of non-attacking rooks $F \subset \PP$, the subset $G\subset F$ is also a set of non-attacking rooks. This yields that the set $\RR$ of sets of non-attacking rooks is a simplicial complex and

\[
\mathcal{R}=\RR_0 \cup \RR_1 \cup \ldots \cup \RR_{r(\PP)},
\]

where for any $k=0,\ldots, r(\PP)$, $\RR_k$ contains the sets of $k$ non-attacking rooks, with $\RR_0=\varnothing$. Set $r_k = |\RR_k|$. The polynomial

\[
r_{\PP}(t)=\sum_{k=0}^{r(\PP)} r_k t^k
\]

is called the rook polynomial of $\PP$. The rook polynomials are widely studied in combinatorics. We refer to <cit.>, for more information on this topic.

Next, we introduce an equivalence relation on the set $\RR_k$ for $2 \leq k \leq r(\PP)$. For this aim, we define the following.

Two non-attacking rooks $r_1$ and $r_2$ of $\PP$ are switching rooks if they are diagonal (resp. antidiagonal) cells of a rectangle of $\PP$.  Let $r_1'$ and $r_2'$ be the antidiagonal (resp. diagonal).
Observe that if $F\in \RR$  and $r_1,r_2 \in F$ are switching rooks, then the set $F'\setminus\{r_1,r_2\}\cup \{r_1',r_2'\}\in \RR$. The replacement of $r_1$ and $r_2$ by $r_1'$ and $r_2'$ is called switch of $r_1$ and $r_2$.

There exists a natural equivalence relation $\sim$ on $\RR_k$ given as:  $F_1,F_2 \in \RR_k$  are equivalent if one can obtain $F_2$ from $F_1$ after some switches. We define the quotient set

\[
\widetilde{\RR}_k=\RR_k/\sim.
\]

We observe that the rook number $r(\PP)$ does not change. That is, we define the polynomial

\[
\widetilde{r}_{\PP}(t)=\sum\limits_{k=0}^{r(\PP)} |\widetilde{\RR}_k|t^k.
\]

With the notation introduced above, we state the following:

Let $\PP$ a simple polyomino and let $\widetilde{r}_{\PP}(t)$ be the polynomial defined in Definition <ref>. Then $h(t)=\widetilde{r}_{\PP}(t)$.

The following example depicts the construction of a rook complex $\mathcal{R}$ of a polyomino and the quotient set $\widetilde{\RR}:=\RR / \sim $.

We describe $\RR$ and $\widetilde{\RR}$ for the simple polyomino $\PP$ in Figure <ref>. The polyomino $\PP$ consists of seven cells labelled as $A,B,C,D,E,F,G$ and  $r(\PP)=3$. The rook complex $\RR=\RR_0 \cup \RR_1 \cup \RR_2 \cup \RR_3$ of $\PP$ is given below.

$\RR_0=$ {$\varnothing$}

$\RR_1=${ $\{A\}$, $\{B\}$, $\{C\}$, $\{D\}$, $\{E\}$, $\{F\}$, $\{G\}$}

$\RR_2=$ $\{A,D\}$, $\{A,E\}$, $\{A,G\}$, $\{B, C\}$, $\{B, E\}$, $\{B,F \}$, $\{B, G\}$, $\{C,G\}$, $\{D,F\}$, $\{D,G\}$, $\{E,F\}$, $\{F,G\}$

$\RR_3=$ {$\{A,D,G\}$, $\{B, C, G\}$, $\{B, E, F\}$, $\{B,F, G\}$, $\{D,F,G\}$}.

This gives,

\[
\]

We observe that $A$ and $D$ are switching rooks and they can be switched with $B$ and $C$. Then

\[
\{A,D\} \sim \{B,C\}, \ \{A,D,G\}\sim \{B,C,G\}
\]

\[
\widetilde{r}_{\PP}(t)=1+7t+11t^2+4t^3.
\]

By using , one can see that $h(t)=\widetilde{r}_{\PP}(t)$.

at (0.5,0.5)$A$;
at (1.5,0.5)$B$;
at (0.5,1.5)$C$;
at (1.5,1.5)$D$;
at (2.5,1.5)$E$;
at (0.5,2.5)$F$;
at (2.5,2.5)$G$;

A simple polyomino

As proved in <cit.>, Conjecture <ref> holds true for the class of simple thin polyominoes. In fact, by definition of a thin polyomino, it does not contain a square tetromino (see <cit.>) as a subpolyomino. This happens because there are no switching rooks in a simple thin polyomino $\PP$ and $\widetilde{r}_{\PP}(t)= r_{\PP}(t)=h(t)$. Moreover, by computational approach we obtain the following

Let $\PP$ be a simple polyomino with $\rank \PP \leq 11$ and let $\widetilde{r}_{\PP}(t)$ be the polynomial defined in Definition <ref>. Then $h(t)=\widetilde{r}_{\PP}(t)$.

To prove the claim we have implemented a computer program that, for a fixed
number $n$, performs the following steps:

(S1) compute the set of all the simple polyominoes of rank $n$;

(S2) for any polyomino of the set compute the polynomial $h(t)$;
(S3) for any polyomino of the set compute the polynomial $\widetilde{r}_\PP(t)$;

(S4) check whether the polynomial from step (S2) is equal to the polynomial from step (S3).

In particular, for step (S1) we slightly modified the implementation given in <cit.>. For step (S2) we used the Macaulay2 functions for the Hilbert series. For step (S3), we constructed the rook complex $\RR$ as the independence complex of the graph $G$ with $V(G)=\{x_C : C \in \PP \}$ and

\[
E(G)=\{\{x_C,x_D\} : \mbox{the cells $C$ and $D$ lie on the same row or column}\},
\]

and then, by introducing the equivalence relation, we constructed $\widetilde{\RR}$. Finally we refer the reader to <cit.> for a complete description of the algorithm that we used.

Now we will prove Conjecture <ref> for parallelogram polyominoes, that is we will prove the following.

Let $\PP$ a parallelogram polyomino and let $\widetilde{r}_{\PP}(t)$ be the polynomial defined in Definition <ref>. Then $h(t)=\widetilde{r}_{\PP}(t)$.

From Proposition <ref>, we know that a parallelogram polyomino can be seen as a simple planar distributive lattice. Furthermore, Remark <ref> shows that the join-meet ideal and polyomino ideal of a simple planar distributive lattice coincides. To achieve our aim, we will first recall some notions related to simple planar distributive lattices and their Hilbert series.

Let $x, y \in L$ such that $y$ covers $x$, that is, $x <y$ and there is no $z \in L$ such that $x<z<y$. Then the edge between $x$ and $y$ in the Hasse diagram of $L$ can be represented by $x \rightarrow y$. Recall from <cit.> that an edge-labeling $\lambda$ of L is an integer labelling of the edges in Hasse diagram of $L$. Each chain in $L$, say $\mathfrak{c}: x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_k$  can be labelled by a $k$-tuple $\lambda(\mathfrak{c})=(\lambda(x_0 \rightarrow x_1), \lambda(x_1 \rightarrow x_2),\ldots, \lambda(x_{n-1} \rightarrow x_n) )$. One can compare two such $k$-tuples $(a_1, \ldots , a_k)$ and $(b_1, \ldots , b_k)$ lexicographically, that is, $(a_1, \ldots , a_k) <_{\lex}(b_1, \ldots , b_k)$,  if the most-left nonzero component of the vector $(a_1-b_1, \ldots , a_k-b_k)$ is positive.

An edge labelling $\lambda$ of $L$ is called EL-labelling if for every interval $[x,y]$ in $L$, $\lambda$ satisfies the following:

* there  is a unique chain $\mathfrak{c} : x=x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_k=y$ such hat $\lambda(x_0 \rightarrow x_1) \leq \lambda(x_1 \rightarrow x_2) \leq \ldots \leq \lambda(x_{k-1} \rightarrow x_k) )$.

* for every other chain $\mathfrak{b} : x=y_0 \rightarrow y_1 \rightarrow y_2 \rightarrow \ldots \rightarrow y_k=y$, we have $\lambda (\mathfrak{b}) >_{\lex} \lambda (\mathfrak{c})$.

Let $\rank(L)=d+1$. Then for each maximal chain $\mathfrak{m}: \min{L}=x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_{d+1}=\max(L)$, the descent set of $\mathfrak{m}$ is $D(\mathfrak{m})= \{i : \lambda(x_{i-1} \rightarrow x_i)  > \lambda(x_{i} \rightarrow x_{i+1}) \}$. Then by following <cit.>, for any $S \subset [d]$, we set $\beta(S)$ to be the number of maximal chains $\mathfrak{m}$ in $L$ such that $D(\mathfrak{m})=S$. It is known from <cit.>, that

\[
\HS_{K[L]}(t)=\frac{h(t)}{(1-t)^{d+2}}
\]

\[
h(t)=\sum_{S \subset [d]} \beta(S) t^{|S|}.
\]

Our main goal is to interpret $ h(t)$ in terms of $\widetilde{r}_{\PP}(t)$.

Let $L$ be a simple planar distributive lattice of rank $d+1$.

* Let $\mm_0: x_0<x_1<\cdots<x_d< x_{d+1}$ be the maximal chain of $L$ with $x_t=(i_t,j_t)$ for all
$0\leq t\leq d+1$ satisfying the following property: $(i_0,j_0)=(0,0)$, $(i_{d+1},j_{d+1})=\max L$, and for any $(k,\ell)\in L$ with $k=i_t$ for some $t,$ if $\ell \geq j_t$ then $(k,\ell)=(i_s,j_s)$ for some $s\geq t$. We call such an $\mm_0$  the uppermost chain of $L.$ We label the edges of $\mm_0$ by $\lambda(x_t\to x_{t+1})=t+1$ for $0\leq t\leq d.$

* Similar to (1), we can generalize the notion of uppermost chain between any two elements of $L$. Let $x, y \in L$ such that $x < y$. Then the uppermost chain from $x$ to $y$ in $L$ is the uppermost chain of the sublattice $L\cap [x,y]$.

Note that the definition of upper most chain in above definition is the same as the one given in proof of Proposition <ref>. The Figure <ref> illustrates an example of an uppermost chain of a lattice $L$ and an example of an uppermost chain between two elements of $L$. The uppermost chains are indicated by thick lines.

[very thick] (2,1)–(1,2);
[very thick] (1,2)–(2,3);
(2,1) circle () node [anchor=west]$x$;
(2,3) circle () node [anchor=west]$y$;

The uppermost chain between $x$ and $y$.

[very thick] (1,0)–(0,1);
[very thick] (1,2)–(0,1);
[very thick] (1,2)–(0,3);
[very thick] (0,3)–(1,4);
(1,0) circle ();
(1,4) circle ();

The uppermost chain of $L$

Two examples of uppermost chains

In <cit.>, the following EL-labelling is defined for simple planar distributive lattices.

We label all the edges in the Hasse diagram of $L$ as follows. If $i_{t+1}=i_t+1,$, in other words if $x_t\to x_{t+1}$, is a horizontal edge, then we label by $t+1$ all the edges of $L$ of the form $(i_t,j)\to (i_{t+1},j)$. If $j_{t+1}=j_t+1$, that is, if $x_t\to x_{t+1}$ is a vertical edge, then we label by $t+1$ all the edges of $L$ of the form $(i,j_t)\to (i,j_{t+1})$. In <cit.>, it is shown that $\lambda$ is an EL-labelling.

In Figure <ref>, we give an illustration of  EL-labeling $\lambda$. The chain marked with thick line is the uppermost chain of $L$.

[thick] (0,0) –  (3,0);
[thick] (0,1) –  (4,1);
[thick] (1,2) –  (4,2);
[thick] (2,3) –  (4,3);

[thick] (0,0) –  (0,1);
[thick] (1,0) –  (1,2);
[thick] (2,0) –  (2,3);
[thick] (3,0) –  (3,3);
[thick] (4,1) –  (4,3);

at (0,0.5)[anchor=east]1;
at (0.3,1)[anchor=south]2;
at (1,1.5)[anchor=east]3;
at (1.3,2)[anchor=south]4;
at (2,2.5)[anchor=east]5;
at (2.3,3)[anchor=south]6;
at (3.3,3)[anchor=south]7;

at (1,0.5)[anchor=east]1;
at (2,0.5)[anchor=east]1;
at (3,0.5)[anchor=east]1;
at (0.3,0)[anchor=south]2;
at (2,1.5)[anchor=east]3;
at (3,1.5)[anchor=east]3;
at (4,1.5)[anchor=east]3;
at (1.3,1)[anchor=south]4;
at (1.3,0)[anchor=south]4;
at (3,2.5)[anchor=east]5;
at (4,2.5)[anchor=east]5;
at (2.3,2)[anchor=south]6;
at (2.3,1)[anchor=south]6;
at (2.3,0)[anchor=south]6;
at (3.3,2)[anchor=south]7;
at (3.3,1)[anchor=south]7;

The $EL$-labelling for a parallelogram polyomino

Throughout the following text, we will follow the EL-labelling given in Definition <ref>. The following remarks are immediate consequences of Definition <ref>.

* Let $(i,j) \rightarrow (i,j+1)$ and $(k,l) \rightarrow (k,l+1)$ be two edges in $L$ with $i \leq k$ and $j+1 \leq l$. Then $\lambda ((i,j) \rightarrow (i,j+1)) \leq \lambda ((k,l) \rightarrow (k,l+1) )$. In particular, if $(i,j) \rightarrow (i,j+1)$ and $(i,j+1) \rightarrow (i,j+2)$ are two edges in $L$, then

\[
\lambda ((i,j) \rightarrow (i,j+1)) < \lambda ((i,j+1) \rightarrow (i,j+2) ).
\]

* Let $(i,j) \rightarrow (i+1,j)$ and $(k,l) \rightarrow (k+1,l)$ be two edges in $L$ with $i+1 \leq k$ and $j \leq l$. Then $\lambda ((i,j) \rightarrow (i+1,j)) \leq \lambda ((k,l) \rightarrow (k+1,l) )$. In particular, if $(i,j) \rightarrow (i+1,j)$ and $(i+1,j) \rightarrow (i+2,j)$ are two edges in $L$, then

\[
\lambda ((i,j) \rightarrow (i+1,j)) < \lambda ((i+1,j) \rightarrow (i+2,j) ).
\]

* Let $(i,j) \rightarrow (i,j+1)$ and $(k,l) \rightarrow (k+1,l)$ be two edges in $L$ with $i \leq k$ and $j+1 \leq l$. Then $\lambda ((i,j) \rightarrow (i,j+1)) \leq \lambda ((k,l) \rightarrow (k+1,l) )$. In particular, if $(i,j) \rightarrow (i,j+1)$ and $(i,j+1) \rightarrow (i+1,j+1)$ are two edges in $L$, then

\[
\lambda ((i,j) \rightarrow (i,j+1)) < \lambda ((i,j+1) \rightarrow (i+1,j+1) ).
\]

* Let $(i,j) \rightarrow (i+1,j)$ and $(i+1,j) \rightarrow (i+1,j+1)$ be two edges in $L$. If $(i,j+1) \notin L$, then $(i,j) \rightarrow (i+1,j)$ and $(i+1,j) \rightarrow (i+1,j+1)$ appear in “most upper" chain in $L$ and  $\lambda ((i,j) \rightarrow (i+1,j)) \leq \lambda ((i+1,j) \rightarrow (i+1,j+1))$. However, if $(i,j+1) \in L$, then  $(i,j) \rightarrow (i,j+1)$ and $(i,j+1) \rightarrow (i+1,j+1)$  are edges in $L$. Moreover, due to (3) we have $\lambda ((i,j) \rightarrow (i,j+1)) \leq \lambda ((i,j+1) \rightarrow (i+1,j+1) )$. Following the Definition <ref>, we have

\[
\lambda ((i,j) \rightarrow (i,j+1)) = \lambda ((i+1,j) \rightarrow (i+1,j+1))
\]

\[
\lambda ((i,j+1) \rightarrow (i+1,j+1) ) =  \lambda ((i,j) \rightarrow (i+1,j) )
\]

which gives

\[
\lambda((i,j) \rightarrow (i+1,j)) \geq \lambda ((i+1,j) \rightarrow (i+1,j+1))
\]

* By using (1)–(4), we can compute the descent set of a maximal chain $\mathfrak{m}$ in $L$. If $\mathfrak{m}$ contains edges of the form  $(i,j) \rightarrow (i+1,j)$ and $(i+1,j) \rightarrow (i+1,j+1)$ and $(i,j+1) \in L$, then we have a descent at $(i+1,j)$.

* Let $x=(i,j), y=(p,q) \in L$ with $i<p$ and $j<q$ and let $\mathfrak c : x=x_0 < x_1 <\ldots < x_l=y$ be the uppermost chain between $x$ and $y$. It follows that if $(i,j+1)\in L$, then $x_1=(i,j+1)$. In fact according to Definition of maximal chain either $x_1=(i+1,j)$ or $x_1=(i,j+1)$ and from Definition <ref> since $j+1 > j$, it holds $x_1=(i,j+1)$. Similarly one proves that in an uppermost chain there are no descents.

The following definition is needed for the Proposition <ref>.

Let $C=[(i,j), (i+1,j+1)]$ be a cell in a simple planar distributive lattice $L$. Then the lower left corner $(i,j)$ of $C$ is denoted by $l(C)$. Given any maximal chain $\mathfrak{m}$ in a simple planar distributive lattice $L$, we say that $\mathfrak{m}$  has a descent at cell $C$ if $\mathfrak{m}$ passes through the edges $(i,j) \rightarrow (i+1,j)$ and $(i+1,j) \rightarrow (i+1,j+1)$.

Let $L$ be a simple planar distributive lattice. Then:

* for any maximal chain $\mathfrak{m}$ in $L$ with $|D(\mathfrak{m})|=r$ there exist $r$ cells $C_1$, $C_2$, $\ldots$, $C_r$ of $L$  with $l(C_k)=(i_k,j_k)$ for $ 1 \leq k \leq r$ such that

\[
i_1< i_2 < \ldots < i_r \mbox{ and } j_1< j_2 < \ldots < j_r.
\]

* for any $C_1, C_2, \ldots, C_r$ cells of $L$ with $l(C_k)=(i_k,j_k)$ for $ 1 \leq k \leq r$ such that

\[
i_1< i_2 < \ldots < i_r \mbox{ and } j_1< j_2 < \ldots < j_r,\]

there exists a maximal chain $\mathfrak{m}$ in $L$ that has descent at  $C_1, C_2, \ldots, C_r$ and  $|D(\mathfrak{m})|=r$.

(1) Let $\mm: x_0<x_1<\cdots<x_d< x_{d+1}$  be a maximal chain with descent set $D(\mathfrak m)=\{l_1,\ldots,l_r\}$ with $l_1 < \ldots < l_r$. Then $x_{l_1}< x_{l_2}< \ldots <x_{l_r}$. From Remark <ref>.(5) and Definition <ref>, for any $i \in \{1,\ldots, r\}$ there exists a cell $C_i$ such that lower right corner and the lower left corner of $C_i$ are $x_{l_i}$  and $x_{l_i-1}$, respectively.
We now prove that for any $k=1,\ldots,r-1$  we have $i_k<i_{k+1}$ and $j_{k}<j_{k+1}$. From the fact that, $x_{l_{k}-1}<x_{l_{k+1}-1}$ it follows that $i_k \leq i_{k+1}$. By contraposition, assume that $i_k = i_{k+1}$ for some $k$, then we have that $x_{l_k-1}=(i_k,j_k)$, $x_{l_k}=(i_k+1,j_k)$ and $x_{l_{k+1}-1}=(i_k,j_{k+1})$. That is, $x_{l_k} \not < x_{l_{k+1}-1}$, hence $\mm$ is not a chain and this is a contradiction. Hence $i_k < i_{k+1}$ and similarly $j_k < j_{k+1}$.

(2) For a cell $C \in \PP$, let $r(C)$ be its lower right corner. Let $\mathfrak c_0$ be the uppermost chain between $(0,0)$ and $(i_1,j_1)$ and for $1\leq k \leq r-1$ let $\mathfrak{c}_{k}$ be the uppermost chain between $r(C_k)=(i_k+1,j_k)$ and $l(C_{k+1})=(i_{k+1},j_{k+1})$ and let $\mathfrak c_r$ be the uppermost chain between $r(C_{r})$ and $(m,n)$. From the concatenation of $\mathfrak c_0 \mathfrak c_1 \ldots \mathfrak c_r $, we obtain in a natural way a maximal chain $\mathfrak m$ of $L$. We prove that $\mathfrak{m}$ has descent at  $C_1, C_2, \ldots, C_r$. We fix $k\in \{1,\ldots,r\}$. According to Remark <ref>.(5), since  $(i_k,j_k)\rightarrow (i_k+1,j_k) \in E(\mathfrak m)$, it is sufficient to prove $(i_k+1,j_k)\rightarrow (i_k+1,j_k+1) \in E(\mathfrak m)$. The assertion follows from Remark <ref>.(6) applied to the uppermost chain $\mathfrak c_{k+1}$. Therefore, $\mathfrak m$ has descent at $C_k$. This completes the proof.

In order to prove Theorem <ref>, we premise the following lemma which shows that given any set of non-attacking rooks in a parallelogram polyomino, one can find an equivalent set of non-attacking rooks whose lower left corners appear in a chain.

Let $\PP$ be a parallelogram polyomino and let $F=\{A_1,\ldots, A_d\}\in \RR$. Then there exists  $G=\{B_1,\ldots, B_d\}\in \RR$  with $l(B_k)=(i_k,j_k)$ for $ 1 \leq k \leq d$ such that

\[
i_1< i_2 < \ldots < i_d \mbox{ and } j_1< j_2 < \ldots < j_d
\]

and $F\sim G$.

Let $l(A_i)=(x_i,y_i)$ for $i =1,\ldots, d$.
We prove the assertion by applying induction on $d$.

Let $d=2$ and assume that $\mathcal{A}=\{A_1,A_2\}$ is labelled such that $x_1 < x_2$. If $y_1 < y_2$ then the statement holds trivially. If $y_1>y_2$, then by using the assumption that $\PP$ is a parallelogram polyomino and hence a distributive lattice, we conclude that the join $b_1=(x_2,y_1)$ and the meet $b_2=(x_1,y_2)$ of $\mathcal{A}_1$ and $\mathcal{A}_2$ belong to $V(\Pc)$. In particular, $b_1$ and $b_2$ are lower left corners of some cells of $\PP$ and $A_1$ and $A_2$ are antidiagonal cells of a rectangle of $\PP$. Let $B_1$ and $B_2$ be the cells having lower left corners $b_1$ and $b_2$, respectively. It follows that the set $\{B_1,B_2\}$ satisfies the assertion.
Now, let $d>2$ and assume that the assertion is true for all of the sets containing $d-1$ non-attacking rooks.
We label the elements of $\mathcal{A}$ in a way such that $x_1< x_2< \ldots < x_d$. Let $k\in \{1,\ldots, d\}$ such that $y_k < y_{i}$ for $i\neq k$. If $k=1$, then we set $B_1=A_1$ and we apply the inductive hypothesis on the set $\{A_2,\ldots , A_d\}$ to get the desired result.

If $k>1$, then let $B_1$ and $C_k$ be the cells whose lower left corners are respectively $(x_1,y_k)$ and $(x_k,y_1)$. Then $\{A_2,\ldots, A_{k-1},C_k,A_{k+1},\ldots, A_d\}$ is a set of $d-1$ non-attacking rooks and by applying the inductive hypothesis the assertion follows.

Now we state the proof of Theorem <ref>.

\[
\HS_{K[\PP]}(t)=\frac{\sum\limits_{k} h_{k}t^k}{(1-t)^{\dim K[\PP]}}.
\]

We show that for any $k$ one has $\widetilde{r}_k=h_k$.

For $k=0,1$ it is easy to see that $\widetilde{r}_k=h_k$.

For $k\geq 2$, by Proposition <ref>  the maximal chains with descent set of cardinality $k$ in $\PP$ seen as a planar distributive lattice are in bijection with the sets $F$ of non-attacking rooks $B_1,\ldots, B_k$ with $l(B_\ell)=(i_\ell,j_\ell)$ for $ 1 \leq \ell \leq k$ such that $i_1< i_2 < \ldots < i_k \mbox{ and } j_1< j_2 < \ldots < j_k$. Thanks to Lemma <ref>, such sets $F$ are the representatives of the equivalence classes of $\RR_k / \sim$, that is $\widetilde{r}_k=h_k$.

As a consequence of Theorem <ref>, we observe that the Conjecture <ref> also holds for $L$-convex polyominoes. As stated in Section <ref>, the coordinate ring of an $L$-convex polyomino is isomorphic to the coordinate ring of a suitable Ferrer diagram. Then the conclusion follows from the fact that every Ferrer diagram is a parallelogram polyomino. We also note that the Hilbert series of Ferrer diagram was given in <cit.>.

From Lemma <ref>, it follows that for a parallelogram polyomino $\PP$ the coordinate ring $K[\PP]$ is a Cohen-Macaulay domain. Furthermore, as mentioned at the beginning of this section, $\deg h(t)=\reg K[\PP]$. Hence we obtain the following corollary of Theorem <ref>.

Let $\PP$ be a parallelogram polyomino. Then $\reg K[\PP] = r(\PP)$.

§ GORENSTEIN PARALLELOGRAM POLYOMINOES

Given a polyomino $\PP$, we call $\PP$ Gorenstein if $K[\PP]$ is Gorenstein. In this section we discuss the Gorenstein parallelogram polyominoes. Although the Gorenstein distributive lattices are completely characterized in <cit.>,  we plan to give a combinatorial interpretation of the Gorenstein parallelogram polyominoes in the language of polyominoes. Our aim is to compare the conditions on a parallelogram polyomino to be Gorenstein with the conditions found in <cit.> for $L$-convex polyominoes and in <cit.> for simple thin polyominoes.

Let $\MM(\PP)$ be the set of the maximal rectangles of $\PP$. We generalize <cit.> with the following.

Let $S$ be a rectangular (square) subpolyomino of a parallelogram polyomino $\PP$. Then $S$ is said to be single if there exists a unique maximal rectangle $R \in \MM(\PP)$ such that $S \subseteq R$ and $S \cap R' =\varnothing$ for all $R' \in \MM(\PP)$ with $R'\neq R$. We say that $\PP$ has the $S$-property if each maximal rectangle $R$ of $\PP$ has a unique single square.

To see an illustration of the above definition, consider the parallelogram polyomino $\PP$ given in Figure <ref>.(1). $\Pc$ has six maximal rectangles

\[
\{A,B\},\{B,C,E\}, \{C,D,E,F,\}, \{D,F,H\}, \{E,F,G\}, \{F,G,H,I\}
\]

The maximal rectangle $\{A,B\}$ has $A$ as its single square, and the maximal rectangle $\{F,G,H,I\}$ has $I$ as its single square. However, other rectangles do not have a single square or a single rectangle because each of their cells belong to other rectangles as well. The maximal rectangles $\{A,B\}$ and $\{F,G,H,I\}$ are special in a sense that $\{A,B\}$  is the unique maximal rectangle containing $\min (\PP)$ (as a distributive lattice) and  $\{F,G,H,I\}$ is the unique maximal rectangle containing $\max (\PP)$.

Next, we prove that if a maximal rectangle $R$ in a parallelogram polyomino $\PP$ contains either $\min(\PP)$ or $\max(\PP)$ then $R$ must contain a single rectangle. Given a parallelogram polyomino $\PP$, we set $\min (\PP)=(0,0)$ throughout the following text.

Let $\PP$ be a parallelogram polyomino. Then there exists a unique $R \in \MM(\PP)$ such that $(0,0) \in V(R)$. In particular, the maximal rectangle $R$ has a single rectangle.

By contraposition, assume that there are two distinct maximal rectangles $R,R'$ of $\PP$, such that $(0,0)\in V(R)\cap V(R')$. Let $a,b,c,d \in V(\PP)$ be such that $V(R)=[(0,0),(a,b)]$ and $V(R')=[(0,0),(c,d)]$. Since $R$ and $R'$ are distinct, without loss of generality, we may assume that $a <c$ and $b>d$. From Proposition <ref>, it follows that $\PP$ is a simple planar distributive lattice. Therefore, $(c,b)\in V(\PP)$ because it is join of $(a,b)$ and $(c,d)$. This shows that the rectangle $\widetilde{R}$ with $V(\widetilde{R})=[(0,0),(c,b)]$ contains both $R$ and $R'$, a contradiction to the maximality of $R$ and $R'$. Therefore, we conclude that there exists a unique maximal rectangle $R$ that contains $(0,0)$. In addition, we obtain that the cell with lower left corner $(0,0)$ only belongs to $R$. This shows that $R$ must have a single rectangle.

In the following text, for a given parallelogram polyomino $\PP$, the unique maximal rectangle of $\PP$ containing  $\min (\PP) =(0,0)$ is denoted by $R_0$. Let $\PP'$ be a subpolyomino of $\PP$. Then $\PP\setminus \PP'$ is a collection of cells obtained by removing all cells of $\PP'$ from $\PP$. Next, we introduce a new family of parallelogram polyominoes.

A parallelogram polyomino $\PP$ is said to be shortenable if $\PP \setminus R_0$ is a parallelogram polyomino.  Moreover, $\PP$ is well-shortenable if $\PP$ is shortenable and either $\PP\setminus R_0$ is a rectangle or $\PP\setminus R_0$ is a well-shortenable parallelogram polyomino. The sequence of polyominoes $\{\PP_i\}_{i=1,\ldots l}$ such that $\PP_1=\PP\setminus R_0$, and $\PP_{i+1}=\PP_i\setminus R_i$  where $R_i$ is the unique rectangle containing $\min (\PP_i)$, is called the derived sequence of $\PP$.

We observe that a thin parallelogram polyomino and an $L$-convex parallelogram polyomino (Ferrer diagram) are well-shortenable.
In particular, for a Ferrer diagram the definition of  derived sequence coincides with the one of <cit.>.

We give an example of a shortenable polyomino that is not well-shortenable. Let $\PP$ be the parallelogram polyomino in Figure <ref>. We observe that the maximal rectangle $R_0$ of $\PP$ is the maximal rectangle on the cells $A$ and $B$, and the polyomino $\PP_1= \PP\setminus R_0$ is a parallelogram polyomino. Then $\PP$ is shortenable. However, the rectangle $R_1$ in $\PP_1$ is the maximal rectangle on the cells $\{C,D,E,F\}$ and $\PP_1\setminus \{C,D,E,F\}$ is not a parallelogram polyomino (without rotation).

at (0.5,0.5)$A$;
at (1.5,0.5)$B$;
at (1.5,1.5)$C$;
at (2.5,1.5)$D$;
at (1.5,2.5)$E$;
at (2.5,2.5)$F$;
at (3.5,2.5)$G$;
at (2.5,3.5)$H$;
at (3.5,3.5)$I$;

at (1.5,1.5)$C$;
at (2.5,1.5)$D$;
at (1.5,2.5)$E$;
at (2.5,2.5)$F$;
at (3.5,2.5)$G$;
at (2.5,3.5)$H$;
at (3.5,3.5)$I$;

$\PP_1=\PP\setminus \{A,B\}$

at (3.5,2.5)$G$;
at (2.5,3.5)$H$;
at (3.5,3.5)$I$;

$\PP_1\setminus \{C,D,E,F\}$

A shortenable polyomino that is not well-shortenable

In order to characterize the parallelogram polyominoes that are shortenable, we prove the following.

Let $\PP$ be a parallelogram polyomino. Assume that $R_0$ has size $s\times t$ and its single rectangle $R$ has size $s'\times t'$ with $s'<s$ and $t' < t$. Then there exist $R',R'', \widetilde{R} \in \MM(\PP)$ as in Figure <ref>.

[pattern=north west lines] (0,1) rectangle (4,2);
[pattern=north east lines] (2,0) rectangle (3,3);

(0,0) circle () node [anchor=north]$(0,0)$;

at (1,0.5)$R$;
at (-0.3,1)$R_0$;
at (4.3,1.5)$R'$;
at (2.5,-0.3)$R''$;
at (3,3.3)$\widetilde{R}$;

Let $\PP=(\SS_1,\SS_2)$. If $s'<s$ and $t'<t$, then all cells of $R$ with lower corner $(a,b)$ with either $s'\leq a$ or $t'\leq b$ belong to some other maximal rectangles of $\PP$ as well. Using the fact that $R_0 \in \MM(\PP)$, we observe that $\SS_2$ takes a north step at $(s,0)$. By using the assumptions $s'<s$ and $t'<t$ and $R$ is the single square of $R_0$, we conclude that $\SS_2$ changes the direction from north to east at  $(s,t')$. Then the co-ordinates of $R'$ are determined by the next north turn of $\SS_2$. Similar argument on $\SS_1$ shows the existence of $R''$. The existence of $\tilde{R}$ is guaranteed by the fact that $\PP$ is a parallelogram polyomino and hence a distributive lattice, therefore the join of the diagonal corners of $R'$ and $R''$ must belong to $V(\PP)$.

In the following, we give a characterization of parallelogram polyominoes that are shortenable in terms of the sizes of the single rectangle of $R_0$.

Let $\PP$ be a parallelogram polyomino and assume $R_0$ has size  $s \times t$. Then $\PP$ is shortenable if and only if the single rectangle $R$ of $R_0$ has size $s'\times t'$ with either $s'=s$ or $t'=t$.

By contraposistion, assume that $R$ has size $s' \times t'$ with $s'<s$ and $t'<t$. From Lemma <ref> there exists a rectangle $\widetilde{R}$ having vertices $[(s',t'),(p,q)]$ with $p> s $ and $q>t$. We consider the polyomino $\PP_1=\PP\setminus R_0$. We observe that $(s',q),(p,t')\in V(\PP_1)$ with $s'<s<p$ and $t'<t<q$, that is a contradiction to the fact that $\PP$ is parallelogram.

Conversely, assume that  $V(R)=[(0,0),(s',t)]$ with $s'<s$. Then using Proposition <ref>, we obtain $\PP\setminus R_0$  is the parallelogram polyomino that corresponds to the sublattice $L\cap [(s',t),\max L]$.

We now want to link the shortenability to the Gorensteinness. Hibi showed in <cit.> that given a distributive lattice $L$, the Hibi ring $K[L]$ is Gorenstein if and only if the poset $P$ of the join-irreducible elements of $L$ is pure. Hence we look at the structure of the poset of the join-irreducible elements of parallelogram polyomino $\PP$ that we identify as a distributive lattice.

Let $H_0, H_1, \ldots, H_n$ be the maximal edge horizontal intervals of $\Pc$ and $V_0, V_1, \ldots, V_n$ be the maximal edge vertical intervals of $\Pc$. Note that $H_0\cap V_0=\{(0,0)\}=\min L$. Set $h_i=\min (H_i)$ for all $1\leq i \leq n$ and $v_j=\min (V_i)$ for all $1\leq j \leq m$.

Then $h_1\leq h_2\leq \ldots \leq h_n$ and $v_1 \leq v_2 \leq \ldots \leq v_m$ are two maximal chains of $P$.

(0,1) circle () node [anchor=east]$h_1$;
(1,2) circle () node [anchor=east]$h_2$;
(1,3) circle () node [anchor=east]$h_3$;
(2,4) circle () node [anchor=east]$h_4$;

at (1,0)$\times$;
at (1,0)[anchor=north]$v_1$;

at (2,0)$\times$;
at (2,0)[anchor=north]$v_2$;

at (3,1)$\times$;
at (3,1)[anchor=north]$v_3$;

at (4,2)$\times$;
at (4,2)[anchor=north]$v_4$;

The join-irreducible elements are the minimum of the maximal horizontal and vertical edge intervals

(0,0) circle () node [anchor=east]$h_1$;
(0,1) circle () node [anchor=east]$h_2$;
(0,2) circle () node [anchor=east]$h_3$;
(0,3) circle () node [anchor=east]$h_4$;

(1,0) circle () node [anchor=west]$v_1$;
(1,1) circle () node [anchor=west]$v_2$;
(1,2) circle () node [anchor=west]$v_3$;
(1,3) circle () node [anchor=west]$v_4$;

The poset $P$ of join-irreducible elements

In <cit.>, the authors prove that an $L$-convex polyomino $\PP$ with derived sequence $(\PP_k)_{k=1, \ldots, t}$ for some $t$ is Gorenstein if and only if the bounding box of any $\PP_k$ is a square. For parallelogram polyominoes the latter condition is necessary but not sufficient, as shown in Figure <ref>. The polyomino $\PP$ in Figure <ref> is known to be non-Gorenstein from <cit.>, while $\PP$, $\PP_1$ and $\PP_2$ have square bounding boxes.

at (1.5,3);

at (1.5,3);

An example of non-Gorenstein parallelogram polyomino with square bounding boxes

Next, we prove that a Gorenstein parallelogram polyomino is well-shortenable.

Let $\PP$ be a parallelogram polyomino. If $\PP$ is Gorenstein, then $\PP$ is well-shortenable.

Let $\PP$ be Gorenstein. Then due to <cit.>, the poset $P$ of join-irreducible elements of $\PP$ is pure. Assume that $\PP$ is not shortenable. Then by using Lemma <ref>, we obtain that if $R_0$ has size $s\times t$ with $t<s$ then the single rectangle of $R$ has size $r\times q$ with $r<s$ and $q<t$. From Lemma <ref>, we can find a maximal rectangle $R'$ with $V(R')=[(r,0),(s,w)]$ with $w > t$, as shown in Figure <ref>.

(0,1) circle () node [anchor=east] $h_q$;
(0,2) circle () node [anchor=east]$h_t$;
(2,2.3) circle () node [anchor=east]$h_{t+1}$;

at (2,0)$\times$;
at (2,0) [anchor=north]$v_r$;

at (1,0.5)$R$;
at (3.3,1.5)$R'$;

This implies that $v_r\leq h_{t+1}$, that is

\[
h_1\leq h_2\leq \ldots \leq h_n, \ \ \ v_1 \leq v_2 \leq \ldots \leq v_r \leq h_{t+1}\leq \ldots \leq h_n
\]

are two maximal chains of the poset $P$. The first chain has length $n$ while the second has length $n-t+q<n$ because $q<t$. This contradicts the Gorensteinness of $\PP$. Therefore, we conclude that $\PP$ is shortenable and hence, $ \PP_1=\PP\setminus R_0$ is a parallelogram polyomino.

To show that $\PP$ is well-shortenable, it is enough to show that $\PP_1$ is Gorenstein. Indeed, if $\PP_1$ is Gorenstein then by following the previous argument, it is shortenable and the conclusion follows by applying the same argument. Let $P_1$ be the poset of the join-irreducible elements of $\PP_1$. Assume that the single rectangle $R$ of $R_0$ (in $\PP$) is such that $V(R)=[(0,0),(r,t)]\subset V(R_0)=[(0,0),(s,t)]$. Then $\min (\PP_1)=(r,t)$ and in $P$ we have $v_{r}\leq h_{t+1}$. If $\PP_1$ is not Gorenstein, then there exists two chains

\[
c_1\leq c_2 \leq \ldots \leq c_l, \ \ d_1\leq d_2 \leq \ldots \leq d_h
\]

with $c_i,d_j \in V(P_1)=\{v_{r+1},\ldots,v_n,h_{t+1},\ldots , h_n\}$ and $l\neq h$. If $c_1=d_1=h_{t+1}$, then $h_1\leq\ldots \leq h_t \leq c_1\leq c_2 \leq \ldots \leq c_l$ and $h_1\leq\ldots \leq h_t\leq d_1\leq d_2 \leq \ldots \leq d_h$ are two maximal chains of $P$ having different lengths, a contradiction to the Gorensteinness of $\PP$. Similar arguments hold for the case $c_1=d_1=v_{r+1}$. We are left with the case $c_1=h_{t+1}$ and $d_1=v_{r+1}$. Since $v_{r}\leq h_{t+1}$, then

\[
v_1\leq \ldots \leq v_{r} \leq c_1 \leq c_2 \leq \ldots \leq c_l, v_1\leq \ldots \leq v_{r} \leq d_1 \leq d_2 \leq \ldots \leq d_h
\]

are two chains of $P$ having lengths $r+l$ and $r+h$ and since $h\neq l$, then they have different lengths and $\PP$ is not Gorenstein, a contradiction. This shows that $\PP\setminus R_0$ is Gorenstein and hence shortenable.

In order to link the Gorensteinness with the $S$-property, we prove that a parallelogram polyomino with $S$-property is well shortenable.

Let $\PP$ be a parallelogram polyomino with S-property. Then $\PP$ is shortenable.

Let $S$ be the single square of $R_0$. Assume that $R_0$ has size $s \times t$ and $S$ has size $r \times r$ with $r<\min \{s,t\}$. From Lemma <ref>, there exist some maximal rectangles $R',R''$ and $\widetilde{R}$ as in Figure <ref>. We observe that in this case $R',R''$ are contained in $R_0\cup \widetilde{R}$, that is they do not have single squares, and it is a contradiction to the fact that $\PP$ has the $S$-property. Therefore, either $r=s$ or $r=t$ and the conclusion follows from Lemma <ref>.

Let $\PP \subseteq [m,n]$ be a parallelogram polyomino with S-property, let $R_0,\ldots, R_l$  be the maximal rectangles of $\PP$ having single squares $S_0,S_1,\ldots S_l$ of sizes $t_1 \times t_1,\ldots, t_l \times t_l$, respectively. For any $i \in {1,\ldots, l}$ let $c_i=\sum_{j=1}^i t_j$. Then, we have  $V(S_{i})\cap V(S_{i+1})=(c_i,c_i)$ and $m=n=c_l$. Moreover $\PP$ is well-shortenable.

From Lemma <ref> we have that $V(S_0)=[(0,0),(t_1,t_1)]$ and $\PP$ is shortenable. Let $\PP_1=\PP\setminus R_0$. From Lemma <ref> applied to $\PP_1$, we obtain that $S_1$ is such that $V(S_1)=[(t_1,t_1),(c_2,c_2)]$. We recursively consider the polyomino $\PP_i$ obtained from from $\PP_{i-1}$ by removing the rectangle $R_i$ and we obtain from Lemma <ref>.that $V(S_{i+1})=[(c_i,c_i),(c_{i+1},c_{i+1})]$. The polyomino $\PP_l$ is a square, that is $c_l=m=n$ and $\PP$ is well-shortenable.

Now we prove the main theorem of this section.

Let $\PP$ be a parallelogram polyomino. The following are equivalent:

(i) $\PP$ is Gorenstein;

(ii) $\PP$ has the $S$-property.

(i)$\Rightarrow$(ii). From Lemma <ref>, we have that $\PP$ is well shortenable. Moreover, from the proof of Lemma <ref> it arises that all of the polyominoes in the derived sequence are Gorenstein, that is they have square bounding boxes. In particular $\PP \subset  [(0,0),(n,n)]$.

First, we show that the single rectangle $R$ of $R_0$ is a square. Let $P$ be the poset of the join-irreducible elements of $\PP$. Assume that

\[
V(R)=[(0,0),(s,t)]\subset V(R_0)=[(0,0),(q,t)]
\]

with $s \neq t$. Hence $\min V(\PP_1)=(s,t)$ and in $P$ we have $v_{s}\leq h_{t+1}$. This gives that the two chains

\[
v_1 \leq \ldots \leq v_s\leq v_{s+1} \leq \ldots \leq v_n, v_1 \leq \ldots \leq v_s\leq h_{t+1} \leq \ldots \leq h_n
\]

have different lengths and this is a contradiction to the assumption that $P$ is Gorenstein. That is $s=t$. Let $R_1$ be the maximal rectangle such that $R_0\cap R_1=R_0\setminus R$. We show that $R_1$ has a single rectangle. If this is not the case, then there exists a maximal rectangle $R_2$ such that $R_1 \subseteq R_0 \cup R_2$ and $V(R_2)=[(s,s),(a,b)]$ with $a > q$, hence $h_s \leq v_{q+1}$ in $P$. This implies that

\[
h_1 \leq \ldots \leq h_s\leq v_{q+1} \leq \ldots \leq v_n, h_1 \leq \ldots \leq h_n
\]

are two chains of different length since $s<q<q+1$. In particular this implies that any maximal rectangle has a single rectangle. By using a similar technique on any polyomino of the derived sequence we obtain that all of the rectangles of $\PP$ have a single square.

(ii)$\Rightarrow$(i). We assume that $\PP$ has the $S$-property. To have the Gorensteinness, we have to prove that for any edge in the Hasse diagram of the poset $\PP$ of the form $v_s \to h_{t+1}$ (or $h_c \to v_{d+1}$), we have $s=t$ (or $c=d$). We follow the notation of Corollary <ref>. From the latter result we obtain that if $S_0$ has size $t_0 \times t_0$ and $S_1$ has size $t_1 \times t_1$. Then $R_0$ has either size $t_0 \times (t_0 +t_1)$ or $(t_0 +t_1) \times t_0$, that is either $h_{t_0}\to v_{t_0 +1}$ or $v_{t_0}\to h_{t_0 +1}$.
Since $\PP$ is well-shortenable, we inductively apply the same argument to find that for any $k \in \{1,\ldots l\}$ either $h_{c_k}\to v_{c_k +1}$ or $v_{c_k}\to h_{c_k +1}$.
Moreover, assume that  $h_r \to v_s$ is an edge of the poset $P$ such that $c_{k-1}+1 \leq r < c_{k}$ for some $k$. It follows that $s>c_{k}+1$ and there exists a maximal rectangle in $\MM(\PP)$ of size $a \times b $ with $b = c_{k}-r$  that has non-empty intersection with $S_k$. This leads to a contradiction to the fact that $S_k$ is single.

Now, we give a description of Gorenstein parallelogram polyominoes in terms of the 2-colored Motzkin paths. To do this, we first recall the well-known bijection between the parallelogram polyominoes and 2-colored Motzkin paths, see <cit.>.  Let $(a,b) \in \NN$. Then

* the edge $\{(a,b), (a+1,b+1)\}$ is called a  rise step,

* the edge $\{(a,b), (a+1,b-1)\}$ is called a fall step,

* the edge $\{(a,b), (a+1,b)\}$ is called a east step or a horizontal step.

A 2-colored Motzkin path

\[
\mathcal{M}: (0,0)=(a_0,b_0), (a_1, b_1), \ldots, (a_n,b_n)=(n,0)
\]

in $\NN \times \NN$ is a path that never passes below the $x$-axis and consists of rise steps, fall steps and two types of horizontal steps that are called $\alpha$-colored horizontal steps and $\beta$-colored horizontal steps. Each 2-colored Motzkin path can be regarded as a 2-colored Motzkin word. For more information, see <cit.>.
Let $\Pc$ be a parallelogram polyomino determined by $(\mathcal{S}_1,\mathcal{S}_2)$ such that $\mathcal{S}_1$ and $\mathcal{S}_2$ intersect at $(0,0)$ and $(m,n)$. Then $\Pc$ can be encoded in a unique 2-colored Motzkin path $\MM_\PP$ as described in the following algorithm given in <cit.>.

Each north-east path in $\NN \times \NN$ of length $n$ can be identified as a binary sequence with 0 representing an east step and 1 representing a north step.   Let $\Pc=(\SS_1, \SS_2)$ be a parallelogram polyomino and set $u(\Pc)$ be the binary tuple representing $\SS_1$ and $\ell(\Pc)$ be the binary tuple representing $\SS_2$. Create a matrix $M$ with $u(\Pc)$ as its first row and $\ell(\Pc)$ as its second row.  Then $M$ can be encoded as a Motzkin path by the coding:

\begin{equation}
\begin{aligned}[a]
&\binom{1}{0} \mapsto  \text{rise step}  &  &\binom{0}{1} \mapsto  \text{fall step}\\
&\binom{1}{1} \mapsto  \text{$\alpha$-colored horizontal step}  &  &\binom{0}{0} \mapsto  \text{$\beta$-colored horizontal  step}
\end{aligned}
\label{eq:coding}
\end{equation}

at (0.5,0) [anchor=north]$0$;
at (1.5,0) [anchor=north]$0$;
at (2.7,1) [anchor=north]$0$;
at (3.7,2) [anchor=north]$0$;

at (2,0.5) [anchor=west]$1$;
at (3,1.5) [anchor=west]$1$;
at (4,2.5) [anchor=west]$1$;
at (4,3.5) [anchor=west]$1$;

at (0,0.5) [anchor=east]$1$;
at (1,1.5) [anchor=east]$1$;
at (1,2.5) [anchor=east]$1$;
at (2,3.5) [anchor=east]$1$;

at (0.3,1) [anchor=south]$0$;
at (1.3,3) [anchor=south]$0$;
at (2.5,4) [anchor=south]$0$;
at (3.5,4) [anchor=south]$0$;

[dashed] (0,0)–(8,0);
[dashed] (0,1)–(8,1);
[dashed] (0,2)–(8,2);
[dashed] (0,3)–(8,3);
[dashed] (0,4)–(8,4);
[dashed] (0,5)–(8,5);
[dashed] (0,6)–(8,6);

[dashed] (0,0)–(0,6);
[dashed] (1,0)–(1,6);
[dashed] (2,0)–(2,6);
[dashed] (3,0)–(3,6);
[dashed] (4,0)–(4,6);
[dashed] (5,0)–(5,6);
[dashed] (6,0)–(6,6);
[dashed] (7,0)–(7,6);
[dashed] (8,0)–(8,6);

[ultra thick] (0,2)–(1,3);
[ultra thick, densely dashed] (1,3)–(2,3);
[ultra thick] (2,3)–(3,3)–(4,4)–(5,3)–(6,4)–(8,2);

at (0.5,5.5)rise;
at (1.5,5.5)$\beta$;
at (2.5,5.5)$\alpha$;
at (3.5,5.5)rise;
at (4.5,5.5)fall;
at (5.5,5.5)rise;
at (6.5,5.5)fall;
at (7.5,5.5)fall;

A parallelogram polyomino with its Motzkin path

For example, Figure <ref> shows a  parallelogram polyomino and the associated 2-colored Motzkin path. The $\beta$-colored horizontal steps are shown as dashed lines and the $\alpha$-colored steps are shown as normal lines.
We observe that

\[
u(\PP)= 1 0 1 1 0 1 0 0  \ \ \ \
\ell(\PP)= 0 0 1 0 1 0 1 1
\]

The associated matrix $M$ of $\Pc$ described above is :

\[
\begin{pmatrix}
1 &0 &1 &1 &0 &1 &0 &0\\
0 &0 &1 &0 &1 &0 &1 &1 \\
\end{pmatrix}
\]

We need the following terminologies to describe Gorenstein parallelogram polyominoes in terms of their associated 2-colored Motzkin paths.

* Let $\SS:s_1,\ldots, s_l$ be a north-east path. A sequence of consecutive north steps (resp. east steps) $s_i,\ldots, s_{i+k}$ makes a maximal block of length $k$ in $\SS$ if either $i=1$ or $s_{i-1}$ is an east step (resp. north step), and either $i+k=l$ or $s_{i+k+1}$ is a north step (resp. east step). Note that in $\SS$, a maximal block of length $k$ of consecutive north steps corresponds to a maximal block of $k$ 1s in its binary representation. Similarly, a maximal block of length $k$ of consecutive east steps in $\SS_1$ corresponds to a maximal block of $k$ 0s in its binary representation.

* let $\PP=(\SS_1,\SS_2)$ be a parallelogram polyomino. A sequence of consecutive elements $s_1, s_2,\ldots, s_{l}$ of $\SS_1$ (resp. $\SS_2$) is called a maximal NE-block if there exists $i \in \{1,\ldots l\}$ such that $s_1 \ldots s_i$ is a maximal block of north steps (resp. east steps) and $s_{i+1} \ldots s_l$ is a maximal block of east steps (resp. north steps).

For example, for the parallelogram polyomino given in Figure <ref>, the binary representation of $\SS_1$ is $u(\PP): 10110100$.  The maximal NE-block in $\SS_1$ are $10$, $110$ and $100$. The NE-blocks in $\SS_1$ determine the corners in $\SS_1$. Similarly, the maximal NE-block in $\SS_2$ are $001$, $01$, and  $011$ and the NE-blocks in $\SS_2$ determine the corners in $\SS_2$. We emphasize that in $\SS_1$ each NE-block starts with a north step, while an NE-block in $\SS_2$ starts with an east step.

Let $\PP=(\SS_1,\SS_2)$ be a parallelogram polyomino. $\PP$ has the $S$-property if and only if the following conditions hold:

* in $\SS_1$, each maximal block of length $k$ of consecutive north steps is followed by a maximal block of length $k$ of consecutive east steps.

* in $\SS_2$, each maximal block of length $k$ of consecutive east steps of is followed by a maximal block of length $k$ of consecutive north steps.

Assume that $\PP$ has the $S$-property. We need to show that $\PP$ satisfies the conditions (1) and (2). We proceed by induction on the total number $l$ of maximal rectangles of $\PP$.

If $l=1$, then $\PP$ itself is a rectangle. Using the assumption that $\PP$ has the $S$-property, we see that $\PP$ is in fact a square of size $t\times t$. This shows that binary representations of $\SS_1$ and $\SS_2$ are given by

\[
u(\PP): \ \underbrace{11\ldots1}_{t \mbox{ \scriptsize times}} \underbrace{00\ldots0}_{t \mbox{ \scriptsize times}}, \ \ \ \ell (\PP) : \  \underbrace{00\ldots0}_{t \mbox{ \scriptsize times}} \underbrace{11\ldots1}_{t \mbox{ \scriptsize times}}
\]

as claimed.

Now assume that $l\geq 2$ and the assertion is true for any parallelogram polyomino with $l-1$ maximal rectangles. Let the size of $R_0$ be $s \times t$. Assume that $t<s$, and the case when $t>s$ can be discussed in a similar way. The assumption that $\Pc$ has the $S$-property together with Lemma <ref> and <ref> shows that the single square $S$ of $R_0$ has size $t\times t$. Consider the parallelogram polyomino $\PP'= \PP\setminus R_0$ given by some paths $(\SS_1', \SS_2')$. Then $\PP'$ also has the $S$-property. We observe that since $S$ is single square, the path $\SS_1$ is of the form

\[
\underbrace{11\ldots1}_{t \mbox{ \scriptsize times}}\underbrace{00\ldots0}_{t \mbox{ \scriptsize times}}u(\PP').
\]

where $u(\PP')$ is the binary representation of $\SS'_1$. By using the inductive hypothesis on $\PP'$ we conclude that $\PP$ satisfies the condition (1). Moreover, again by using the inductive hypothesis on $\PP'$, we see that $\SS_2'$ satisfies condition (2). That is, the binary representation $\ell(\PP')$ of $\SS_2'$ starts with a block of $s-t$ $0$s followed by a block of $s-t$ $1$s, in particular

\[
\underbrace{00\ldots0}_{s-t \mbox{ \scriptsize times}} \beta.
\]

Hence $\ell(\PP)$ is given by

\[
\underbrace{00\ldots0}_{s \mbox{ \scriptsize times}} \underbrace{11\ldots1}_{t \mbox{ \scriptsize times}}\beta
\]

This shows that $\SS_2$ satisfies the condition (2).

To prove the converse, assume that $\PP$ satisfies the conditions (1) and (2). We need to show that $\PP$ has the S-property. We proceed by induction on the total number $e\geq 2$ of maximal NE-blocks in $\SS_1$ and $\SS_2$. In other words, we apply the induction on total number of corners in $\SS_1$ and $\SS_2$.

For $e=2$, from the conditions (1) and (2) we get that in $\SS_1$ (resp. $\SS_2$) the maximal NE-block has size $2t$ for some $t \in \NN$. More precisely, $\SS_1$ (resp. $\SS_2$) has a maximal block of $t$ north-steps (resp. east-steps) followed by a block of $t$ east-steps (resp. north-steps). Then the binary representations of $\SS_1$ and $\SS_2$ are

\[
u(\PP): \underbrace{11\ldots1}_{t \mbox{ \scriptsize times}} \underbrace{00\ldots0}_{t \mbox{ \scriptsize times}} \mbox{ and } \ell(\PP): \underbrace{00\ldots0}_{t \mbox{ \scriptsize times}} \underbrace{11\ldots1}_{t \mbox{ \scriptsize times}}
\]

and the polyomino is a square.

Now, let $e\geq 3$ and assume that any parallelogram polyomino having a total number of maximal NE-blocks equal to $e-1$ has the $S$-property. Let $\PP'=\PP \setminus R_0$.  It follows from Lemma <ref> that $\PP'$ is a parallelogram polyomino. Set $\PP'=(\SS_1', \SS_2')$. To prove that $\PP$ has the $S$-property, it is enough to show that $R_0$ has a single square and that $\PP'$ has the $S$-property. In particular, we prove that $\SS_1'$ and $\SS_2'$ satisfy conditions (1) and (2), respectively. Then the conclusion will follow by using inductive hypothesis on $\PP'$ and existence of single square in $R_0$.

If $R_0$ has size $s\times t$ with $t <s$, then $u(\PP)$ begins with a maximal block of $t$ $1$s and by using condition (1), there is a maximal block of $t$ $0s$ following it. Therefore, $u(\PP)$ is of the following form

\[
\underbrace{11\ldots1}_{t \mbox{ \scriptsize times}}\underbrace{00\ldots0}_{t \mbox{ \scriptsize times}}u(\PP').
\]

This shows that $R_0$ has a single square of size $t \times t$ and $\SS'_1$ satisfies the condition (1). Moreover, by using the assumption that $\PP$ satisfies condition (2), we obtain that $\ell(\PP)$ starts with a maximal blocks of $s$ 0s followed by a maximal block of $s$ 1s. We write

\[
\underbrace{00\ldots0}_{s \mbox{ \scriptsize times}} \underbrace{11\ldots1}_{s \mbox{ \scriptsize times}}\beta.
\]

where $\beta$ is binary sequence consistent with condition (2). Then $\ell(\PP')$ takes the following form

\[
\underbrace{00\ldots0}_{s-t \mbox{ \scriptsize times}}\ \ \underbrace{11\ldots1}_{s-t \mbox{ \scriptsize times}}\beta.
\]

which shows that $\PP'$ satisfies the condition (2).  Moreover, the total number of maximal NE-blocks in $\PP'$ is $e-1$ (because one maximal NE-block is at the beginning of $\SS_1$). By using the inductive hypothesis, we conclude that $\PP'$ has the $S$-property. Then, it follows that $\PP$ has the $S$-property as well.

With the help of Theorem <ref>, to be able to describe Motzkin paths associated with Gorenstein parallelogram polyominoes, it is enough to see the impact of condition (1) and (2) of Theorem <ref> on the associated Motzkin paths. Let $\PP=(\SS_1, \SS_2)$ be a Gorenstein parallelogram polyomino with associated Motzkin path $\MM_\PP$. Note that in $\SS_1$, a maximal block of length $k$ of consecutive north steps corresponds to a combination of $k$ rise and $\alpha$-colored horizontal steps in $\MM_\PP$. Indeed, this combination of rise and $\alpha$-colored horizontal steps in $\MM_\PP$ is maximal in a sense that it is followed by either a fall or a $\beta$-colored horizontal step. Similarly, a maximal block of length $k$ of consecutive east steps corresponds to a maximal block of a combination of $k$ fall and $\beta$-colored horizontal steps in $\MM_\PP$. Hence, the condition (1) of Theorem <ref> translates as: in $\MM_\PP$ each maximal block of a combination of $k$ rise and $\alpha$-colored horizontal steps must be followed by a maximal block of a combination of $k$ fall and $\beta$-colored horizontal steps.

To translate condition (2) for $\MM_{\PP}$, we consider the reflection of $M_{\PP}$ through the $x$-axis. We denote this reflection by $\overline{\MM_\PP}$. The reflection $\overline{\MM_\PP}$ corresponds to the coding given in (<ref>) applied to the matrix that contains $\ell(\PP)$ as first row and $u(\PP)$ as the second row. Then the condition (2) of Theorem <ref> translates as: in $\overline{\MM_\PP}$ each maximal block of a combination of $k$ fall and $\beta$-colored horizontal steps must be followed by a maximal block of a combination of $k$ rise and $\alpha$-colored horizontal steps. We formulate this discussion in the following corollary.

Let $\PP=(\SS_1,\SS_2)$ be a parallelogram polyomino with associated Motzkin path $\MM_\PP$. Let $\overline{\MM_\PP}$ be the reflection of $\MM_\PP$ through $x$-axis.  Then $\PP$ is Gorenstein if and only if  the following conditions hold:

* in $\MM_\PP$ each maximal block of a combination of $k$ rise and $\alpha$-colored horizontal steps must be followed by a maximal block of a combination of $k$ fall and $\beta$-colored horizontal steps;

* in $\overline{\MM_\PP}$ each maximal block of a combination of $k$ fall and $\beta$-colored horizontal steps must be followed by a maximal block of a combination of $k$ rise and $\alpha$-colored horizontal steps.

We give an illustration of Corollary <ref> in the following example.

The Figure <ref> shows a Gorenstein parallelogram polyomino. The associated Motzkin path $\MM_\PP$ is shown on the left side and its reflection through $x$-axis is shown on the right side. The Motzkin path $\MM_\PP$ and its reflection satisfy the conditions (1) and (2) of Corollary <ref>.

[dashed] (0,0)–(8,0);
[dashed] (0,1)–(8,1);
[dashed] (0,2)–(8,2);
[dashed] (0,3)–(8,3);
[dashed] (0,4)–(8,4);
[dashed] (0,5)–(8,5);
[dashed] (0,6)–(8,6);

[dashed] (0,0)–(0,6);
[dashed] (1,0)–(1,6);
[dashed] (2,0)–(2,6);
[dashed] (3,0)–(3,6);
[dashed] (4,0)–(4,6);
[dashed] (5,0)–(5,6);
[dashed] (6,0)–(6,6);
[dashed] (7,0)–(7,6);
[dashed] (8,0)–(8,6);

[ultra thick] (0,2)–(1,3)–(2,3);
[ultra thick, densely dashed] (2,3)–(4,3);
[ultra thick] (4,3)–(5,4)–(6,4)–(8,2);

[dashed] (0,0)–(8,0);
[dashed] (0,1)–(8,1);
[dashed] (0,2)–(8,2);
[dashed] (0,3)–(8,3);
[dashed] (0,4)–(8,4);
[dashed] (0,5)–(8,5);
[dashed] (0,6)–(8,6);

[dashed] (0,0)–(0,6);
[dashed] (1,0)–(1,6);
[dashed] (2,0)–(2,6);
[dashed] (3,0)–(3,6);
[dashed] (4,0)–(4,6);
[dashed] (5,0)–(5,6);
[dashed] (6,0)–(6,6);
[dashed] (7,0)–(7,6);
[dashed] (8,0)–(8,6);

[ultra thick] (0,3+1)–(1,2+1)–(2,2+1);
[ultra thick, densely dashed] (2,2+1)–(4,2+1);
[ultra thick] (4,2+1)–(5,1+1)–(6,1+1)–(8,3+1);

A Gorenstein parallelogram polyomino satisfying conditions (1) and (2) of Corollary <ref>

The Figure <ref> shows a non-Gorenstein parallelogram polyomino. The associated Motzkin path $\MM_\PP$ is shown on the left side and its reflection through $x$-axis is shown on the right side. The Motzkin path $\MM_\PP$ fails the condition (1) of Corollary <ref>. However, its reflection satisfies the condition (2) of Corollary <ref>.

[dashed] (0,0)–(6,0);
[dashed] (0,1)–(6,1);
[dashed] (0,2)–(6,2);
[dashed] (0,3)–(6,3);
[dashed] (0,4)–(6,4);
[dashed] (0,5)–(6,5);

[dashed] (0,0)–(0,5);
[dashed] (1,0)–(1,5);
[dashed] (2,0)–(2,5);
[dashed] (3,0)–(3,5);
[dashed] (4,0)–(4,5);
[dashed] (5,0)–(5,5);
[dashed] (6,0)–(6,5);

[ultra thick] (0,2)–(1,3);
[ultra thick, densely dashed] (1,3)–(3,3);
[ultra thick] (3,3)–(5,3)–(6,2);

[dashed] (0,0)–(6,0);
[dashed] (0,1)–(6,1);
[dashed] (0,2)–(6,2);
[dashed] (0,3)–(6,3);
[dashed] (0,4)–(6,4);
[dashed] (0,5)–(6,5);

[dashed] (0,0)–(0,5);
[dashed] (1,0)–(1,5);
[dashed] (2,0)–(2,5);
[dashed] (3,0)–(3,5);
[dashed] (4,0)–(4,5);
[dashed] (5,0)–(5,5);
[dashed] (6,0)–(6,5);

[ultra thick] (0,3)–(1,2);
[ultra thick, densely dashed] (1,2)–(3,2);
[ultra thick] (3,2)–(5,2)–(6,3);

A non-Gorenstein parallelogram polyomino satisfying condition (2) of Corollary <ref>