††thanks: Corresponding author

# Complementarity via error-free measurement in a two-path interferometer

Yanjun Liu  Key Laboratory of Low-Dimensional Quantum Structures and Quantum
Control of Ministry of Education, Department of Physics and Synergetic
Innovation Center of Quantum Effects and Applications, Hunan Normal
University, Changsha 410081, China  Jing Lu  Key Laboratory of Low-Dimensional
Quantum Structures and Quantum Control of Ministry of Education, Department of
Physics and Synergetic Innovation Center of Quantum Effects and Applications,
Hunan Normal University, Changsha 410081, China  Lan Zhou
<EMAIL_ADDRESS>Key Laboratory of Low-Dimensional Quantum Structures and
Quantum Control of Ministry of Education, Department of Physics and Synergetic
Innovation Center of Quantum Effects and Applications, Hunan Normal
University, Changsha 410081, China

###### Abstract

We study both the wave-like behavior and particle-like behavior in a general
Mach-Zehnder interferometer with its asymmetric beam splitter. A error-free
measurement in the detector is used to extract the which-path information. The
fringe visibility V and the which-path information $I_{path}$ are derived:
their complementary relation $V+I_{path}\leq 1$ are found, and the condition
for the equality is also presented.

###### pacs:

03.67.-a, 03.65.Ta, 07.60.Ly

##  I Introduction

The wave-like nature and particle-like nature are two mutual exclusion
properties of quantum systems, and the appearance of these two properties are
determined by the experimental instrument, which is known as Bohr’s
complementarity principle Bohr . The wave-particle duality is the well-known
example used to exhibit the curious nature of the complementarity principle.
In the recoiling-slit gedanken experiment introduced by Einstein and Bohr
where a particle is sent through a movable slit placed before a double slit,
Wootters and Zurek Woo  proposed their quantitative formulation of the wave-
particle duality. In a two-path interferometer, such as Mach-Zehnder
interferometer (MZI) Wolf , a complementarity was first found between a priori
fringe visibility of the interference pattern and the predictability Yasin ,
which were determined by the initial state of the particle. Later on, the
wave-like and particle-like nature were characterized by the visibility of the
interferometer fringe and the path distinguishability Englert , respectively,
and there is a trade-off between these quantities. Both predictability and
distinguishing are quantities that measure the which-path knowledge. Since
there are many ways to define the measure of which-path knowledge, the
complementarity between the fringe visibility and the which-path knowledge has
been studied greatly in theory and experiment Yasin ; Mandel ; Jaeger ; Horne
; Englert ; Rempe ; rrS ; Zawisky ; Kaszlikowski ; Bimonte ; Bramon ; Jakob ;
BanO ; Masashi ; Han ; LiLi ; Fonseca ; Asad ; Angelo .

Form the information theory viewpoint, the achievement of knowledge is an
information transmission process. It is natural to use information measure to
characterize the particle nature of a quantum system in a two-path
interferometer. Here, we employ the mutual information which is called which-
path information (WPI). The information cannot be transmitted until a
measurement is performed, for example, a detector is placed in one path of the
MZI in Ref.Englert , and an error-minimum state distinguishing measurement
Helstrom  is performed on the detector after the particle interacts with the
detector to acquire the path distinguishability. Although such ambiguous
measurement yields a conclusive outcome, there is nonvanishing probability of
making a wrong guess since errors in the conclusive outcome are unavoidable.
The other optimized measure strategies is the error-free discrimination
Chefles  among nonorthogonal states, which allow a nonzero probability of
inconclusive outcomes.

In this paper, we study the trade-off between the fringe visibility and WPI in
a two-path interferometer made of one symmetric beam splitter (BS) and one
asymmetric BS. The error-free measurement is used to obtain the WPI. It is
found that the magnitudes of the fringe visibility and the WPI are effected by
the asymmetric BS and the input state of the particle. A bound between the
fringe visibility and the WPI is also found.

The paper is organized as follows. In Sec. II, we introduce the setup that a
quantum system display its wave-like behavior and particle-like behavior. In
Sec. III, the WPI is defined, and an unambiguous discrimination on the state
of the detector is used to obtain the which-path information. In Sec. IV, we
made our conclusion.

##  II The setups and the state evolution

A general MZI, shown in Fig. 1, consists of two BSs and phase shifters (PSs).
A beam of particles coming from either port a or b is first splitted by beam
splitter BS1 into two beams and then these beams are recombined by BS2. So two
paths a and b are available between BS1 and BS2. A particle taking path a(b)
is denoted by the state $|a\rangle=\hat{a}^{\dagger}|0\rangle$
$(|b\rangle=\hat{b}^{\dagger}|0\rangle)$, where $\hat{a}^{\dagger}$ and
$\hat{b}^{\dagger}$ are the corresponding creation operators in path a and b,
and they satisfy $[\hat{a},\hat{b}]=0$, $[\hat{a},\hat{a}^{\dagger}]=1$,
$[\hat{b},\hat{b}^{\dagger}]=1$. States $|a\rangle$ and $|b\rangle$ support a
two-dimensional $H_{q}$. In this sense, a quantum bit is formed. The state of
particle traveling in this interferometer is characterized by the change of a
Bloch vector in a Bloch sphere. Before the particle incident into the general
MZI, the state of the particle is described by the density matrix

$\rho_{in}^{Q}=\frac{1}{2}(1+S_{x}\sigma_{x}+S_{y}\sigma_{y}+S_{z}\sigma_{z}),$
(1)

where $\sigma_{x},\sigma_{y},\sigma_{z}$ are the Pauli matrix and
$\sigma_{z}=|b\rangle\langle b|-|a\rangle\langle a|$. Here, the initial Bloch
vector
$\overrightarrow{S}=(\overrightarrow{S_{x}},\overrightarrow{S_{y}},\overrightarrow{S_{z}})$.
When $|\overrightarrow{S}|=1$, the particle is in a pure state, when
$|\overrightarrow{S}|<1$ , the particle is in a mixed state.

Figure 1: The schematic sketch of the general Mach-Zehnder interferometer with
the second BS asymmetric, a detector is placed in path a.

The effect of the BS on the state of the incoming particles is described by
the operator
$B(\beta)=\exp[i\beta(\hat{a}^{\dagger}\hat{b}+\hat{b}^{\dagger}\hat{a})]$,
which preserves the total number of particles in this MZI. In the subspace
spanned by basis $\\{|a\rangle,|b\rangle\\}$, the BS performs a rotation
around the y axis by angle $\beta$, which is denoted by

$U_{B}(\beta)=\exp(-i\frac{\beta}{2}\sigma_{y})=(\begin{array}[]{cc}\sqrt{t}&-\sqrt{r}\\\
\sqrt{r}&\sqrt{t}\end{array}).$ (2)

Here, $r$ and $t$ respectively represent the reflection coefficient and
transmission coefficient of the beam splitter.

$r=\sin^{2}{\frac{\beta}{2}},\text{ \ \ \ \ \ \ \ \
}t=\cos^{2}{\frac{\beta}{2}}.$ (3)

The PS in path $d\in\\{a,b\\}$ is described by
$P(\phi_{d})=\exp(i\phi_{d}\hat{d}^{\dagger}\hat{d})$. If the parameters
$\phi_{a}$ and $\phi_{b}$ have the same magnitude but different sign, i.e.,
$\phi_{a}=-\phi_{b}=\phi$, a rotation around the $z$ axis by angle $\phi$ is
realized by PS1 and PS2,

$U_{P}(\phi)=\exp(-i\frac{\phi}{2}\sigma_{z}).$ (4)

To acquire the WPI, a detector is usually placed in one of the paths (e.g. the
a path). As long as the particle go through the general MIZ, a operator

$M=\frac{1+\sigma_{Z}}{2}I+\frac{1+\sigma_{Z}}{2}U,$ (5)

performs on the detector, where U is unitary. The final state of the particle
and the detector reads

$\displaystyle\rho_{f}$ $\displaystyle=$ $\displaystyle
U_{B}(\beta)MU_{P}(\varphi)U_{B}(\frac{\pi}{2})\rho_{in}^{Q}\rho_{in}^{D}U_{B}^{\dagger}(\frac{\pi}{2})U_{P}^{\dagger}(\varphi)M^{\dagger}U_{B}^{\dagger}(\beta)$
(6) $\displaystyle=$
$\displaystyle\frac{1}{4}(1-S_{x})(1+\sigma_{z}\cos\beta+\sigma_{x}\sin\beta)\otimes\rho_{in}^{D}$
$\displaystyle-\frac{1}{4}e^{-i\phi}(S_{z}-iS_{y})(\sigma_{z}\sin\beta-\sigma_{x}\cos\beta-i\sigma_{y})\otimes\rho_{in}^{D}U^{\dagger}$
$\displaystyle-\frac{1}{4}e^{i\phi}(S_{z}+iS_{y})(\sigma_{z}\sin\beta-\sigma_{x}\cos\beta+i\sigma_{y})\otimes
U\rho_{in}^{D}$
$\displaystyle+\frac{1}{4}(1+S_{x})(1-\sigma_{z}\cos\beta-\sigma_{x}\sin\beta)\otimes
U\rho_{in}^{D}U^{\dagger},$

where $\rho_{in}^{D}$ is the initial state of the detector, and the BS1 is
assumed to be symmetric.

The probability that we finding the particle at the output port $a$ reads

$\displaystyle p(\phi)$ $\displaystyle=$ $\displaystyle
tr_{QD}[\frac{1}{2}(1-\sigma_{z})\rho_{f}]$ (7) $\displaystyle=$
$\displaystyle\frac{1}{2}(1+S_{x}\cos\beta)$
$\displaystyle+\frac{1}{2}\sqrt{S_{z}^{2}+S_{y}^{2}}\sin\beta|tr_{D}(U\rho_{in}^{D})|\cos(\alpha+\gamma+\phi),$

where $\alpha$ and $\gamma$ are defined as

$\alpha=\arctan\frac{S_{y}}{S_{z}},\text{ \ \ \ \ \ \
}\gamma=-i\ln\frac{tr_{D}(U\rho_{in}^{D})}{|tr_{D}(U\rho_{in}^{D})|}.$ (8)

The fringe visibility which documents the wave-like property of the particle
is defined via the probability in Eq. (7) as

$\displaystyle V$ $\displaystyle=$
$\displaystyle\frac{maxP(\phi)-minP(\phi)}{maxP(\phi)+minP(\phi)},$ (9)

where the maximum and minimum is achieved by adjusting $\phi$. And one can
easily obtain that

$\displaystyle V$ $\displaystyle=$
$\displaystyle\frac{\sin\beta}{1+S_{x}\cos\beta}\sqrt{S_{z}^{2}+S_{y}^{2}}|tr_{D}(U\rho_{in}^{D})|.$
(10)

We note that the fringe visibility can also be defined by the probability at
the output port $b$. However, the fringe visibility measured in either output
port $a$ or $b$ is different expect the BS2 is symmetric (i.e. $\beta=\pi/2$).

Eq. (10) shows that both the BS2 and the initial state have influence on the
fringe visibility. It can be found that for a given $\beta$, more wave nature
appears when the particle is in a pure state $(|\overrightarrow{S}|=1)$. To
show the dependence of the wave nature of the BS2 and the initial state, we
have plotted the fringe visibility V as a function of the $\beta$ and $S_{x}$
for $|tr_{D}(U\rho_{in}^{D})|=1/3$ and $|\overrightarrow{S}|=1$ in Fig. 2. It
can be observed for a given $S_{x}(\beta)$, the fringe visibility first
increase and then decrease as $\beta(S_{x})$ increases, and the fringe
visibility obtains the maximum $C\equiv|tr_{D}(U\rho_{in}^{D})|$ when
$\cos\beta=-S_{x}$. This is the reason the quantified wave-particle duality in
Englert  is presented by choosing $S_{x}=0$ when $\beta=\pi/2$. The value of
the fringe visibility is zero in the following situation: (1) The effect of
the BS2 for the particle is full transmission or full reflection,
corresponding to $\beta=0$ or $\pi$. (2) The particle travels only in a path
or b path, corresponding to $S_{x}=1$ or $-1$.

Figure 2: (Color online).(a) The fringe visibility as the function of the
$S_{x}$ and $\beta$ with $|tr_{D}(U\rho_{in}^{D})|=1/3$ and
$S_{x}^{2}+S_{y}^{2}+S_{z}^{2}=1$, (b) the cross section of (a) when
$S_{x}=-0.5,0,0.5$, (c) the cross section of (a) when
$\beta=\Pi/4,\Pi/2,3\Pi/4$.

It is well-known that the wave-like property characterized by the fringe
visibility is complementary to the particle-like property which gives rise to
the WPI. A decrease of the fringe visibility predicts an increasing of the
WPI. From Eq. (10), one can find that the BS2 besides the initial state affect
the WPI, which indicates that the asymmetric BS2 introduce additional WPI LiLi
. Then, the set up of measuring the particle-like property is different form
the one which is obtained simply by removing the BS2 in Fig. 1. Actually, the
particle-like property is measured by the setup with four input and output
ports, which is shown in Fig. 3. Since two paths c and d have been introduced,
the initial density matrix for the total system reads

$\displaystyle\rho_{in}^{QD}=\rho_{in}^{Q}\otimes|00\rangle_{cd}\langle
00|\otimes\rho_{in}^{D},$ (11)

where $|00\rangle_{cd}$ is vacuum states of the input ports c and d. Before
the particle meets the BS2 and BS3, the state of the particle and the detector
is the same to the state before the BS2 in Fig. 1. The BS2 acts on the paths a
and c, and BS3 acts on the paths b and d. The performance of BS2 and BS3 is
denoted by
$B_{2}=exp[(-\frac{\beta}{2})(\hat{a}^{\dagger}\hat{c}-\hat{c}^{\dagger}\hat{a})]$
and
$B_{3}=exp[(-\frac{\beta}{2})(\hat{b}^{\dagger}\hat{d}-\hat{d}^{\dagger}\hat{b})]$
respectively. After the particle goes through the BS2 and BS3, the state for
the particle appearing in either output a or d reads

$\displaystyle\rho^{QD}_{f}$ $\displaystyle=$
$\displaystyle\omega_{b}|d\rangle\langle
d|\rho_{in}^{D}+\omega_{a}|a\rangle\langle a|U\rho_{in}^{D}U^{\dagger}$ (12)
$\displaystyle+\frac{\sqrt{rt}}{1+S_{x}(t-r)}e^{i\phi}(S_{z}+iS_{y})|a\rangle\langle
d|U\rho_{in}^{D}$
$\displaystyle+\frac{\sqrt{rt}}{1+S_{x}(t-r)}e^{-i\phi}(S_{z}-iS_{y})|d\rangle\langle
a|\rho_{in}^{D}U^{\dagger}.$

Figure 3: Schematic representation of the setup with four input and output
ports.

Here, the prior probabilities

$\omega_{a}=\frac{t(1+S_{x})}{1+S_{x}(t-r)},\text{ \ \ \ \ \ \
}\omega_{b}=\frac{r(1-S_{x})}{1+S_{x}(t-r)},$ (13)

for finding the particle in output a and d respectively. Since the particle
detected at output port a(d) is obtained by transmission (reflection) from
path a(b), we change the letter d in Eq. (12) by b, which is rewritten as

$\displaystyle\rho^{QD}_{f}$ $\displaystyle=$
$\displaystyle\omega_{b}|b\rangle\langle
b|\rho_{in}^{D}+\omega_{a}|a\rangle\langle a|U\rho_{in}^{D}U^{\dagger}$ (14)
$\displaystyle+\frac{\sqrt{rt}}{1+S_{x}(t-r)}e^{i\phi}(S_{z}+iS_{y})|a\rangle\langle
b|U\rho_{in}^{D}$
$\displaystyle+\frac{\sqrt{rt}}{1+S_{x}(t-r)}e^{-i\phi}(S_{z}-iS_{y})|b\rangle\langle
a|\rho_{in}^{D}U^{\dagger}.$

##  III  Information gain via error-free measurement

After tracing over the degree of the particle in Eq. (14), we obtain the final
state of the detector

$\displaystyle\rho^{D}_{f}=\omega_{b}\rho_{in}^{D}+\omega_{a}\rho_{out}^{D}.$
(15)

To obtain the WPI, we have to discriminate the states $\rho_{in}^{D}$ and
$\rho_{out}^{D}\equiv U\rho_{in}^{D}U^{\dagger}$ with prior probabilities
$\omega_{b}$ and $\omega_{a}$ in an optimal way. Here, we perform the error-
free measurement on the detector. This kind of measurement gives two results:
a conclusive one without any error and an inconclusive one. The conclusive
result means which-path the particle takes is definitely known.
Mathematically, to calculate the WPI, one has to introduce the positive
operator-valued measure (POVM) $\\{{\Pi_{k},k=a,b,0}\\}$ with the resolution
of the identity $\sum_{k}\Pi_{k}=I$, which leads to an inconclusive outcome 0
and two definitely results a and b. The unambiguous discrimination requires

$\rho_{in}^{D}\Pi_{a}=\rho_{out}^{D}\Pi_{b}=0.$ (16)

The joint probability that the particle travels on path $d\in\\{a,b\\}$ and
the which-path result k indicated from the measurement of the detector reads

$\displaystyle Q(\mu,k)$ $\displaystyle=$ $\displaystyle
Tr_{D}\langle\mu|\Pi_{k}\rho_{f}^{QD}|\mu\rangle.$ (17)

Then, the amount of the WPI Thomas  obtained from the error-free measure is
given by

$\displaystyle I_{path}$ $\displaystyle=$
$\displaystyle\underset{\mu=a,b}{\sum}\underset{k=a,b}{\sum}Q(\mu,k)\log[\frac{Q(\mu,k)}{Q(\mu)Q(k)}].$
(18)

For the sake of simplicity, we assume that the detector is initially in a pure
state $\rho_{in}^{D}=|r\rangle\langle r|$. Since the unitary operator U is
arbitrary, states $|r\rangle$ and $|s\rangle\equiv U|r\rangle$ can be assumed
to be linearly independent, the POVM is constructed as

$\displaystyle\Pi_{a}$ $\displaystyle=$
$\displaystyle\alpha|r^{\perp}\rangle\langle r^{\perp}|,$
$\displaystyle\Pi_{b}$ $\displaystyle=$
$\displaystyle\beta|s^{\perp}\rangle\langle s^{\perp}|,$
$\displaystyle\Pi_{0}$ $\displaystyle=$ $\displaystyle(1-\beta
S^{2})|r\rangle\langle r|+\beta SC|r\rangle\langle r^{\perp}|$ (19)
$\displaystyle+\beta SC|r^{\perp}\rangle\langle r|+(1-\beta C^{2}-\alpha)|\
r^{\perp}\rangle\langle r^{\perp}|,$

where states $|r\rangle(|s\rangle)$ are orthogonal to

$\displaystyle|r^{\perp}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{S}(|s\rangle-C|r\rangle),$
$\displaystyle|s^{\perp}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{S}(|r\rangle-C|s\rangle),$ (20)

respectively. Capital letter $S=\sqrt{1-C^{2}}$, and $C=\langle r|s\rangle$,
where the maximum value of the fringe visibility becomes the overlap between
two linearly independent states. In Eq. (19), parameters $\alpha$ and $\beta$
are chosen to minimize the probability of failure

$\displaystyle Q$ $\displaystyle=$
$\displaystyle\omega_{b}Tr(\rho_{in}^{D}{\Pi}_{0})+\omega_{a}Tr(\rho_{out}^{D}{\Pi}_{0}).$
(21)

By the Cauchy inequality and the resolution of the identity, we derive the
lower bound on the probability of failure Feng

$\displaystyle Q$ $\displaystyle\geq$ $\displaystyle
2\sqrt{\omega_{a}\omega_{b}}F(\rho_{in}^{D},\rho_{out}^{D}),$ (22)

where the fidelity Nielsen  is defined as

$F=Tr|\sqrt{\rho_{in}^{D}\rho_{out}^{D}}|=C.$ (23)

The lower bound of the failure probability is achieved if and only if

$\omega_{b}Tr(\rho_{in}^{D}\Pi_{0})=\omega_{a}Tr(\rho_{out}^{D}\Pi_{0})=\sqrt{\omega_{a}\omega_{b}}F(\rho_{in}^{D},\rho_{out}^{D}).$
(24)

Figure 4: (Color online). (a) The WPI as the function of $S_{x}$ and $\beta$
with $C=1/3$, the range with purple, brown, and cyan represent the $I_{path}$
under the conditions $\sqrt{\omega_{a}/\omega_{b}}\in(0,C)$, $(C,C^{-1})$, and
$(C^{-1},+\infty)$, respectively. (b) The cross section of 3D surface for
$S_{x}=-0.5,0,0.5$, (c) the cross section of 3D surface for
$\beta=\pi/4,\pi/2,3\pi/4$. Figure 5: (Color online). (a) The WPI as the
function of $\beta$ and $C$ with $S_{x}=1/2$, the range with purple, brown,
and cyan represent the $I_{path}$ under the conditions
$\sqrt{\omega_{a}/\omega_{b}}\in(0,C)$, $(C,C^{-1})$, and $(C^{-1},+\infty)$,
respectively. (b) The cross section of 3D surface for
$\beta=2\pi/3,3\pi/4,\pi/3$, (c) the cross section of 3D surface for
$C=0.75,0.50,0.25$. Figure 6: (Color online). (a) The WPI as the function of
$S_{x}$ and $C$ with $\beta=\pi/3$, the range with purple, brown, and cyan
represent the $I_{path}$ under the conditions
$\sqrt{\omega_{a}/\omega_{b}}\in(0,C)$, $(C,C^{-1})$, and $(C^{-1},+\infty)$,
respectively. (b) The cross section of 3D surface for $S_{x}=-0.5,0,0.5$, (c)
the cross section of 3D surface for $C=0.75,0.50,0.25$.

The probability of the kth outcome, $tr(\Pi_{k}\rho_{k}^{D})$, is always real
and nonnegative, which requires $0\leq\alpha,\beta\leq 1$. The choice of the
measurement that discriminates $|r\rangle$ and $|s\rangle$ unambiguously
depends on the relation between the ratio $\sqrt{\omega_{a}/\omega_{b}}$ and
the overlap C:

(1) When $\sqrt{\omega_{a}/\omega_{b}}\leq C$, the minimum probability of
failure $Q=\omega_{a}+C^{2}\omega_{b}$ is achieved by selecting the following
measurement operators $\Pi_{a}=0$, $\Pi_{b}=|s^{\perp}\rangle\langle
s^{\perp}|$, $\Pi_{0}=|s\rangle\langle s|$. Here, state $|s\rangle$ is never
detected, and the optimal POVM becomes a von Neumann projective measurement.
Actually, in this case, $\omega_{b}>\omega_{a}$, the state of the detector is
more likely to be in state $\rho_{in}^{D}$, so we make the failure direction
along $\rho_{out}^{D}$ for obtaining the minimum probability of failure. The
joint probability is obtained as

$\displaystyle Q(b,b)$ $\displaystyle=$
$\displaystyle(1-C^{2})\frac{\sin^{2}\frac{\beta}{2}(1-S_{x})}{1+S_{x}\cos\beta},$
(25) $\displaystyle Q(a,b)$ $\displaystyle=$ $\displaystyle 0,$ (26)
$\displaystyle Q(a,0)$ $\displaystyle=$
$\displaystyle\frac{\cos^{2}\frac{\beta}{2}(1+S_{x})}{1+S_{x}\cos\beta},$ (27)
$\displaystyle Q(b,0)$ $\displaystyle=$ $\displaystyle
C^{2}\frac{\sin^{2}\frac{\beta}{2}(1-S_{x})}{1+S_{x}\cos\beta}.$ (28)

Then, the amount of WPI via the von Neumann projective measurement reads

$\displaystyle I_{path}$ $\displaystyle=$
$\displaystyle(1-C^{2})\frac{\sin^{2}\frac{\beta}{2}(1-S_{x})}{1+S_{x}\cos\beta}\log\frac{1+S_{x}\cos\beta}{\sin^{2}\frac{\beta}{2}(1-S_{x})}.$
(29)

(2) When $C\leq\sqrt{\omega_{a}/\omega_{b}}\leq 1/C$, the minimum probability
of failure $Q=2C\sqrt{\omega_{a}\omega_{b}}$ is achieved by choosing the
following measurement operators

$\displaystyle\Pi_{a}$ $\displaystyle=$
$\displaystyle\frac{1}{S^{2}}(1-C\tan\frac{\beta}{2}\sqrt{\frac{1-S_{x}}{1+S_{x}}})|r^{\perp}\rangle\langle
r^{\perp}|,$ (30) $\displaystyle\Pi_{b}$ $\displaystyle=$
$\displaystyle\frac{1}{S^{2}}(1-C\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}})|s^{\perp}\rangle\langle
s^{\perp}|,$ (31) $\displaystyle\Pi_{0}$ $\displaystyle=$ $\displaystyle
C\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}}|r\rangle\langle r|$ (32)
$\displaystyle+\frac{C}{S}(1-C\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}})|r\rangle\langle
r^{\perp}|$
$\displaystyle+\frac{C}{S}(1-C\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}})|r^{\perp}\rangle\langle
r|$
$\displaystyle+[1-\frac{C^{2}}{S^{2}}(1-C\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}})$
$\displaystyle-\frac{1}{S^{2}}(1-C\tan\frac{\beta}{2}\sqrt{\frac{1-S_{x}}{1+S_{x}}})]|r^{\perp}\rangle\langle
r^{\perp}|,$

This measurement is more general than the von Neumann projective measurement.
Via Eq. (17), the joint probability reads

$\displaystyle Q(a,a)$ $\displaystyle=$
$\displaystyle\frac{\cos^{2}\frac{\beta}{2}(1+S_{x})}{1+S_{x}\cos\beta}(1-C\tan\frac{\beta}{2}\sqrt{\frac{1-S_{x}}{1+S_{x}}}),$
(33) $\displaystyle Q(b,b)$ $\displaystyle=$
$\displaystyle\frac{\sin^{2}\frac{\beta}{2}(1-S_{x})}{1+S_{x}\cos\beta}(1-C\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}}),$
(34) $Q(a,b)=Q(b,a)=0,$ (35) $\displaystyle Q(a,0)$ $\displaystyle=$
$\displaystyle
C\frac{\cos^{2}\frac{\beta}{2}(1+S_{x})}{1+S_{x}\cos\beta}\tan\frac{\beta}{2}\sqrt{\frac{1-S_{x}}{1+S_{x}}},$
(36) $\displaystyle Q(b;0)$ $\displaystyle=$ $\displaystyle
C\frac{\sin^{2}\frac{\beta}{2}(1-S_{x})}{1+S_{x}\cos\beta}\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}}.$
(37)

Then the amount of WPI obtained from the POVM measurement is calculated as

$\displaystyle I_{path}$ $\displaystyle=$
$\displaystyle\frac{\cos^{2}\frac{\beta}{2}(1+S_{x})}{1+S_{x}\cos\beta}(1-C\tan\frac{\beta}{2}\sqrt{\frac{1-S_{x}}{1+S_{x}}})$
(38)
$\displaystyle\times\log\frac{1+S_{x}\cos\beta}{\cos^{2}\frac{\beta}{2}(1+S_{x})}$
$\displaystyle+\frac{\sin^{2}\frac{\beta}{2}(1-S_{x})}{1+S_{x}\cos\beta}(1-C\cot\frac{\beta}{2}\sqrt{\frac{1+S_{x}}{1-S_{x}}})$
$\displaystyle\times\log\frac{1+S_{x}\cos\beta}{\sin^{2}\frac{\beta}{2}(1-S_{x})},$

according to its definition given by Eq. (18).

(3) When $\sqrt{\omega_{a}/\omega_{b}}\geq 1/C$, the minimum probability of
failure $Q=\omega_{b}+C^{2}\omega_{a}$ is achieved by selecting the
measurement operators $\Pi_{a}=|r^{\perp}\rangle\langle r^{\perp}|$,
$\Pi_{b}=0$, $\Pi_{0}=|r\rangle\langle r|$. Here, state $|r\rangle$ is never
detected, and the optimal POVM becomes a von Neumann projective measurement.
In this case, $\omega_{a}>\omega_{b}$. The state of the detector is more
likely to be in state $\rho_{out}^{D}$, so the failure direction is chosen
along $\rho_{in}^{D}$ for obtaining the minimum probability of failure. The
joint probability is obtained as

$\displaystyle Q(a,a)$ $\displaystyle=$
$\displaystyle(1-C^{2})\frac{\cos^{2}\frac{\beta}{2}(1+S_{x})}{1+S_{x}\cos\beta},$
(39) $Q(b,a)=0,$ (40) $\displaystyle Q(a,0)$ $\displaystyle=$ $\displaystyle
C^{2}\frac{\cos^{2}\frac{\beta}{2}(1+S_{x})}{1+S_{x}\cos\beta},$ (41)
$\displaystyle Q(b,0)$ $\displaystyle=$
$\displaystyle\frac{\sin^{2}\frac{\beta}{2}(1-S_{x})}{1+S_{x}\cos\beta}.$ (42)

And, the amoumt of WPI is given by

$\displaystyle I_{path}$ $\displaystyle=$
$\displaystyle(1-C^{2})\frac{\cos^{2}\frac{\beta}{2}(1+S_{x})}{1+S_{x}\cos\beta}\log\frac{1+S_{x}\cos\beta}{\cos^{2}\frac{\beta}{2}(1+S_{x})}.$
(43)

Eqs. (29), (38) and (43) show that the WPI is a piecewise function of the
parameters $S_{x}$, $\beta$, and C. Although all the components of the Bloch
vector determines the fringe visibility, only $S_{x}$ occurs in the expression
of the WPI, indicating that $I_{path}$ is independent of the initial state of
the quantum particle. In Fig.4, we plot the WPI as the function of $S_{x}$ and
$\beta$ with the overlap $C=1/3$. The $I_{path}$ under the conditions
$\sqrt{\omega_{a}/\omega_{b}}\in(0,C)$, $(C,C^{-1})$, and $(C^{-1},+\infty)$
is shown in the ranges with purple, brown, and cyan in Fig.4(a), respectively.
The white range in Fig.4(a) indicates that $I_{path}$ is a discontinuous
function of $S_{x}$ and $\beta$. It can be observed from Fig.4 that
$I_{path}\leq 1-C$ for any $S_{x}$ and $\beta$, and the position along the
$S_{x}(\beta)$ axis that $I_{path}=1-C$ occurs varies with different given
$\beta(S_{x})$. In Fig.5(6), we have plotted $I_{path}$ as the function of
parameters $\beta(S_{x})$ and C for a given $S_{x}(\beta)$. One can also find
that $I_{path}$ is less than or equal to $1-C$, $I_{path}$ decrease as C
increase, the position that the peak occurs is fixed for different overlap C,
i.e., the peak appears at $\beta=2\pi/3$ when $S_{x}=1/2$ in Fig.5(c), and
$S_{x}=-1/2$ when $\beta=\pi/3$ in Fig.6(c). From Eq. (38), we find that the
maximum of $I_{path}$ can be achieved once $\cos\beta=-S_{x}$.

The wave-like and the particle-like property are quantitated by fringe
visibility V in Eq. (10) and the WPI $I_{path}$ in Eq. (18). Since $V\leq C$
and $I_{path}\leq 1-C$, we obtain the complementary relation

$\displaystyle V+I_{path}\leq 1,$ (44)

the equal sign holds in Eq. (44) when $\cos\beta=-S_{x}$.

##  IV  conclusion

We have investigated the complementarity of the fringe visibility and the WPI
in a MZI with one asymmetric BS. Although the fringe visibility measured in
either two output ports are different, there exists an upper limit, i.e.
$V\leq C$. The upper bound $C=|tr_{D}(U\rho_{in}^{D})|$ is determined by the
initial state of the detector and the unitary operator performed on the
detector. The maximum value of the fringe visibility C can be achieved when
the quantum system is initially in pure state with $\cos\beta=-S_{x}$. To
observe the particle-like behavior of this quantum system, a four-path
interferometer must be introduced due to the asymmetrical BS2. The WPI is
characterized by the WPI $I_{path}$, which is obtained via the unambiguous
discrimination on the state of the detector. Although $I_{path}$ is dependent
on the asymmetric BS and the initial state of the quantum system, the WPI is
bounded by the following inequality, $I_{path}\leq 1-C$. The maximum
$I_{path}$ is achieved when $\cos\beta=-S_{x}$. It is also found that
$V+I_{path}\leq 1$.

###### Acknowledgements.

This work was supported by NSFC Grants No. 11374095, No. 11422540, No.
11434011, No. 11575058; National Fundamental Research Program of China (the
973 Program) Grant No. 2012CB922103; Hunan Provincial Natural Science
Foundation of China Grants No. 11JJ7001.

## References

  * (1) N. Bohr, Naturwiss. 16, 245 (1928); Nature (London) 121, 580 (1928).
  * (2) W. K. Wootters and W. H. Zurek, Phys. Rev. D 19,473 (1979).
  * (3) Mandel, L.; Wolf, E. Optical Coherence and Quantum Optics;Cambridge University Press: Cambridge (1995).
  * (4) D.M. Greenberger and A. Yasin, Phys. Lett. A 128, 391 (1988).
  * (5) B.-G. Englert, Phys. Rev. Lett. 77, 2154 (1996).
  * (6) L. Mandel, Opt. Lett. 16, 1882 (1991).
  * (7) Jaeger, G.; Horne, M.A.; Shimony, A. Phys. Rev. A 48: 1023-1027 (1993).
  * (8) G. Jaeger, A. Shimony, and L. Vaidman, Phys. Rev. A 51, 54 (1995).
  * (9) S. D$\ddot{u}$rr, T. Nonn, and G. Rempe Phys. Rev. Lett. 81, 5705 (1998).
  * (10) D$\ddot{u}$rr, S. Phys. Rev. A 64: 042113-1-9 (2001).
  * (11) M. Zawisky, M. Baron, and R. Loidl Phys. Rev. A 66, 063608 (2002).
  * (12) Kaszlikowski, D.; Kwek, L.C.; Zukowski, M.; Englert, B. Phys. Rev. Lett. 91: 037901-1-4 (2003).
  * (13) G. Bimonte and R. Musto Phys. Rev. A 67, 066101 (2003).
  * (14) A. Bramon, G. Garbarino, and B. C. Hiesmayr Phys. Rev. A 69, 022112 (2004).
  * (15) Jakob, M.; Bergou, J. Phys. Rev. A 76: 052107-1-15 (2007).
  * (16) Ban, M. J. Mod. Opt. 55, 21, 3625-3639 (2008).
  * (17) Masashi Bana, Fumiaki Shibataa and Sachiko Kitajimaa, Journal of Modern Optics 56, 89 (2009).
  * (18) Han Yang, Wu Chun-Wang, Wu Wei, Chen Ping-Xing, and Li Cheng-Zu Chinese Phys. Lett. 26 040303 (2009).
  * (19) Li Li, Nai-Le Liu, and Sixia Yu, Phys. Rev. A 85, 054101 (2012).
  * (20) K. M. Fonseca-Romero, J. G. G. de Oliveira, J. G. Peixoto de Faria, and M. C. Nemes Phys. Rev. A 90 062102 (2014).
  * (21) Mohd Asad Siddiqui and Tabish Qureshi Prog. Theor. Exp. Phys. 2015 083A02 (2015).
  * (22) Angelo, R.M. and Ribeiro, A.D. Found Phys 45: 1407 (2015).
  * (23) Helstrom, C.W. Quantum Detection and Estimation Theory; Academic Press: New York (1976).
  * (24) Chefles, A. Contemporary Physics. 41: 401-424 (2000).
  * (25) Cover, T.M.; Thomas, J.A. Elements of Information Theory; Wiley: New York (1991).
  * (26) Yuan Feng, Runyao Duan, and Mingsheng Ying, Phys. Rev. A 70, 012308 (2004).
  * (27) M. A. Nielsen and I. L. Chuang, Quantum Computation and Information (Cambridge University Press, Cambridge, UK, 2000).


# NON-SIMPLE POLYOMINOES OF KÖNIG TYPE

RODICA DINU  University of Konstanz, Fachbereich Mathematik und Statistik,
Fach D 197 D-78457 Konstanz, Germany, and Institute of Mathematics Simion
Stoilow of the Romanian Academy, Calea Grivitei 21, 010702, Bucharest, Romania
<EMAIL_ADDRESS>and  FRANCESCO NAVARRA  Universitá di Messina,
Dipartimento di Scienze Matematiche e Informatiche, Scienze Fisiche e Scienze
della Terra
Viale Ferdinando Stagno D’Alcontres 31
98166 Messina, Italy<EMAIL_ADDRESS>
###### Abstract.

We study the König type property for non-simple polyominoes. We prove that,
for closed path polyominoes, the polyomino ideals are of König type, extending
the results of Herzog and Hibi for simple thin polyominoes.

###### Key words and phrases:

Polyominoes, binomial ideals, Krull dimension, König type.

###### 2010 Mathematics Subject Classification:

05B50, 05E40, 13C05, 13G05

##  1\. Introduction

Polyominoes are plane figures obtained by joining unitary squares along their
edges. They raise many combinatorial problems, for instance, tiling a certain
region or the plane with polyominoes and related problems 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 defined by Golomb first in 1953 and later, in 1996,
in his monograph [14].
The study of polyominoes reveals many connections to different subjects. For
instance, in algebraic languages: there seems to be a nice relation between
polyominoes and Dyck words and Motzkin words [10], 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 [32].
A classic topic in commutative algebra is the study of determinantal ideals.
These are the ideals generated by the $t$-minors of any matrix, and a special
attention received the case of the minors of a generic matrix, whose entries
are indeterminates, see for instance [2] and [30]. More generally, ideals of
$t$-minors of 2-sided ladders were studied, see [7], [8], [9], [15]. When
considering the case of 2-minors, these classes of ideals are special cases of
the ideal $I_{\mathcal{P}}$ of inner 2-minors of a polyomino $\mathcal{P}$ in
the polynomial ring over a field $K$ in the variables $x_{v}$ where $v$ is a
vertex of $\mathcal{P}$. This type of ideal, called polyomino ideal, was
introduced in 2012 by Qureshi [24]. Since then, the study of the main
algebraic properties of the polyomino ideal and of its quotient ring
$K[\mathcal{P}]=S/I_{\mathcal{P}}$ in terms of the shape of $\mathcal{P}$ has
become an exciting area of research. For instance, several mathematicians have
studied the primality of $I_{\mathcal{P}}$, see [3], [4], [5], [19], [20],
[22], [23], [28]. Moreover,in [18] and [26], the authors showed that
$K[\mathcal{P}]$ is a normal Cohen-Macaulay domain if $\mathcal{P}$ is a
simple polyomino, i.e. a polyomino without holes; a precise definition will be
given in Section 2. See also the references [11], [12], [13], [21], [27].
Not many properties are known for non-simple polyominoes. However, the reader
may consult [28] and [29], and, for the special class of closed path
polyominoes, there are several interesting results that can be found in [3],
[5] and [6]. In the paper [17], the authors introduced graded ideals of König
type with respect to a monomial order $<$, i.e ideals $I$ for which there
exists a sequence of the height of $I$ homogeneous polynomials forming part of
a minimal system of generators of the ideal such that, there exists 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 the paper [16],
Herzog and Hibi showed that if $\mathcal{P}$ is a simple thin polyomino, then
its polyomino ideal has the König type property.
We are interested in understanding the König type property for non-simple
polyominoes, following the path initiated by Herzog and Hibi. We will focus on
a specific class of non-simple thin polyominoes, namely closed path
polyominoes.
Not all the polyominoes have their ideals of König type and there is no known
classification of the polyominoes which have this property. In particular, a
class of polyominoes for which this property does not hold is given by the
parallelogram polyominoes. Indeed, this follows by [25, Proposition 2.3],
where the authors showed that parallelogram polyominoes are simple planar
distributive lattices, and by using the classification of distributive
lattices of König type provided in [16, Theorem 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 $\mathcal{P}$ is a closed path polyomino, then its number of vertices
is twice the number of its cells, fact that will be useful in the next
sections.
In order to study closed path polyominoes of König type, a combinatorial
formula to compute height $I_{\mathcal{P}}$ is needed. Section 3 is devoted to
this scope. In Theorem 3.3, we give a combinatorial formula for the Krull
dimension of $K[\mathcal{P}]$, and we prove it by using the theory of
simplicial complexes. Essential here is the fact that, by [3, Section 6],
$\mathcal{P}$ contains some specific configurations that will be analyzed in
our proof. As a consequence, in Corollary 3.4, we prove that the height of
$I_{\mathcal{P}}$ is the number of cells of the closed path polyomino. We
conjecture that this formula holds for any non-simple polyomino.
The last section, Section 4, is devoted to the proof of the König type
property of $I_{\mathcal{P}}$ for any closed path polyomino, see Theorem 4.7.
In Definition 4.2, we define a suitable order on the vertices of the closed
path polyomino $\mathcal{P}$ with respect to whom the desired property holds.
There are two cases to be examined: either $\mathcal{P}$ contains a
configuration of four cells (treated in Proposition 4.3) or $\mathcal{P}$ has
an $L$-configuration in every change of direction (treated in Proposition
4.5). Moreover, we present concrete examples to illustrate our procedures.

##  2\. Polyominoes and polyomino ideals

Let $(i,j),(k,l)\in\mathbb{Z}^{2}$. We say that $(i,j)\leq(k,l)$ if $i\leq k$
and $j\leq l$. Consider $a=(i,j)$ and $b=(k,l)$ in $\mathbb{Z}^{2}$ with
$a\leq b$. The set $[a,b]=\\{(m,n)\in\mathbb{Z}^{2}:i\leq m\leq k,\ j\leq
n\leq l\\}$ is called an interval of $\mathbb{Z}^{2}$. Moreover, if $i<k$ and
$j<l$, then $[a,b]$ is a proper interval. In this case, we say $a$ and $b$ are
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 $a$ and $b$ are in
horizontal (or vertical) position. We denote by $]a,b[$ the set
$\\{(m,n)\in\mathbb{Z}^{2}:i<m<k,\ j<n<l\\}$. A proper interval $C=[a,b]$ with
$b=a+(1,1)$ is called a cell of ${\mathbb{Z}}^{2}$; moreover, the elements
$a$, $b$, $c$ and $d$ are called respectively the lower left, upper right,
upper left and lower right corners of $C$. The set of vertices of $C$ is
$V(C)=\\{a,b,c,d\\}$ and the set of edges of $C$ is
$E(C)=\\{\\{a,c\\},\\{c,b\\},\\{b,d\\},\\{a,d\\}\\}$. Let $\mathcal{S}$ be a
non-empty collection of cells in $\mathbb{Z}^{2}$. Then
$V(\mathcal{S})=\bigcup_{C\in\mathcal{S}}V(C)$ and
$E(\mathcal{S})=\bigcup_{C\in\mathcal{S}}E(C)$, while the rank of
$\mathcal{S}$ is the number of cells belonging to $\mathcal{S}$. If $C$ and
$D$ are two distinct cells of $\mathcal{S}$, then a walk from $C$ to $D$ in
$\mathcal{S}$ is a sequence $\mathcal{C}:C=C_{1},\dots,C_{m}=D$ of cells of
${\mathbb{Z}}^{2}$ such that $C_{i}\cap C_{i+1}$ is an edge of $C_{i}$ and
$C_{i+1}$ for $i=1,\dots,m-1$. Moreover, if $C_{i}\neq C_{j}$ for all $i\neq
j$, then $\mathcal{C}$ is called a path from $C$ to $D$. Moreover, if we
denote by $(a_{i},b_{i})$ the lower left corner of $C_{i}$ for all
$i=1,\dots,m$, then $\mathcal{C}$ has a change of direction at $C_{k}$ for
some $2\leq k\leq m-1$ if $a_{k-1}\neq a_{k+1}$ and $b_{k-1}\neq b_{k+1}$. In
addition, a path can change direction in one of the following ways:

  1. (1)

North, if $(a_{i+1}-a_{i},b_{i+1}-b_{i})=(0,1)$ for some $i=1,\dots,m-1$;

  2. (2)

South, if $(a_{i+1}-a_{i},b_{i+1}-b_{i})=(0,-1)$ for some $i=1,\dots,m-1$;

  3. (3)

East, if $(a_{i+1}-a_{i},b_{i+1}-b_{i})=(1,0)$ for some $i=1,\dots,m-1$;

  4. (4)

West, if $(a_{i+1}-a_{i},b_{i+1}-b_{i})=(-1,0)$ for some $i=1,\dots,m-1$.

We say that $C$ and $D$ are connected in $\mathcal{S}$ if there exists a path
of cells in $\mathcal{S}$ from $C$ to $D$. A polyomino $\mathcal{P}$ is a non-
empty, finite collection of cells in $\mathbb{Z}^{2}$ where any two cells of
$\mathcal{P}$ are connected in $\mathcal{P}$. For instance, see Figure 1.

Figure 1. A polyomino.

Let $\mathcal{P}$ be a polyomino. A sub-polyomino of $\mathcal{P}$ is a
polyomino whose cells belong to $\mathcal{P}$. We say that $\mathcal{P}$ is
simple if for any two cells $C$ and $D$ not in $\mathcal{P}$ there exists a
path of cells not in $\mathcal{P}$ from $C$ to $D$. A finite collection of
cells $\mathcal{H}$ not in $\mathcal{P}$ is a hole of $\mathcal{P}$ if any two
cells of $\mathcal{H}$ are connected in $\mathcal{H}$ and $\mathcal{H}$ is
maximal with respect to set inclusion. For example, the polyomino in Figure 1
is not simple. Obviously, each hole of $\mathcal{P}$ is a simple polyomino,
and $\mathcal{P}$ is simple if and only if it has no hole. A polyomino is said
to be thin if it does not contain the square tetromino. The rank of a
polyomino, $\mathop{\rm rank}\nolimits(\mathcal{P})$, is given by the number
of its cells. Consider two cells $A$ and $B$ of $\mathbb{Z}^{2}$ with
$a=(i,j)$ and $b=(k,l)$ as the lower left corners of $A$ and $B$ with $a\leq
b$. A cell interval $[A,B]$ is the set of the cells of $\mathbb{Z}^{2}$ with
lower left corner $(r,s)$ such that $i\leqslant r\leqslant k$ and $j\leqslant
s\leqslant l$. If $(i,j)$ and $(k,l)$ are in horizontal (or vertical)
position, we say that the cells $A$ and $B$ are in horizontal (or vertical)
position.
Let $\mathcal{P}$ be a polyomino. Consider two cells $A$ and $B$ of
$\mathcal{P}$ in vertical or horizontal position. The cell interval $[A,B]$,
containing $n>1$ cells, is called a block of $\mathcal{P}$ of rank n if all
cells of $[A,B]$ belong to $\mathcal{P}$. The cells $A$ and $B$ are called
extremal cells of $[A,B]$. Moreover, a block $\mathcal{B}$ of $\mathcal{P}$ is
maximal if there does not exist any block of $\mathcal{P}$ which contains
properly $\mathcal{B}$. It is clear that an interval of ${\mathbb{Z}}^{2}$
identifies a cell interval of ${\mathbb{Z}}^{2}$ and vice versa, hence we can
associate to an interval $I$ of ${\mathbb{Z}}^{2}$ the corresponding cell
interval denoted by $\mathcal{P}_{I}$. A proper interval $[a,b]$ is called an
inner interval of $\mathcal{P}$ if all cells of $\mathcal{P}_{[a,b]}$ belong
to $\mathcal{P}$. We denote by $\mathcal{I}(\mathcal{P})$ the set of all inner
intervals of $\mathcal{P}$. An interval $[a,b]$ with $a=(i,j)$, $b=(k,j)$ and
$i<k$ is called a horizontal edge interval of $\mathcal{P}$ if the sets
$\\{(\ell,j),(\ell+1,j)\\}$ are edges of cells of $\mathcal{P}$ for all
$\ell=i,\dots,k-1$. In addition, if $\\{(i-1,j),(i,j)\\}$ and
$\\{(k,j),(k+1,j)\\}$ do not belong to $E(\mathcal{P})$, then $[a,b]$ is
called a maximal horizontal edge interval of $\mathcal{P}$. We define
similarly a vertical edge interval and a maximal vertical edge interval.
We follow [22] and we call a zig-zag walk of $\mathcal{P}$ a sequence
$\mathcal{W}:I_{1},\dots,I_{\ell}$ of distinct inner intervals of
$\mathcal{P}$ where, for all $i=1,\dots,\ell$, the interval $I_{i}$ has either
diagonal corners $v_{i}$, $z_{i}$ and anti-diagonal corners $u_{i}$,
$v_{i+1}$, or anti-diagonal corners $v_{i}$, $z_{i}$ and diagonal corners
$u_{i}$, $v_{i+1}$, such that:

  1. (1)

$I_{1}\cap I_{\ell}=\\{v_{1}=v_{\ell+1}\\}$ and $I_{i}\cap
I_{i+1}=\\{v_{i+1}\\}$, for all $i=1,\dots,\ell-1$;

  2. (2)

$v_{i}$ and $v_{i+1}$ are on the same edge interval of $\mathcal{P}$, for all
$i=1,\dots,\ell$;

  3. (3)

for all $i,j\in\\{1,\dots,\ell\\}$ with $i\neq j$, there exists no inner
interval $J$ of $\mathcal{P}$ such that $z_{i}$, $z_{j}$ belong to $J$.

According to [3], we recall the definition of a closed path polyomino, and the
configuration of cells characterizing its primality. We say that a polyomino
$\mathcal{P}$ is a closed path if there exists a sequence of cells
$A_{1},\dots,A_{n},A_{n+1}$, $n>5$, such that:

  1. (1)

$A_{1}=A_{n+1}$;

  2. (2)

$A_{i}\cap A_{i+1}$ is a common edge, for all $i=1,\dots,n$;

  3. (3)

$A_{i}\neq A_{j}$, for all $i\neq j$ and $i,j\in\\{1,\dots,n\\}$;

  4. (4)

For all $i\in\\{1,\dots,n\\}$ and for all $j\notin\\{i-2,i-1,i,i+1,i+2\\}$, we
have $V(A_{i})\cap V(A_{j})=\emptyset$, where $A_{-1}=A_{n-1}$, $A_{0}=A_{n}$,
$A_{n+1}=A_{1}$ and $A_{n+2}=A_{2}$.

(a)

(b)

Figure 2. An example of two closed paths.

A path of five cells $C_{1},C_{2},C_{3},C_{4},C_{5}$ of $\mathcal{P}$ is
called an L-configuration if the two sequences $C_{1},C_{2},C_{3}$ and
$C_{3},C_{4},C_{5}$ go in two orthogonal directions. A set
$\mathcal{B}=\\{\mathcal{B}_{i}\\}_{i=1,\dots,n}$ of maximal horizontal (or
vertical) blocks of rank at least two, with $V(\mathcal{B}_{i})\cap
V(\mathcal{B}_{i+1})=\\{a_{i},b_{i}\\}$ and $a_{i}\neq b_{i}$ for all
$i=1,\dots,n-1$, is called a ladder of $n$ steps if $[a_{i},b_{i}]$ is not on
the same edge interval of $[a_{i+1},b_{i+1}]$ for all $i=1,\dots,n-2$. We
recall that a closed path has no zig-zag walks if and only if it contains an
L-configuration or a ladder of at least three steps (see [3, Section 6]). For
instance, in Figure 2 they are displayed a prime closed path on the left and
an other one with zig-zag walks on the right.

######  Lemma 2.1.

Let $\mathcal{P}$ be a closed path polyomino. Then
$|V(\mathcal{P})|=2\mathop{\rm rank}\nolimits(\mathcal{P})$.

###### Proof.

Consider the sub-polyominoes of $\mathcal{P}$ arranged in Figure 3.

(a)

(b)

(c)

(d)

Figure 3.

In (A) and (B), we attached to the cell $A_{i}$ the red vertices. In (C), we
attached to $A_{i-1}$, $A_{i}$ and $A_{i+1}$ respectively the blue vertices,
the black ones and the red ones. In (D), we attached to $A_{i-1}$ and $A_{i}$
respectively the blue vertices and the black ones. It easy to see that a
closed path is made up of suitable arrangements of the sub-polyominoes in
Figure 3 and of their rotations or reflections. Once we label the cells of
$\mathcal{P}$, we can attach to every cell two distinct vertices as before.
Therefore, we obtain that $|V(\mathcal{P})|=2\mathop{\rm
rank}\nolimits(\mathcal{P})$.

∎

Let $\mathcal{P}$ be a polyomino. We set $S_{\mathcal{P}}=K[x_{v}\colon\;v\in
V(\mathcal{P})]$, where $K$ is a field. If $[a,b]$ is an inner interval of
$\mathcal{P}$, with $a$,$b$ and $c$,$d$ respectively diagonal and anti-
diagonal corners, then the binomial $x_{a}x_{b}-x_{c}x_{d}$ is called an inner
2-minor of $\mathcal{P}$. We define $I_{\mathcal{P}}$ as the ideal in
$S_{\mathcal{P}}$ generated by all the inner 2-minors of $\mathcal{P}$ and we
call it the polyomino ideal of $\mathcal{P}$. We set also
$K[\mathcal{P}]=S_{\mathcal{P}}/I_{\mathcal{P}}$, which is the coordinate ring
of $\mathcal{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 finite simplicial complex $\Delta$ on the vertex set
$[n]=\\{1,\dots,n\\}$ is a collection of subsets of $[n]$ satisfying the
following two conditions:

  1. (1)

if $F^{\prime}\in\Delta$ and $F\subseteq F^{\prime}$ then $F\in\Delta$;

  2. (2)

$\\{i\\}\in\Delta$ for all $i=1,\dots,n$.

The elements of $\Delta$ are called faces, and the dimension of a face is one
less than its cardinality. An edge of $\Delta$ is a face of dimension 1, while
a vertex of $\Delta$ is a face of dimension 0. The maximal faces of $\Delta$
with respect to the set inclusion are called facets. The dimension of $\Delta$
is the dimension of a facet. Let $\Delta$ be a simplicial complex on $[n]$ and
$R=K[x_{1},\dots,x_{n}]$ be the polynomial ring in $n$ variables over a field
$K$. To every collection $F=\\{i_{1},\dots,i_{r}\\}$ of $r$ distinct vertices
of $\Delta$, we associate a monomial $x^{F}$ in $R$ where
$x^{F}=x_{i_{1}}\dots x_{i_{r}}.$ The monomial ideal generated by all
monomials $x^{F}$ such that $F$ is not a face of $\Delta$ is called Stanley-
Reisner ideal and it denoted by $I_{\Delta}$. The face ring of $\Delta$,
denoted by $K[\Delta]$, is defined to be the quotient ring $R/I_{\Delta}$.
From [31, Corollary 6.3.5], if $\Delta$ is a simplicial complex on $[n]$ of
dimension $d$, then $\dim K[\Delta]=d+1=\max\\{s\colon\;x_{i_{1}}\dots
x_{i_{s}}\notin I_{\Delta},i_{1}<\dots<i_{s}\\}$.

######  Definition 3.1.

A polyomino $\mathcal{R}$ is called $\Gamma$-path with middle cell $D$ and
hooking vertex $w$ if it consists of an horizontal maximal block
$\mathcal{B}_{1}=[C_{1},B_{1}]$ of rank greater than three, a vertical maximal
block $\mathcal{B}_{2}=[B_{2},C_{2}]$ of rank greater than three and a cell
$D$ not belonging to $\mathcal{B}_{1}\cup\mathcal{B}_{2}$, with
$V(\mathcal{B}_{1})\cap V(\mathcal{B}_{2})=\\{w\\}$ where $w$ is the upper
left corner of $D$. This is illustrated in Figure 4 (A). With reference to
Figure 4, we define $\tau$-paths, $W$-paths and $\zeta$-paths in a similar
way.

(a) $\Gamma$-path

(b) $\tau$-path

(c) $W$-path

(d) $\zeta$-path

Figure 4.

Moreover, we say that a pair $(\mathcal{F},\mathcal{G})$ of the previous
polyominoes is compatible if $\mathcal{F}$ is a $\Gamma$-path ($\tau$-path or
$W$-path or $\zeta$-path) and $\mathcal{G}$ is one of the other paths.

######  Definition 3.2.

A polyomino $\mathcal{S}$ is called LU-skew path with hooking vertices $a,b$
if it is made up of two maximal blocks $\mathcal{B}_{1}=[C_{1},D_{1}]$ and
$\mathcal{B}_{2}=[C_{2},D_{2}]$, both of them having rank greater than three,
with $V(\mathcal{B}_{1})\cap V(\mathcal{B}_{2})=\\{a,b\\}$ where $a,b$ are the
right and, respectively, left upper corners of $D_{1}$. For instance, see
Figure 5 (A). With reference to Figure 5, we can define $LD$-skew, $DU$-skew
and $UD$-skew paths in a similar way.

(a) $LU$-skew

(b) $LD$-skew

(c) $DU$-skew

(d) $UD$-skew

Figure 5.

Let $\mathcal{P}$ be a closed path and $(\mathcal{F},\mathcal{G})$ be a pair
of two sub-polyominoes of $\mathcal{P}$ as in Definition 3.1. Without loss of
generality, we may assume that the middle cell of $\mathcal{F}$ and of
$\mathcal{G}$ are $A_{1}$ and, respectively, $A_{k}$ with $k\in[n-1]$. Then a
sub-polyomino $\mathcal{Q}$ of $\mathcal{P}$ as in Definition 3.2 is said to
be between $\mathcal{F}$ and $\mathcal{G}$ if $\mathcal{Q}$ is contained in
$\\{A_{i}:1<i<k\\}$.

######  Theorem 3.3.

Let $\mathcal{P}$ be a closed path. Then the Krull dimension of
$K[\mathcal{P}]$ is $|V(\mathcal{P})|-\mathop{\rm
rank}\nolimits(\mathcal{P})$.

###### Proof.

We recall from [6] that, if $\mathcal{P}$ does not contain any zig-zag walk,
then $K[\mathcal{P}]$ is a normal Cohen-Macaulay domain and the Krull
dimension is given by $|V(\mathcal{P})|-\mathop{\rm
rank}\nolimits(\mathcal{P})$. We need to examine only the case when
$\mathcal{P}$ contains a zig-zag walk. Suppose that we are in this case.
Let $<^{1}$ be the total order on $V(\mathcal{P})$ defined as $u<^{1}v$ if and
only if, for $u=(i,j)$ and $v=(k,l)$, $i<k$, or $i=k$ and $j<l$. Let $Y\subset
V(\mathcal{P})$ and consider $<^{Y}_{\mathrm{lex}}$ be the lexicographical
order in $S_{\mathcal{P}}$ induced by the following order on the variables of
$S_{\mathcal{P}}$:

$\mbox{for}\ u,v\in V(\mathcal{P})\qquad
x_{u}<^{Y}_{\mathrm{lex}}x_{v}\Leftrightarrow\left\\{\begin{array}[]{l}u\notin
Y\ \mbox{and}\ v\in Y\\\ u,v\notin Y\ \mbox{and}\ u<^{1}v\\\ u,v\in Y\
\mbox{and}\ u<^{1}v\end{array}\right.$

From [5, Theorem 4.9], we know that there exists a suitable set $Y\subset
V(\mathcal{P})$ such that the set of generators of $I_{\mathcal{P}}$ forms the
reduced Gröbner basis of $I_{\mathcal{P}}$ with respect to
$<^{Y}_{\mathrm{lex}}$, defined in [5, Algorithm 4.7, Definition 4.8]. The
square-free monomial ideal
$J=\mathrm{in}_{<^{Y}_{\mathrm{lex}}}(I_{\mathcal{P}})$ can be viewed as the
Stanley-Reisner ideal of a simplicial complex $\Delta(J)$. In order to
determine the dimension of $K[\mathcal{P}]$, we compute the dimension of the
simplicial complex $\Delta(J)$, which is the cardinality of a facet of
$\Delta(J)$ minus 1. Hence, in what follows, our aim to define a suitable
facet of $\Delta(J)$.
From [3, Section 6], it follows easily that $\mathcal{P}$ contains just the
configurations defined in Definitions 3.1 and 3.2, arranged in a suitable way.
Let $\mathcal{S}_{1}$ be a $\Gamma$-path. Referring to Figure 4 (A), we label
the cells of $\mathcal{P}$ setting $D=A_{1}$, $C_{1}=A_{2}$ and so on. Let
$k>1$ be the minimum integer such that $\mathcal{S}_{2}$ is either a $W$-path
or a $\tau$-path with middle cell $A_{k}$. The hooking vertices of
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are on the same maximal horizontal
edge interval $V$ of $\mathcal{P}$ and, if there exist, the hooking vertices
of the $LU$-skew or $LD$-skew paths between $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$ belong to $V$. Moreover, by the minimality of $k$, there
does not exist any $DU$-skew and $UD$-skew path between $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$ belonging to $V$. We want to define a suitable set of
vertices of $\mathcal{P}$ in order to find a facet of $\Delta(J)$. We
distinguish two cases, depending if $\mathcal{S}_{2}$ is a $W$-path or a
$\tau$-path. Moreover, we have $z_{T},x_{T}\in Y$ and $y_{T}\notin Y$, with
reference to Figure 6.
Case I: Assume that $\mathcal{S}_{2}$ is a $W$-path.

  1. (1)

Suppose that there does not exist any $LU$-skew or $LD$-skew paths between
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$. Let $\mathcal{B}_{1}$ be the maximal
horizontal block $[A_{2},A_{k-1}]$. Denote the upper right corner of $A_{i}$
by $a_{i}^{1}$ for all $i=2,\dots,k-1$ and the upper left corner of $A_{2}$ by
$a_{1}^{1}$. We set

$V(\mathcal{S}_{1},\mathcal{S}_{2})=\\{a_{i}^{1}:i\in[\mathop{\rm
rank}\nolimits(\mathcal{B}_{1})]\\},$

as in Figure 6.

Figure 6.

  2. (2)

Suppose that there exist $LD$-skew or $LU$-skew paths between
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ and, in particular, that there are $m$
maximal horizontal blocks $\mathcal{B}_{i}$ between $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$. Set $\mathcal{B}_{j}=[A_{k_{j}},A_{k_{j+1}}]$, where
$k_{1}=2$ and $k_{j}<k_{j+1}$ for all $j\in[m]$. For all $j\in[m]$ odd and for
all $i=1,\dots,\mathop{\rm rank}\nolimits(\mathcal{B}_{j})$, we denote by
$a_{1}^{j}$ the upper left corner of $A_{k_{j}}$ and by $a_{i}^{j}$ the right
upper corner of $A_{k_{j}+i}$ in $\mathcal{B}_{j}$. For all $j\in[m]$ even and
for all $i=1,\dots,\mathop{\rm rank}\nolimits(\mathcal{B}_{j})$, we denote by
$a_{i}^{j}$ the lower right corner of $A_{k_{j}+i}$ in $\mathcal{B}_{j}$. See
Figure 7.

Figure 7.

Recall that for all $j\in[m]$,
$a^{j}_{|\mathcal{B}_{j}|-2},a^{j}_{|\mathcal{B}_{j}|-1}\notin Y$ and
$a^{j+1}_{1},a^{j+1}_{2}\in Y$ with $a^{j+1}_{2}>a^{j+1}_{1}$. Then we set

$V(\mathcal{S}_{1},\mathcal{S}_{2})=\bigcup_{j\in[m]\atop
even}\\{a_{i}^{j}:i\in[\mathop{\rm
rank}\nolimits(\mathcal{B}_{j})]\\}\cup\biggl{(}\bigcup_{j\in[m]\atop
odd}\\{a_{i}^{j}:i\in[\mathop{\rm
rank}\nolimits(\mathcal{B}_{j})+1]\\}\biggr{)}\backslash\bigcup_{j\in[m]\atop
odd}\\{a_{2}^{j}\\}.$

Case II: Assume that $\mathcal{S}_{2}$ is a $\tau$-path.

  1. (1)

Suppose that there exists just an $LD$-skew path between $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$. For all $i=0,\dots,\mathop{\rm
rank}\nolimits(\mathcal{B}_{1})-1$, we denote by $a_{1}^{1}$ the upper left
corner of $A_{2}$ and by $a_{i}^{1}$ the right upper corner of $A_{k_{j}+i}$
in $\mathcal{B}_{j}$. For all $i=1,\dots,\mathop{\rm
rank}\nolimits(\mathcal{B}_{2})-1$, we denote by $a_{i}^{2}$ the lower right
corner of $A_{t+i}$ in $\mathcal{B}_{2}$. See Figure 8. In this case, we set

$V(\mathcal{S}_{1},\mathcal{S}_{2})=\\{a_{i}^{1}:i\in[\mathop{\rm
rank}\nolimits(\mathcal{B}_{1})]\\}\cup\\{a_{i}^{2}:i\in[\mathop{\rm
rank}\nolimits(\mathcal{B}_{2})]\\}.$

Figure 8.

  2. (2)

Suppose that there exist $LD$-skew or $LU$-skew paths between
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$. With the same notations as in (2) of
Case I (see Figure 9), we set

$V(\mathcal{S}_{1},\mathcal{S}_{2})=\bigcup_{j\in[m]\atop
even}\\{a_{i}^{j}:i\in[\mathop{\rm
rank}\nolimits(\mathcal{B}_{j})]\\}\cup\biggl{(}\bigcup_{j\in[m]\atop
odd}\\{a_{i}^{j}:i\in[\mathop{\rm
rank}\nolimits(\mathcal{B}_{j})]\\}\biggr{)}\backslash\bigcup_{j\in[m]\atop
odd}\\{a_{2}^{j}\\}.$

Figure 9.

In each case, we can define the following bijective correspondence
$\phi_{1,2}:V(\mathcal{S}_{1},\mathcal{S}_{2})\rightarrow\\{A_{1}\\}\cup\bigcup_{i=1}^{m}\mathcal{B}_{i}$
with $\phi_{1,2}(a_{1}^{1})=A_{1}$ and $\phi_{1,2}(a_{i}^{j})=A_{k_{j}+i}$ all
$j\in[m]$ and for all $i\in[\mathop{\rm rank}\nolimits(\mathcal{B}_{j})]$; in
particular, $|V(\mathcal{S}_{1},\mathcal{S}_{2})|=\sum_{i=1}^{m}\mathop{\rm
rank}\nolimits(\mathcal{B}_{i})+1$. Once we have defined the set
$V(\mathcal{S}_{1},\mathcal{S}_{2})$, we can use the same arguments for all
pairs $(\mathcal{S}_{i},\mathcal{S}_{i+i})$ of compatible paths, where
$\mathcal{S}_{i+1}$ is taken by minimality with respect $\mathcal{S}_{i}$, as
done for $(\mathcal{S}_{1},\mathcal{S}_{2})$. Assume that there exist $t$ such
pairs, where $\mathcal{S}_{t+1}=\mathcal{S}_{1}$. So as done before, for all
$i\in[t]$, we can define $V(\mathcal{S}_{i},\mathcal{S}_{i+1})$ by similar
arguments as for $V(\mathcal{S}_{1},\mathcal{S}_{2})$. Hence,
$V=\cup_{i=1}^{t}V(\mathcal{S}_{i},\mathcal{S}_{i+1})$. Observe that
$|V|=\mathop{\rm rank}\nolimits(\mathcal{P})$. We want to prove that
$F=\\{x_{v}:v\in V\\}$ is a facet of $\Delta(J)$. Obviously $F$ is a face of
$\Delta(J)$, so we need to prove the maximality with respect to the set
inclusion. Suppose, by contradiction, that $F$ is not maximal. Then there
exists a $p\in V(\mathcal{P})\backslash V$ such that $F\subset
F\cup\\{x_{p}\\}$. Without loss of generality, we may assume that $p$ is a
vertex of the sub-polyomino $\\{A_{1}\\}\cup\bigcup_{i=1}^{m}\mathcal{B}_{i}$
between $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$.

  1. (1)

Assume that we are in $(1)$ of Case I. Suppose $p\in V(\mathcal{B}_{1})$. If
$p$ is the lower left corner of $A_{2}$ then $x_{p}x_{q}\in J$, where $q$ is
the lower left corner of $A_{n}$ belongs to $J$, since $y_{T}\notin Y$, as a
consequence $\\{x_{q},x_{v}\\}\notin\Delta(J)$; but $x_{q}\in F$, so
$\\{x_{q},x_{v}\\}\in\Delta(J)$, which is a contradiction; in the other cases
we obtain similarly a contradiction considering $\\{x_{a_{1}^{1}},x_{p}\\}$,
as well as when $p$ is the lower left or right corner of $A_{1}$.

  2. (2)

Assume that we are in $(2)$ of Case I. The only case which we discuss is when
$p=a_{2}^{j+1}$ for some $j\in[m]$. In this case, since
$a_{2}^{j+1}>a_{1}^{j+1}$ we have
$x_{a^{j}_{|\mathcal{B}_{j}|-1}}x_{a_{2}^{j+1}}\in J$. But
$\\{x_{a^{j}_{|\mathcal{B}_{j}|-1}},x_{a_{2}^{j+1}}\\}\in\Delta(J)$ since
$p=a_{2}^{j+1}$, so we get a contradiction.

  3. (3)

In the subcases $(1)$ and $(2)$ of Case II, we can argue in a similar way, and
we obtain a contradiction.

Therefore, $F$ is a facet of $\Delta$. Hence, $\dim\Delta(J)=\mathop{\rm
rank}\nolimits(\mathcal{P})-1$, so $\dim K[\mathcal{P}]=\mathop{\rm
rank}\nolimits(\mathcal{P})$. From Lemma 2.1, we obtain that $\dim
K[\mathcal{P}]=|V(\mathcal{P})|-\mathop{\rm rank}\nolimits(\mathcal{P})$.

∎

######  Corollary 3.4.

Let $\mathcal{P}$ be a closed path polyomino. Then
$\mathrm{ht}(I_{\mathcal{P}})=\mathop{\rm rank}\nolimits(\mathcal{P})$.

###### Proof.

It follows from Theorem 3.3 and [31, Corollary 3.1.7]. ∎

It is known that if $\mathcal{P}$ is a simple polyomino, then
$\dim(K[\mathcal{P}])=|V(\mathcal{P})|-\mathop{\rm
rank}\nolimits(\mathcal{P})$, so $\mathrm{ht}(I_{\mathcal{P}})=\mathop{\rm
rank}\nolimits(\mathcal{P})$. Arises naturally the following conjecture.

######  Conjecture 3.5.

Let $\mathcal{P}$ be a non-simple polyomino. Then
$\mathrm{ht}(I_{\mathcal{P}})=\mathop{\rm rank}\nolimits(\mathcal{P})$.

##  4\. Closed paths and König type property

Let $R=K[x_{1},\dots,x_{n}]$ and $I$ be a graded ideal in $R$ of height $h$.
In according to [17], we say that $I$ is of König type if the following two
conditions hold:

  1. (1)

there exists a sequence $f_{1},\dots,f_{h}$ of homogeneous polynomials forming
part of a minimal system of homogeneous generators of $I$;

  2. (2)

there exists a monomial order $<$ on $R$ such that $\mathop{\rm
in}\nolimits_{<}(f_{1}),\dots,\mathop{\rm in}\nolimits_{<}(f_{h})$ is a
regular sequence.

If $\mathcal{P}$ is a polyomino and $I_{\mathcal{P}}$ is its polyomino ideal,
then we say that $\mathcal{P}$ is of König type if $I_{\mathcal{P}}$ is an
ideal of König type. In [16] it is proved that all simple thin polyominoes are
of König type. Obviously, a closed path is a thin and non-simple polyomino.
The aim of this paper is to show that also this class of polyominoes satisfies
this property, as well as it seems that it is true for all non-simple thin
polyominoes.

######  Remark 4.1.

Let $\mathcal{P}$ be a closed path polyomino having $n$ distinct cells. Let
$<_{\mathrm{lex}}$ be the lexicographic order induced by a total order on
$\\{x_{v}:v\in V(\mathcal{P})\\}$. Suppose that there exist $n$ generators
$f_{1},\dots,f_{n}$ of $I_{\mathcal{P}}$ whose initial terms have not any
variable in common. Then $I_{\mathcal{P}}$ is of König type. In fact, from
Corollary 3.4, we know that $\mathrm{ht}(\mathcal{P})=n$. Moreover,
$\gcd(\mathop{\rm in}\nolimits_{<_{\mathrm{lex}}}(f_{i}),\mathop{\rm
in}\nolimits_{<_{\mathrm{lex}}}(f_{j}))=1$ for all $i\neq j$, so $\mathop{\rm
in}\nolimits_{<_{\mathrm{lex}}}(f_{1}),\dots,\mathop{\rm
in}\nolimits_{<_{\mathrm{lex}}}(f_{n})$ forms a regular sequence. Therefore we
have the desired conclusion.

######  Definition 4.2.

Let $\mathcal{P}:A_{1},\dots,A_{n}$ be a closed path polyomino. In order to
define a suitable total order on $\\{x_{v}:v\in V(\mathcal{P})\\}$, Table 1
will be very useful. Let $Y^{(1)}\subset V(\mathcal{P})$. Let $j\geq 2$ and
assume that $Y^{(j-1)}$ is known. We want to define $Y^{(j)}$. We refer to
Table 1 up to suitable rotations and reflections of $\mathcal{P}$. If it
occurs one of the configurations in the left column of Table 1, where the blue
vertices are in $Y^{(j-1)}$, then we denote by $k$ the maximum integer such
that $m+k$ is an orange vertex in the picture displayed in the corresponding
right column. Hence, we set $Z^{(j)}_{1}=\\{x_{m},\dots,x_{m+k}\\}$ and
$Z^{(j)}_{2}=\\{x_{m^{\prime}},\dots,x_{(m+k)^{\prime}}\\}$, where for all
$a\in Y^{(j-1)}_{1}$ we put $x_{a}>x_{h_{1}}>x_{h_{2}}>x_{1^{\prime}}$ with
$m<h_{1}<h_{2}\leq m+k$ and for all $b\in Y^{(j-1)}_{2}$ we put
$x_{b}>x_{t_{1}}>x_{t_{2}}$ with $m^{\prime}<t_{1}<t_{2}\leq(m+k)^{\prime}$.
Therefore, we define $Y^{(j)}=Y^{(j)}_{1}\sqcup Y^{(j)}_{2}$ where
$Y^{(j)}_{1}=Y^{(j-1)}_{1}\sqcup Z^{(j)}_{1}$ and
$Y^{(j)}_{2}=Y^{(j-1)}_{2}\sqcup Z^{(j)}_{2}$.

|  IF it occurs … |  THEN we refer to …
---|---|---
I |  |
II |  |
III |  |
IV |  |
V |  |
VI |  |
VII |  |
VIII |  |
IX |  |
X |  |
Table 1.

We need to distinguish just two cases depending on the changes of direction in
$\mathcal{P}$, so we have the following two results.

######  Proposition 4.3.

Let $\mathcal{P}:A_{1},\dots,A_{n}$ be a closed path polyomino. Suppose that
$\mathcal{P}$ contains a configuration of four cells as in Figure 10 (A), up
to reflections or rotations of $\mathcal{P}$ or up to relabelling of the cells
of $\mathcal{P}$. Then $I_{\mathcal{P}}$ is of König type.

###### Proof.

We distinguish two cases depending on the position of $A_{3}$ with respect to
$A_{2}$.
Case I: We assume that $A_{3}$ is at North of $A_{2}$.

(a)

(b)

(c)

Figure 10.

We set $Y^{(1)}=Y^{(1)}_{1}\sqcup Y^{(1)}_{2}$ where
$Y^{(1)}_{1}=\\{x_{1},x_{2}\\}$ and
$Y^{(1)}_{2}=\\{x_{1^{\prime}},x_{2^{\prime}}\\}$ with
$x_{1}>x_{2}>x_{1^{\prime}}>x_{2^{\prime}}$, with reference to Figure 10 (B)
if $A_{4}$ is at East of $A_{3}$ or to Figure 10 (C) if $A_{4}$ is at North of
$A_{3}$. Starting with this position for $Y^{(1)}$, we apply the procedure
described in Definition 4.2.

Since $\mathcal{P}$ has a finite number of cells and stopping it in the
configuration $\\{A_{n-1},A_{n},A_{1},A_{2}\\}$, the previous procedure
consists of a finite number of steps, let us say $p$ steps. In particular, in
Figure 11, we summarize all cases which may appear in the last step, where the
blue vertices represent the points which are in $Y^{(p-1)}$ in the penultimate
step. Let $Y=Y^{(p)}$ be the order set of variables obtained by using the
previous arguments and let $|Y|=2r$ with $r\in{\mathbb{N}}$. We have
$x_{1}>x_{2}>\dots>x_{r}>x_{1^{\prime}}>x_{2^{\prime}}>\dots>x_{r^{\prime}}$
and we set $Y_{1}=\\{x_{1},x_{2},\dots,x_{r}\\}$ and
$Y_{2}=\\{x_{1^{\prime}},x_{2^{\prime}},\dots,x_{r^{\prime}}\\}$. Moreover,
observe that all vertices of $\mathcal{P}$ are covered two by two, so $r=n$ by
Lemma 2.1. Hence, we obtain $n$ generators of $I_{\mathcal{P}}$ whose initial
terms do not have any variables in common, hence, by Remark 4.1, it follows
that $I_{\mathcal{P}}$ is of König type.

(a) Note $a\in Y_{2}$

(b) Note $a\in Y_{2}$

(c) Note $b\in Y_{2}$

Figure 11. The cases in the last step.

Case II: We assume that $A_{3}$ is at East of $A_{2}$. We set
$Y^{(1)}=Y^{(1)}_{1}\sqcup Y^{(1)}_{2}$ where $Y^{(1)}_{1}=\\{x_{1}\\}$ and
$Y^{(1)}_{2}=\\{x_{1^{\prime}}\\}$ with $x_{1}>x_{1^{\prime}}$, with reference
to Figure 12 (A). As done before, we start with this position for $Y^{(1)}$
and we apply the procedure described in Definition 4.2. Let $q$ be the number
of the steps until $\\{A_{n-1},A_{n},A_{1},A_{2}\\}$. In Figure 11 (A), (B)
and (C) we show all cases in the last step and we point out that we set
$x_{0}>x_{1}$. Hence, with the same arguments as before we get the desired
conclusion.

(a)

(b)

(c) Note $a\in Y_{2}$

(d) Note $b\in Y_{2}$

Figure 12.

∎

######  Example 4.4.

An example of the procedure described in Lemma 4.3 can be seen in Figure 13.
In particular, $\mathcal{P}$ is of König type with respect to the
lexicographic order induced by

$x_{1}>x_{2}>\dots>x_{30}>x_{1^{\prime}}>x_{2^{\prime}}>\dots>x_{30^{\prime}}$

and to the thirty generators of $I_{\mathcal{P}}$ corresponding to the inner
intervals having $i$ and $i^{\prime}$ as diagonal or anti-diagonal corners,
for all $i\in[30]$.

Figure 13.

We describe the algorithm given in Proposition 4.3 and we show how it works
step by step, with reference to Figure 13.
I step) Starting from the tetromino $\\{A_{1},A_{2},A_{3},A_{4}\\}$, observe
that $A_{4}$ is at East of $A_{3}$ so we are in the case of Figure 10 (B).
Hence we set $Y^{(1)}=Y^{(1)}_{1}\sqcup Y^{(1)}_{2}$ with
$Y^{(1)}_{1}=\\{x_{1},x_{2}\\}$ and
$Y^{(1)}_{2}=\\{x_{1^{\prime}},x_{2^{\prime}}\\}$, where
$x_{1}>x_{2}>x_{1^{\prime}}>x_{2^{\prime}}$.
II step) Consider now the tetromino $\\{A_{3},A_{4},A_{5},A_{6}\\}$, so it
occurs the case (V) of Table 1. Hence we set $Y^{(2)}=Y^{(2)}_{1}\sqcup
Y^{(2)}_{2}$ with $Y^{(2)}_{1}=Y^{(1)}_{1}\sqcup Z^{(2)}_{1}$ where
$Z^{(2)}_{1}=\\{x_{3},x_{4}\\}$ and $Y^{(2)}_{2}=Y^{(1)}_{2}\sqcup
Z^{(2)}_{2}$ where $Z^{(2)}_{2}=\\{x_{3^{\prime}},x_{4^{\prime}}\\}$, where
$x_{1}>x_{2}>x_{3}>x_{4}>x_{1^{\prime}}>x_{2^{\prime}}>x_{3^{\prime}}>x_{4^{\prime}}$.
III step) Focusing on $\\{A_{5},A_{6},A_{7},A_{8}\\}$, we are in the case
(III) of Table 1 after suitable rotations of $\mathcal{P}$. Hence
$Z^{(3)}_{1}=\\{x_{5},x_{6}\\}$ and
$Z^{(2)}_{2}=\\{x_{5^{\prime}},x_{6^{\prime}}\\}$, where
$x_{1}>\dots>x_{4}>x_{5}>x_{6}>x_{1^{\prime}}>\dots>x_{4^{\prime}}>x_{5^{\prime}}>x_{6^{\prime}}$.
III step) Take the trimino $\\{A_{8},A_{9},A_{10}\\}$, so we have the case (I)
of Table 1 after a reflection of $\mathcal{P}$ with respect to $y$-axis. Hence
$Z^{(5)}_{1}=\\{x_{8}\\}$ and $Z^{(2)}_{2}=\\{x_{8^{\prime}}\\}$, with
$x_{1}>\dots>x_{7}>x_{8}>x_{1^{\prime}}>\dots>x_{7^{\prime}}>x_{8^{\prime}}$.
V-IX steps) We can argue as done in the previous step so we obtain
$x_{1}>\dots>x_{11}>x_{12}>x_{1^{\prime}}>\dots>x_{11^{\prime}}>x_{12^{\prime}}$.
From this point, it should be clear to the reader how we continue.
X step) Consider $\\{A_{13},A_{14},A_{15},A_{16}\\}$, so we are in the case
(III) of Table 1 after suitable rotations of $\mathcal{P}$. Hence
$Z^{(10)}_{1}=\\{x_{13},x_{14}\\}$ and
$Z^{(10)}_{2}=\\{x_{13^{\prime}},x_{14^{\prime}}\\}$.
XI step) Let $\\{A_{14},A_{15},A_{16},A_{17}\\}$, so we are in the case (VIII)
of Table 1 after suitable rotations of $\mathcal{P}$. Hence
$Z^{(11)}_{1}=\\{x_{15}\\}$ and $Z^{(11)}_{2}=\\{x_{15^{\prime}}\\}$.
XII step) Considering $\\{A_{16},A_{17},A_{18},A_{19}\\}$, we get the case
(IV) of Table 1 up to rotations of $\mathcal{P}$. Hence
$Z^{(12)}_{1}=\\{x_{16},x_{17}\\}$ and
$Z^{(12)}_{2}=\\{x_{16^{\prime}},x_{17^{\prime}}\\}$.
XIII step) Get the trimino $\\{A_{18},A_{19},A_{20}\\}$, so we are in the case
(II) of Table 1 after suitable rotation of $\mathcal{P}$. Hence
$Z^{(13)}_{1}=\\{x_{18}\\}$ and $Z^{(13)}_{2}=\\{x_{18^{\prime}}\\}$.
XIV step) Take $\\{A_{19},A_{20},A_{21},A_{22}\\}$, so we have the case (III)
of Table 1 after a suitable rotation of $\mathcal{P}$. Hence
$Z^{(14)}_{1}=\\{x_{19},x_{20}\\}$ and
$Z^{(14)}_{2}=\\{x_{19^{\prime}},x_{20^{\prime}}\\}$.
XV step) Focus on the tetromino $\\{A_{20},A_{21},A_{22},A_{23}\\}$, so we get
the case (VIII) of Table 1 after a suitable rotation of $\mathcal{P}$. Hence
$Z^{(15)}_{1}=\\{x_{21}\\}$ and $Z^{(15)}_{2}=\\{x_{21^{\prime}}\\}$.
XVI step) Considering the trimino $\\{A_{22},A_{23},A_{24}\\}$, we are in the
case (II) of Table 1 and $Z^{(16)}_{1}=\\{x_{22}\\}$ and
$Z^{(16)}_{2}=\\{x_{22^{\prime}}\\}$.
XVII step) Get $\\{A_{23},A_{24},A_{25},A_{26}\\}$, so we are in the case
(III) of Table 1. Hence $Z^{(17)}_{1}=\\{x_{23},x_{24}\\}$ and
$Z^{(17)}_{2}=\\{x_{23^{\prime}},x_{24^{\prime}}\\}$.
XVIII step) Consider $\\{A_{24},A_{25},A_{26},A_{27}\\}$, we are in the case
(VII) of Table 1. Therefore $Z^{(18)}_{1}=\\{x_{25}\\}$ and
$Z^{(18)}_{2}=\\{x_{25^{\prime}}\\}$.
XIX step) Take $\\{A_{26},A_{27},A_{28},A_{29}\\}$, we are in the case (III)
of Table 1, after a reflection with respect to $x$-axis. Hence
$Z^{(19)}_{1}=\\{x_{26},x_{27}\\}$ and
$Z^{(19)}_{2}=\\{x_{26^{\prime}},x_{27^{\prime}}\\}$.
XX step) Consider $\\{A_{27},A_{28},A_{29},A_{30}\\}$, so we get the case
(VII) of Table 1, after a reflection with respect to $x$-axis. Hence
$Z^{(20)}_{1}=\\{x_{28}\\}$ and $Z^{(20)}_{2}=\\{x_{28^{\prime}}\\}$.
Last step) Consider $\\{A_{29},A_{30},A_{1},A_{2}\\}$, so we are in the case
of Figure 11 (B), or equivalently of (III) in Table 1. Hence
$Z^{(21)}_{1}=\\{x_{29},x_{30}\\}$ and
$Z^{(21)}_{2}=\\{x_{29^{\prime}},x_{30^{\prime}}\\}$.
In conclusion, we obtain the order set of variables as

$x_{1}>x_{2}>\dots>x_{30}>x_{1^{\prime}}>x_{2^{\prime}}>\dots>x_{30^{\prime}}.$

######  Proposition 4.5.

Let $\mathcal{P}:A_{1},\dots,A_{n}$ be a closed path polyomino. Suppose that
$\mathcal{P}$ has an $L$-configuration in every change of direction. Consider
such an $L$-configuration as in Figure 14 (A), up to relabelling of the cells
of $\mathcal{P}$. Then $I_{\mathcal{P}}$ is of König type.

###### Proof.

We distinguish three cases depending on the position of $A_{4}$ with respect
to $A_{3}$. First of all, we assume that $A_{4}$ is at North of $A_{3}$. We
set $Y^{(1)}=Y^{(1)}_{1}\sqcup Y^{(1)}_{2}$ where
$Y^{(1)}_{1}=\\{x_{1},x_{2}\\}$ and
$Y^{(1)}_{2}=\\{x_{1^{\prime}},x_{2^{\prime}}\\}$ with
$x_{1}>x_{2}>x_{1^{\prime}}>x_{2^{\prime}}$, with reference to Figure 14 (A).
The procedure described in Definition 4.2 finishes with one of the two cases
displayed in Figure 14 (B) and (C). As done in Proposition 4.3 the desired
conclusion follows.

(a)

(b) Note $a\in Y_{2}$

(c) Note $b\in Y_{2}$

Figure 14.

We assume that $A_{4}$ is at South of $A_{3}$. In such a case we set
$Y^{(1)}=Y^{(1)}_{1}\sqcup Y^{(1)}_{2}$ where $Y^{(1)}_{1}=\\{x_{1}\\}$ and
$Y^{(1)}_{2}=\\{x_{1^{\prime}}\\}$ with $x_{1}>x_{1^{\prime}}$, with reference
to Figure 15 (A). Observe that the only two last cases are in Figure 15 (B)
and (C).

(a)

(b) Note $a\in Y_{2}$

(c) Note $b\in Y_{2}$

Figure 15.

We assume that $A_{4}$ is at East of $A_{3}$. In such a case we set
$Y^{(1)}=Y^{(1)}_{1}\sqcup Y^{(1)}_{2}$ where $Y^{(1)}_{1}=\\{x_{3}\\}$ and
$Y^{(1)}_{2}=\\{x_{3^{\prime}}\\}$ with $x_{3}>x_{3^{\prime}}$, with reference
to Figure 16 (A). Observe that the only two last cases are in Figure 16 (B)
and (C), where we set:

$x_{1}>x_{2}>x_{3}\dots>x_{r}>x_{1^{\prime}}>x_{2^{\prime}}>x_{3^{\prime}}\dots>x_{r^{\prime}}.$

The conclusion follows arguing as before.

(a)

(b)

(c)

Figure 16.

∎

######  Example 4.6.

In Figure 17 we show two examples of the procedure described in Proposition
4.3. In particular, $\mathcal{P}_{1}$ is of König type with respect the
lexicographic order induced by

$x_{1}>x_{2}>\dots>x_{26}>x_{1^{\prime}}>x_{2^{\prime}}>\dots>x_{26^{\prime}}$

and to the sixty generators of $I_{\mathcal{P}_{1}}$ corresponding to the
inner intervals having $i$ and $i^{\prime}$ as diagonal or anti-diagonal
corners, for all $i\in[26]$; as well as for the polyomino $\mathcal{P}_{2}$
similarly.

(a) Closed path $\mathcal{P}_{1}$

(b) Closed path $\mathcal{P}_{2}$

Figure 17.

######  Theorem 4.7.

Let $\mathcal{P}$ be a closed path polyomino. Then $I_{\mathcal{P}}$ is of
König type.

###### Proof.

If $\mathcal{P}$ contains a configuration of four cells as in Figure 10 (A),
then $I_{\mathcal{P}}$ is of König type by Proposition 4.3. If $\mathcal{P}$
does not contain any such configuration, then it is easy to see that
$\mathcal{P}$ has an $L$-configuration in every change of direction, so
$I_{\mathcal{P}}$ is of König type by Proposition 4.5. Hence, the desired
claim is proved. ∎

######  Conjecture 4.8.

Let $\mathcal{P}$ be a non-simple thin polyomino. Then $I_{\mathcal{P}}$ is of
König type.

## Acknowledgement

RD was supported by the Alexander von Humboldt Foundation and a grant of the
Ministry of Research, Innovation and Digitization, CNCS - UEFISCDI, project
number PN-III-P1-1.1-TE-2021-1633, within PNCDI III.

## References

  * [1]
  * [2] W. Bruns, J. Herzog, Cohen–Macaulay rings, Cambridge University Press, London, Cambridge, New York, 1993.
  * [3] C. Cisto, F. Navarra, Primality of closed path polyominoes, Journal of Algebra and its Applications, 2021.
  * [4] C. Cisto, F. Navarra, R. Utano, Primality of weakly connected collections of cells and weakly closed path polyominoes, Illinois Math. Journal, 1-19, 2022.
  * [5] C. Cisto, F. Navarra, R. Utano, On Gröbner bases and Cohen-Macaulay property of closed path polyominoes, The Electronic Journal of Combinatorics, 29, 3, 2022.
  * [6] C. Cisto, F. Navarra, R. Utano, Hilbert-Poincaré series and Gorenstein property for closed path polyominoes, arXiv:2205.08375, preprint.
  * [7] A. Conca, Ladder determinantal rings, J. Pure and Appl. Alg., 98, 119–134, 1995.
  * [8] A. Conca, Gorenstein ladder determinantal rings, J. London Math. Soc., 54, 453–474, 1996.
  * [9] A. Conca, J. Herzog, Ladder determinantal rings have rational singularities, Adv. Math., 132, 120–147, 1997.
  * [10] M. P. Delest, G. Viennot, Algebraic languages and polyominoes enumeration, Theoretical Computer Science, 34(1-2), 169–206, 1994.
  * [11] V. Ene, J. Herzog, T. Hibi, Linearly related polyominoes, Journal of Algebraic Combinatorics, 41(4), 2015.
  * [12] V. Ene, J. Herzog, A. A. Qureshi, F. Romeo, Regularity and Gorenstein property of the L-convex polyominoes, The Electronic Journal of Combinatorics, 28(1), P1.50, 2021.
  * [13] V. Ene, A. A. Qureshi, Ideals generated by diagonal 2-minors, Comm. in Alg., 41(8), 2013.
  * [14] S. W. Golomb, Polyominoes, puzzles, patterns, problems, and packagings, Second edition, Princeton University Press, 1994.
  * [15] E. Gorla, Mixed ladder determinantal varieties from two-sided ladders, J.Pure and Appl. Alg., 211(2), 433–444, 2007.
  * [16] J. Herzog, T. Hibi, Finite distributive lattices, polyominoes and ideals of König type, arXiv:2202.09643, preprint.
  * [17] J. Herzog, T. Hibi and S. Moradi, Graded ideals of König type, Trans. Amer. Math. Soc. 375, 301–323, 2022.
  * [18] J. Herzog, S. S. Madani, The coordinate ring of a simple polyomino, Illinois J. Math., 58, 981–995, 2014.
  * [19] J. Herzog, A. A. Qureshi, A. Shikama, Gröbner basis of balanced polyominoes, Math. Nachr., 288(7), 775–783, 2015.
  * [20] T. Hibi, A. A. Qureshi, Nonsimple polyominoes and prime ideals, Illinois J. Math., 59, 391–398, 2015.
  * [21] M. Kummini, D. Veer, The $h$-polynomial and the rook polynomial of some polyominoes, arXiv:2110.14905, preprint.
  * [22] C. Mascia, G. Rinaldo, F. Romeo, Primality of multiply connected polyominoes, Illinois J. Math., 64(3), 291–304, 2020.
  * [23] C. Mascia, G. Rinaldo, F. Romeo, Primality of polyomino ideals by quadratic Gröbner basis, Mathematische Nachrichten 295(3), 593–606, 2022.
  * [24] A. A. Qureshi, Ideals generated by 2-minors, collections of cells and stack polyominoes, J. Algebra 357, 279–303, 2012.
  * [25] A. A. Qureshi, G. Rinaldo, F. Romeo, Hilbert series of parallelogram polyominoes, Res. Math. Sci. 9(28), 2022.
  * [26] A. A. Qureshi, T. Shibuta, A. Shikama, Simple polyominoes are prime, J. Commut. Algebra, 9(3), 413–422, 2017.
  * [27] G. Rinaldo, and F. Romeo, Hilbert Series of simple thin polyominoes, J. Algebr. Comb. 54, 607–624, 2021.
  * [28] A. Shikama, Toric representation of algebras defined by certain nonsimple polyominoes, J. Commut. Algebra, 10, 265–274, 2018.
  * [29] A. Shikama, Toric rings of nonsimple polyominoes, International Journal of Algebra, 9(4), 195–201, 2015.
  * [30] B. Sturmfels, Gröbner bases and Stanley decompositions of determinantal rings, Math. Z., 205, 137–144, 1990.
  * [31] R. H. Villarreal, Monomial algebras, Second edition, Monograph and Research notes in Mathematics, CRC press, 2015.
  * [32] S.G. Whittington, C. E. Soteros, Lattice animals: rigorous results and wild guesses, Disorder in Physical Systems, 323—335, 1990.