For a poset \(P = C_a \times C_b\), a subset \(A \subseteq P\) is called a chain blocker for \(P\) if \(A\) is inclusion-wise minimal with the property that every maximal chain in \(P\) contains at least one element of \(A\), where \(C_i\) is the chain \(1 < \cdots < i\). In this article, we define the shelter of the poset \(P\) to give a complete description of all chain blockers of \(C_5 \times C_b\) for \(b \geq 1\).
Let \(P = C_a \times C_b\) be a
poset where \(C_i\) is the chain \(1 < \cdots < i\). A chain blocker of
\(P\) is defined as a subset \(B\subseteq P\) such that every maximal
chain in \(P\) contains at least one
element of \(B\) and \(B\) is inclusion wise minimal with this
property. Initial concept of a chain blocker came from its algebraic
properties. Let \(S=k[x_1,\ldots,x_n]\)
be the polynomial ring over a field \(k\) and in \(n\) variables. A monomial ideal in \(S\) is an ideal generated by only
monomials. A monomial ideal \(I\subset
S\) is called a squarefree monomial ideal if it is generated by
squarefree monomials. An ideal \(J\) is
called primary if \(u_1u_2\in J\)
implies either \(u_1 \in J\) or \(u_2^l \in J\) for some \(l>0\). A primary decomposition of an
ideal \(I\) is an expression of \(I\) as a finite intersection of primary
ideals [1-3].
To each poset \(P\) of cardinality
\(n\) we associate an ideal \(I_P\subset S=k[x_1,\ldots,x_n]\) in the
following way.
We take the Hasse diagram of \(P\)
as a directed graph \(G=(V,E)\). In
[4], Conca and Negri
defined path ideals \(I_G\) of \(G\) as a monomial ideal generated by all
paths of length \(t\) in \(G\), i.e. \(I_G=\langle x_{i_1}\cdots x_{i_t}: x_{i_1},\ldots,
x_{i_t}\rangle\) is a path of length \(t\) in \(G>\subseteq k[x_1,\ldots,x_n]\). The
path ideals associated to Hasse diagram of a poset have also been
studied in [5]. In our
case \(n=ab\) and we denote this ideal
by \(I_P\) such that the generators of
\(I_P\) correspond to the maximal
chains in \(P\). The chain blockers of
\(P\) have one to one correspondence
with the irreducible primary components of \(I_P\) (Proposition 9).
In [6] chain
blockers of \(C_a\times C_b\) are being
discussed for \(a\leq 4\) and \(b\geq 1\). In [7] a new combinatorial interpretation of the
convoluted Catalan numbers were studied when chain blockers of \(P\) were studied for some special cases.
The Catalan numbers \(C(m)=C(m,1)\)
were introduced in \(1887\) by Catalan
[8-10].
In Section \(2\) we define an
\(i\)-shelter of
\(S_i(j)\) as a subset \(C\) of \(P\setminus
\{\mathcal{R}(P),\mathcal{L}(P)\}\) with the property that each
maximal chain of \(P\) containing \(v\in S_i(j)\) contains at least one element
of \(C\) and \(C\) is inclusion wise minimum with this
property. Here \(\mathcal{R}(P)\) and
\(\mathcal{L}(P)\) denote right maximum
and left maximum chains of \(P\),
respectively. We use this definition to describle chain blockers of
\(C_5\times C_b\) for \(b\geq 1\). In Section \(3\) some algebraic consequences of chain
blockers are given.
2. Main Result
Let \(P=C_a\times C_b\) be a poset
where \(C_i\) is the chain \(1< \cdots < i\). Let \[\mathcal{L}(P):=(1,1)<\cdots<(1,b)<\cdots
<(a,b)\] be the left maximal chain of \(P\) and \[\mathcal{R}(P):=(1,1)<\cdots
<(a,1)<\cdots < (a,b)\] be the right maximal chain of
\(P\). We quote the following Corollary
of [7].
Corollary 1. Let \(B
\subseteq P=C_a \times C_b\) be a chain blocker. Then \(B\) contains exactly one element from \(\mathcal{R}(P)\) and exactly one element
from \(\mathcal{L}(P)\).
For a particular subset of \(P\), we
define its shelter in the following way.
Definition 1. Let \(S_i(j)=\{(2,j),(3,j),\ldots,(i+1,j)\}\subset
P\). An \(i\)-shelter of \(S_i(j)\) is a subset \(C\) of \(P\setminus
\{\mathcal{R}(P),\mathcal{L}(P)\}\) with the property that each
maximal chain of \(P\) containing \(v\in S_i(j)\) contains at least one element
of \(C\) and \(C\) is inclusion wise minimum with this
property.
For example in Figure 1 (a), \(i=1,j=2\) and an \(1\)-shelter is \(\{(2,5),(3,6),(4,5),(4,4),(4,3),\)\((4,2)\}\). Also, in Figure 1(b), \(i=2,j=4\) and a \(2\)-shelter is \(\{(2,7),(3,7),(4,6),(4,5),(4,4)\}\). Note
that \(i\)-shelter is not unique. We
denote set of all \(i\)-shelters of
\(S_i(j)\) as \(\widehat{S}_i(j)\) with \(|\widehat{S}_i(j)|=\xi_i(j)\).
Figure 1: Two Shelters \(S_1(2)\) and \(S_2(4)\) for the Poset \(C_5 \times C_8\)
Proposition 1. Let \(P=C_5\times C_b\) be a poset and \(\widehat{S}_1(j)\) be the set of all \(1\)-shelter of \(S_1(j)\subset P\). Then \[|\widehat{S}_1(j)|=\xi_1(j)=3(2^{b-j-1})-b+j-1.\]
Proof. Let \(C\) be a \(1\)-shelter of \(\{(2,j)\}\). Then \(C\) must contains exactly one element from
the set \(\Gamma=\{(2,j),\ldots,(2,b-1)\}\). Because
if \(C\) does not contain any element
from \(\Gamma\) then \(C\) does not fulfil the definition of \(1\)-shelter and if there are two elements
\(\alpha,\beta \in \Gamma\cap C\) with
\(\alpha<\beta\) then by minimality
of \(C\)\(\beta\not\in C\), a contradiction. Now if
\((2,j)\in C\) then \(C=\{(2,j)\}\) is itself a \(1\)-shelter. Now let \((2,i)\in \Gamma\cap C\) for \(i\in \{j+1,\ldots,b-1\}\), then for \(C\) we have two independent choices: (\(a\)) either \((3,l)\in C\) or \((4,l)\in C\) for all \(l\in \{j,\ldots, i-2\}\), thus \(2^{i-j-1}\) such possibilities. (\(b\)) \(\{(3,k),(4,k-1),\ldots,(4,j)\}\subset C\)
for each \(k\in \{i-1,\ldots,b-1\}\),
thus \(b-i+1\) such options. Hence over
all we have \(2^{i-j-1}(b-i+1)\) number
of \(1\)-shelters \(C\) for this choice of \(i\). Hence total number of \(i\)-shelter \(C\) is given by \[1+\sum_{i=j+1}^{b-1}2^{i-j-1}(b-i+1)=3(2^{b-j-1})-b-1+j
.\] ◻
Corollary 2. Let \(P=C_5\times C_b\) be a poset and \(\widehat{S}_2(j)\) be the set of all \(2\)-shelter of \(S_2(j)\subset P\). Then \[|\widehat{S}_2(j)|=\xi_2(j)=3(2^{b-j-1})-2.\]
Proof. Let \(C\) be a \(2\)-shelter of \(\{(2,j),(3,j)\}\), then again as in the
proof of previous proposition, \(C\)
must contain exactly one element from the set \(\Gamma_1=\{(2,j),\ldots,(2,b-1)\}\). If
\((2,j)\in C\), then \(\{(2,j),(3,k),(4,k-1)\ldots,(4,j)\}\) is
the \(2\)-shelter for each \(k\in \{(j+1,\ldots,b-1)\}\). Thus there are
\(b-j-1\) number of \(2\)-shelters containing \((2,j)\). Also if \(\{(2,j),(3,j)\}\in C\), then \(C=\{(2,j),(3,j)\}\) is itself a 2-shelter.
Now if \((2,i)\in C\), where \(i\in \{j+1,\ldots,b-1\}\) then a \(1\)-shelter of \(\{(2,j)\}\) is also a \(2\)-shelter of \[\{(2,j),(3,j)\}\] and vice versa. Hence by
previous proposition total number of \(2\)-shelters of \(\{(2,j),(3,j)\}\) is given by \[b-j+\sum_{i=j+1}^{b-1}2^{i-j-1}(b-i+1)=3(2^{b-j-1})-2
.\] ◻
Remark 1. Let \(P=C_5\times C_b\) be a poset. Note that by
above corollary if we fix \((2,1)\in
\mathcal{R}(P)\) and \((1,3)\in
\mathcal{L}(P)\), then clearly \(\{(1,3)\}\cup C\cup \{(2,1)\}\) is chain
blocker of \(P\), where \(C\) is a \(1\)-shelter of \(\{(2,2)\}\). Thus number of chain blockers
of \(P\) containing \((2,1)\) and \((1,3)\) is given by \(|\widehat{S}_1(2)|\). Similarly the number
of chain blockers of \(P\) containing
\((3,1)\) and \((1,3)\) is given by \(|\widehat{S}_1(2)|\). Also in the same way
the number of chain blockers of \(P\)
containing \((4,1)\) and \((1,3)\) is given by \(|\widehat{S}_2(2)|\).
Let \(P=C_5\times C_b\) be a poset
and \(P_m^n\subset
P\setminus\{\mathcal{L}(P),\mathcal{R}(P)\}\) be a subset of
\(P\) defined by \((p,q)\in P_m^n\)\(\Leftrightarrow\)\(p \in \{2,3,4\}\) and \(q \in \{m, m+1, \ldots, m+n-1\}\). We
extend the idea of \(i\)-shelter in the
following way. Let \(\delta_m^n\) be a
subset of \(P_m^n\) such that for any
maximal chain \(B\) of \(P\) if \(B\cap
P_m^n\cap \mathcal{R}(P_m^n)\not= \emptyset\) then we must have
\(B\cap \delta_m^n\not=\emptyset\) and
\(\delta_m^n\) is minimum with this
property, where \(\mathcal{R}(P_m^n)=\{(5,i)\mid i\in
\{m,\ldots,m+n-1\}\}\).
Remark 2. A set \(\delta_m^n\) blocks each maximal chain of
\(P\) which passes through both \(P_m^n\) and \(\mathcal{R}(P_m^n)\).
Clearly we must have exactly one element from each row of \(P_m^n\) thus we have \(|\delta_m^n|=n\). Obviously \(\delta_m^n\) is not unique. Let \(\beta(n,\lambda_1,\lambda_2)\) be the
cardinality of set of all \(\delta_m^n\), where \(\lambda_1=\beta(0,\lambda_1,\lambda_2)\)
and \(\lambda_2=\beta(1,\lambda_1,\lambda_2)\).
Proposition 2. With the same notations as
defined above we have: \[\label{recursive}
\beta(n,\lambda_1,\lambda_2)=3\beta(n-1,\lambda_1,\lambda_2)-\beta(n-2,\lambda_1,\lambda_2).\tag{1}\]
Proof. To choose one element from each row, let \((\alpha,\beta)\in \delta_m^n\). If \(\alpha = 2\) or \(3\) then we can choose any element from
\((\beta+1)\)th row of \(P_m^n\). If \(\alpha = 4\) then we can not choose \((2,\beta+1)\) since in this case a maximal
chain containing \(\{(2,\beta),(3,\beta),(3,
\beta+1),(4,\beta+1)\}\subset P_m^n\) is not blocked. Thus for
each additional row, \(3\) choices each
for \(\alpha = 2\) or \(3\) and \(2\) choices for \(\alpha = 4\). Hence to get \(\beta(n,\lambda_1,\lambda_2)\) we have
\(3\beta(n-1,\lambda_1,\lambda_2)\)
minus one choice \(\alpha = 4\) which
is exactly equal to \(\beta(n-2,\lambda_1,\lambda_2)\). ◻
Using elementary methods from Combinatorics, we have the following
corollary.
Corollary 3. The generating function for the
recursive relation 1 is given by \[\beta\Big(n,\lambda_1,\lambda_2\Big)=\Big(\frac{\lambda_2-\lambda_1\alpha_2}{\alpha_1-\alpha_2}\Big)\alpha_1^{n}+\Big(\frac{\lambda_2-\lambda_1\alpha_1}{\alpha_2-\alpha_1}\Big)\alpha_2^{n},\]
where \(\alpha_1=\frac{3+\sqrt{5}}{2}\)
and \(\alpha_2=\frac{3-\sqrt{5}}{2}\).
We use Corollary 1 to calculate number of all chain
blockers of \(P=C_5\times C_b\). We fix
one element from \(\mathcal{R}(P)\) and
run over all elements of \(\mathcal{L}(P)\) one by one to calculate
all chain blockers which contain these two elements. Here is the first
proposition regarding this technique.
Proposition 3. Let \(P=C_5\times C_b\) be a poset. Then the
number of chain blockers of \(P\)
containing \((2,1)\in \mathcal{R}(P)\)
is given by \[\begin{aligned}
\mathcal{C}_{2,1}&=&1+\sum\limits_{j=0}^{b-3}\{\beta(j,1,2)\xi_1(b-j-2)+\beta(j,0,1)\xi_2(b-j-2)\}+3\beta(b-2,1,2)+2\beta(b-2,0,1).
\end{aligned}\]
Proof. If we take \((1,2)\in
\mathcal{L}(P)\), then \(\{(1,2),(2,1)\}\) is itself a chain
blocker. If we choose \((1,j)\in
\mathcal{L}(P)\) for \(j\in
\{3,\ldots,b\}\) then we need to calculate all possibilities
of chain blockers containing \(\{(2,1),(1,j)\}\) and elements from \(P_2^{b-1}\), where \(P_m^n\) is defined above. Now we divide the
rows of \(P_2^{b-1}\) into two disjoint
parts. One part is from row \(2\) to
row \(j-2\) and second part is from row
\(j-1\) to row \(b-1\). Now a chain blocker of \(P\) must contains elements from both of
these parts. In particular, each chain blocker must contain exaclty one
element from row \(j-2\) of \(P_2^{b-1}\).
If it contains \((4,j-2)\) then the
number of such chain blockers having elements from first part i.e. from
row \(2\) to row \(j-2\) of \(P_2^{b-1}\) is exactly equal to \(\beta(j-3,\lambda_1,\lambda_2)\) where in
this case we have \(\lambda_1=0\) and
\(\lambda_2=1\). For this case, number
of chain blockers from the second part i.e. from row \(j-1\) to row \(b-1\) is given by \(2\)-shelter \(\xi_2(b-j+1)\). Since choices from these
two parts are disjoint so total number of chain blockers in this case
are given by \(\beta(j-3,0,1)\xi_2(b-j+1)\).
On the other hand if a chain blocker contains \((2,j-2)\) or \((3, j-2)\), then number of such chain
blockers having elements from first part i.e. from row \(2\) to row \(j-2\) is given by \(\beta(j-3,\lambda_1,\lambda_2)\) where in
this case we have \(\lambda_1=1\) and
\(\lambda_2=2\). Also in this case
number of chain blockers containing elements from part \(2\) of \(P_2^{b-1}\) is given by the \(1\)-shelter \(\xi_1(b-j+1)\). Again since both of these
choices are independent so have total number chain blockers in this case
equals to \(\beta(j-3,1,2)\xi_1(b-j+1)\). Summing over
\(j\) from \(3\) to \(b\) we have partial proof to our
formula.
Now we are left to count the number of chain blockers of \(P\) contain \((2,1)\) and \((j,b)\), where \(j\in \{2,3,4\}\). A chain blocker
containing \((2,b)\) must contain
either \((2,b-1)\) or \((3,b-1)\), thus the number of such chain
blockers equals to \(\beta(b-2,1,2)\).
Also a chain blockers containing \((3,b)\) must contain \((2,b-1)\), \((3,b-1)\) or \((4,b-1)\) and hence the number of such
chain blockers equal to \(\beta(b-2,1,2)+\beta(b-2,0,1)\). Finally
the number of chain blockers containing \((4,b)\) equals to \(\beta(b-2,1,2)+\beta(b-2,0,1)\). So we
obatined \[\begin{aligned}
\mathcal{C}_{2,1}&=&1+\sum\limits_{j=0}^{b-3}\{\beta(j,1,2)\xi_1(b-j-2)+\beta(j,0,1)\xi_2(b-j-2)\}
+3\beta(b-2,1,2)+2\beta(b-2,0,1),
\end{aligned}\] which complete the proof. ◻
Corollary 4. Let \(P=C_5\times C_b\) be a poset. Then the
number of chain blockers of \(P\)
containing \((3,1)\) is given by \[\mathcal{C}_{3,1}=\mathcal{C}_{2,1}+\xi_1(b-2)-1.\]
Proof. Since any chain blocker of \(P\) containing \((2,1)\) and any \(p\in \mathcal{L}(P)\setminus \{1,2\}\)
remains a chain blocker if we replace \((2,1)\) by \((3,1)\). Thus we left with those chain
blockers which contains \((3,1)\) and
\((1,2)\). But number of such chain
blockers are given by \(\xi_1(b-2)\). ◻
Proposition 4. Let \(P=C_5\times C_b\) be a poset. Then the
number of chain blockers of \(P\)
containing \((4,1)\) is given by \[\begin{aligned}
\mathcal{C}_{4,1}&=&2\xi_2(b-2)+\sum\limits_{j=1}^{b-3}\{\beta(j,0,1)\xi_1(b-j-2)+\beta(j,1,1)\xi_2(b-j-2)\}\\
&&+3\beta(b-2,0,1)+2\beta(b-2,1,1).
\end{aligned}\]
Proof. If we fix \((1,2)\in
\mathcal{L}(P)\), then clearly number of chain blockers
containing \((4,1)\) and \((1,2)\) is given by the \(2\)-shelter \(\xi_2(b-2)\). Same is true if we fix \((1,3)\in \mathcal{L}(P)\). To calculate
remaining case of chain blockers we will use the same technique as in
the proof of Proposition 3. By the similar arguments the number of chain
blockers for the remaining cases are given by \[\sum\limits_{k=1}^{b-3}\{\beta(k,\lambda_1,\lambda_2)\xi_1(b-k-2)+\beta(k,\lambda'_1,\lambda'_2)\xi_2(b-k-2)\}\]\[+3\beta(b-2,\lambda_1,\lambda_2)+2\beta(b-2,\lambda'_1,\lambda'_2).\]
Now in this case \(\lambda_1=0\) and
\(\lambda_2=1\). Also we have \(\lambda'_1=1\) and \(\lambda'_2=1\). So we conclude \[\begin{aligned}
\mathcal{C}_{4,1}&=&2\xi_2(b-2)+\sum\limits_{j=1}^{b-3}\{\beta(j,0,1)\xi_1(b-j-2)+\beta(j,1,1)\xi_2(b-j-2)\}\\
&&+3\beta(b-2,0,1)+2\beta(b-2,1,1).
\end{aligned}\] which complete the proof. ◻
Proposition 5. Let \(P=C_5\times C_b\) be a poset. Then the
number of chain blockers of \(P\)
containing \((5,1)\) is given by \[\begin{aligned}
\mathcal{C}_{5,1}&=&2b-1+3\xi_2(b-3)+\sum\limits_{j=2}^{b-3}\{\beta(j-2,2,5)\xi_1(b-j-2)
\\
&&+\beta(j-2,1,3)\xi_2(b-j-2)\}+3\beta(b-4,2,5)+ 2\beta(b-4,1,3).
\end{aligned}\]
Proof. Let \(B\) be a chain
blocker of \(P\). Fix \((1,2)\in \mathcal{L}(P)\cap B\). Then \(B\) must contains \((4,2)\). Now if \((3,2)\in B\) then either \(B=\{(1,2),(2,2),(3,2),(4,2),(5,1)\}\) or
\(B=\{(1,2),(2,3),\)\((3,2),(4,2),(5,1)\}\). On the other hand if
\((3,2)\not\in B\) and \((2,2)\in B\). Then \(B=\{(1,2),(2,2),\)\((3,j),(4,j-1),\ldots,(4,2),(5,1)\}\), where
\(j=3,\ldots, b-1\). Lastly if both
\((2,2)\not\in B\) and \((3,2)\not\in B\) holds then number of such
chain blockers are given by \(2\)-shelter \(\xi_2(b-3)\). Similarly if we fix \((1,3)\in \mathcal{L}(P)\cap B\) then we
have the same number of chain blockers. Now we fix \((1,4)\in \mathcal{L}(P)\cap B\), then the
only difference from the previous two cases is while \((3,2)\in B\), in this we have only one
chain blocker given by \(B=\{\)(1,4)\(,\)(2,3)\(,\)(3,2)\(,\)(4,2)\(,\)(5,1)\(\}\) as shown in figure 1. Thus total
number of chain blockers containing \((5,1)\) and a element from the set \(\{(1,2),(1,3),(1,4)\}\) is given by \(2b-1+3\xi_2(b-3)\). Now for the remaining
cases we will use the same technique as we use in the proof of
Proposition 3. Here for the multiplier of \(\xi_1\), we have \(\beta(k-2,\lambda_1,\lambda_2)\), where
\(\lambda_1\) is equal to \(2\) since both \(\{(4,2),(3,2),(2,3)\}\) and \(\{(4,2),(3,3)\}\) ends up for \(1\)-shelter. Now if we extend to next row,
then \(\{(4,2),(3,2),(2,3),(2,4)\}\),
\(\{(4,2),(3,2),(2,3),(3,4)\}\), \(\{(4,2),(3,3),(2,4)\}\), \(\{(4,2),(3,3),(3,4)\}\) and \((4,2),(4,3),(3,4)\) lead to \(1\)-shelter. Hence \(\lambda_2=5\). On the other hand, for the
multiplier of \(\xi_2\), we have \(\beta(k-2,\lambda'_1,\lambda'_2)\).
Now \(\lambda'_1=1\) due to \(\{(4,2),(4,3)\}\) and \(\lambda'_2=3\) due to \(\{(4,2),(3,2),(2,3),(4,4)\}\), \(\{(4,2),(3,3),(4,4)\}\) and \(\{(4,2),(4,3),(4,4)\}\). Thus \[v\sum\limits_{k=2}^{b-3}\{\beta(k-2,2,5)\xi_1(b-k-2)\]
counts number of all chain blockers contain \((5,1)\) and \((1,j)\), where \(j=5, \ldots, b\). The remaining case are
thus given by \(3\beta(b-4,2,5)+
2\beta(b-4,1,3)\). As a result we conclude \[\begin{aligned}
\mathcal{C}_{5,1}&=&2b-1+3\xi_2(b-3)+\sum\limits_{j=2}^{b-3}\{\beta(j-2,2,5)\xi_1(b-j-2)\\
&&+\beta(j-2,1,3)\xi_2(b-j-2)\}+3\beta(b-4,2,5)+ 2\beta(b-4,1,3),
\end{aligned}\] which complete the proof. ◻
Proposition 6. Let \(P=C_5\times C_b\) be a poset. Then the
number of chain blockers of \(P\)
containing \((5,2)\) is given by \[\begin{aligned}
\mathcal{C}_{5,2}&=&5\xi_1(b-4)+5b+5+4\xi_2(b-4)+\sum\limits_{j=5}^{b-1}\{\beta(j-5,7,17)\xi_1(b-j)\\
&&+\beta(j-5,3,10)\xi_2(b-j)\}+3\beta(b-5,7,17)+ 2\beta(b-5,3,10).
\end{aligned}\]
Proof. Let \(B\) be an
arbitrary chain blocker of \(P\)
containing \((5,2)\). If we fix \((1,2)\in B\cap \mathcal{L}(P)\) then
obviously \(B\) must contain at least
one element from each middle columns. Let \(\{(4,2),(3,2)\}\in B\) then either \((2,2)\) or \((2,3)\) belongs to \(B\). Similarly if \(\{(4,2),(3,3)\}\in B\) the \(B\) must contain at least one element from
the set \(\{(2,2),(2,3)\}\) or one
element from \(1\)-shelter starting at
\((2,4)\). Thus number of chain
blockers containing the set \(\{\)(5,2)\(,\)(4,2)\(,\)(1,2)\(\}\) is given by \(4+\xi_1(b-4)\).
Now let \(\{(4,3),(2,2)\}\in B\).
Then \(B\) must contain either one
element from the set \(\{(3,2),(3,3),(3,4)\}\) or contain \((3,j),(4,j-1),\ldots,(4,4)\) for \(j=5,\ldots,b-1\). The same is true if \(\{(4,3),(2,3)\}\in B\). Now if we take
\(B=\{(5,2),(4,3),(3,3)(2,4),(1,2)\),
then the only case remaining for \(B\)
containing \((5,2)\) and \((1,2)\) is given by the \(2\)-shelter starting at \(\{(2,4),(3,4)\}\). Thus number of chain
blockers containing \((5,2)\) and \((1,2)\) is given \[\label{equ1}
2b+1+\xi_1(b-4)+\xi_2(b-4).\tag{2}\] Lets move to second element of
\(\mathcal{L}(P)\) that is \((1,3)\in B\cap \mathcal{L}(P)\). Note that
each chain blocker of \(P\) containing
\(\{(1,2),(5,2)\}\) will remain a chain
blocker if we replace \((1,2)\) with
\((1,3)\) and vice versa. Thus in this
case we have the same number of chain blockers as given in Equation 2.
Now let \((1,4)\in B\cap
\mathcal{L}(P)\). If \((4,2)\in
B\) then we have three possibilities, namely \[B=\{(5,2),(4,2),(3,2),(2,3),(1,4)\},\] or
\[B=\{(5,2),(4,2),(3,3),(2,3),(1,4)\},\] or
\[B=\{(5,2),(4,2),(3,3),(1,4)\}\cup
X_1,\] where \(X_1\) is an
element of \(1\)-shelter having base
element \((2,4)\). Secondly if \((4,3)\in B\) again we have three
possibilities. Either \[B=\{(5,2),(4,3),(4,4),\ldots,(4,j-1),(3,j),(2,3),(1,4)\}\]
for \(j=2,\ldots,b-1\), or \(B=\{(5,2),(4,3),(3,3),(2,4),(1,4)\}\), or
\[B=\{(5,2),(4,3),(1,4)\}\cup X_2\]
where \(X_2\) is an element of \(2\)-shelter having base elements \(\{(2,4),(3,4)\}\). Thus number of chain
blockers containing \((5,2)\) and \((1,4)\) is given by \[b+1+\xi_1(b-4)+\xi_2(b-4).\] Now let \((1,5)\in B\cap \mathcal{L}(P)\). If \((4,2)\in B\) then either \[B=\{(5,2),(4,2),(3,2),(2,3),(1,5)\}\cup
X_1,\] or \[B=\{(5,2),(4,2),(3,3),(1,5)\}\cup X_1,\]
where \(X_1\) is an element of \(1\)-shelter starting from \((2,4)\). Secondly if \((4,3)\in B\) then following three cases
occurs. \[B=\{(5,2),(4,3),(3,2),(2,3),(2,4),(1,5)\},\]
or \[B=\{(5,2),(4,3),(3,3),(2,4),(1,5)\},\] or
\[B=\{(5,2),(4,3),(1,5)\}\cup X_2,\]
where \(X_2\) is an element of \(2\)-shelter having base elements \(\{(2,4),(3,4)\}\). Now summing over all
above cases i.e. number of chain blockers containing \((5,2)\) and exactly one element from the
set \(\{(1,2),\ldots,(1,5)\}\) is given
by \[5b+5+5\xi_1(b-4)+4\xi_2(b-4).\]
For the remaining part of the proof we will use the same technique as
used in the proves of previous results. Namely, for \(k=5,\ldots,b-1\) the multiplier of \(\xi_1(b-k)\), we have \(\beta(k-5,\lambda_1,\lambda_2)\), where
\(\lambda_1\) is equal to \(7\) due to \(\{(4,2),(3,2),(2,3),(2,4)\}\), \(\{(4,2),(3,2),(2,3),(3,4)\}\), \(\{(4,2),(3,3),(2,4)\}\), \(\{(4,2),(3,3),(3,4)\}\), \(\{(4,3),(3,2),(2,3),(2,4)\}\), \(\{(4,3),(3,3),(2,4)\}\) and \(\{(4,3),(3,4)\}\). Similarly if we extend
to next level we have \(\lambda_2=17\).
On the other hand, for the multiplier of \(\xi_2(b-k)\), we have \(\beta(k-5,\lambda'_1,\lambda'_2)\).
Now \(\lambda'_1=3\) due to \(\{(4,2),(3,2),(2,3),(4,4)\}\), \(\{(4,2),(3,3),(4,4)\}\) and \(\{(4,3),(4,4)\}\). Similarly if we extend
to next level we have \(\lambda'_2=10\). Thus summing over all
\(k\) and adding the similar cases for
\((2,b)\), \((3,b)\) and \((4,b)\in B\cap \mathcal{L}(P)\). So we
obtained our required result as: \[\begin{aligned}
\mathcal{C}_{5,2}&=&5\xi_1(b-4)+5b+5+4\xi_2(b-4)+\sum\limits_{j=5}^{b-1}\{\beta(j-5,7,17)\xi_1(b-j)
\\
&&+\beta(j-5,3,10)\xi_2(b-j)\}+3\beta(b-5,7,17)+ 2\beta(b-5,3,10).
\end{aligned}\] ◻
Remark 3. So far we have calculated all chain
blockers containing \(v\) where \(v\in \{(1,1),\ldots,\)\((5,1),(5,2)\}\subset \mathcal{R}(P)\).
Since each chain blocker of \(P\)
contains at least one element from \(\mathcal{R}(P)\) thus we are left with the
case of calculating number of chain blockers containing \(\mathcal{R}(P) \setminus
\{(1,1),\ldots,(5,1),(5,2)\}\equiv \{(5,3),\ldots,(5,b-1)\}\). We
first calculate number of chain blockers \(B\) containing \((5,k)\) where \(k\in\{3,\ldots, b-2\}\). Then \(B\) must contains exactly one element \(w\) from \(\mathcal{L}(R)\). Then we have following
choices of \(w\).
\(w=(1,i)\) where \(2\leq i\leq k+1\)
\(w=(1,i)\) where \(k+2\leq i\leq b\)
\(w=(o,b)\) where \(2\leq o\leq 4\)
In the following results we will use notations from this
remark.
Proposition 7. Let \(\mathcal{C}(k,b)\) be number of chain
blockers containing \((5,k)\) and \((1,i)\) for \(3\leq k\leq b-2\) and \(2\leq i\leq k+1\). Then \[\begin{aligned}
\nonumber
\mathcal{C}(k,b)&=&f_a(k)+\sum_{m=6}^{k+3}f_b(k,m)+2k(b-2)-k^2+3k-2\\
\nonumber &&+\sum_{j=4}^{k+2}f_c(k,j)+(4k-3)\xi_1(b-k-2)\\
\nonumber
&&+\sum_{p=6}^{k+2}f_d(k,p)+(k+1)(1+\xi_2(b-k-2))+k+\xi_2(b-k-2),
\end{aligned}\] where \[\begin{aligned}
% \nonumber to remove numbering (before each equation)
\nonumber f_a(k) &=& \frac{4k^3+27k^2-37k-6}{6}, \\
\nonumber f_b(k,i) &=&
\sum_{j=2}^{i-3}2^{i-j-1}(i-2)(k-i+3+\xi_1(b-k-2)), \\
\nonumber f_c(k,i)&=&(k-i+3)(b-2)-(\frac{k^2-3k+2}{2}-\frac{i^2-7i+12}{2}), \\
\nonumber f_d(k,i)&=&\sum_{j=1}^{k-i+3}(k-1+\frac{j^2+j}{2})+(k-i+3)\xi_1(b-k-2).
\end{aligned}\]
Proof. To calculate number of chain blockers containing
\((5,k)\in \mathcal{R}(P)\) and \(w=(1,i)\) where \(3\leq k\leq b-2\) and \(2\leq i\leq k+1\), we divide into two main
cases.
Case 1.\(2\leq i\leq
5\)
Since a chain blocker \(B\) contains
only these two elements from \(\mathcal{R}(P)\) and \(\mathcal{L}(P)\) so \(B\) must contains at least one element
\((4,l)\) from \(4^{th}\) column. If \(l\leq k\), then \((4,l)\) is the only element which \(B\) contains from column \(4\). Also \(B\) must contains at least one element from
the column \(2\) and \(3\). Now if \((2,m)\in B\) then either \(2\leq m\leq k+1\) or \(m>k+1\). For the first case the number
of chain blockers are same for \(m=2\)
and \(m=3\). Now if \(k+1\geq m\geq l+2\), then the set \(\{(3,l+1),\ldots,(3,m-1)\}\) must belong to
\(B\) and hence we have \(k-l-1\) number of choices. But if \(l+1\geq m\geq 3\), then \[B=\{(1,2),(2,m),(3,n),(4,l),(5,k)\},\]
where \(l+1\geq n \geq m-1\) and we
have \(l+1-(m-1)+1\) number of choices
for this case. Thus subtotal for number of chain blockers in this case
is given by \[\label{eq1}
\sum_{l=2}^k(\sum_{m=3}^{l+1}(l-m+3)+l+\sum_{m=l+2}^{k+1})=\frac{1}{6}k^3+\frac{3}{2}k^2-\frac{5}{3}k. \tag{3}\]
Note that in the above case, if we replace \((1,2)\) with \((1,3)\in \mathcal{R}(P)\) the number of
chain blockers remains the same. On the other hand if we replace \((1,2)\) with \((1,4)\in \mathcal{R}(P)\) then there is no
chain blocker containing \((1,4),\)\((5,k)\) and \((2,2)\), where as the remaining
calculations will be the same as above thus subtotal of number of chain
blockers in this case is given by \[\label{eq2}
\sum_{l=2}^k(\sum_{m=3}^{l+1}(l-m+3)+\sum_{m=l+2}^{k+1})=\frac{1}{6}k^3+k^2-\frac{13}{6}k+1.\tag{4}\]
With the similar arguments and considering the same limits as above, the
number of chain blockers containing \((1,5)\) is given by \[\label{eq3}
\frac{1}{6}k^3+\frac{1}{2}k^2-\frac{2}{3}k-2. \tag{5}\] Let \(f_a(k)\) be function obtained by summing
over the equation 3 two times(for both \((1,2)\) with \((1,3)\)), equations 4 and equation 5.
Thus \[\label{eq4}
f_a(k)=\frac{4k^3+27k^2-37k-6}{6}.\tag{6}\]
Now for \((1,i)\) where \(6\leq i\leq k+3\), and fixing \((5,k)\in \mathcal{R}(P)\) for \(3\leq k\leq b-2\). We take \((4,j)\in B\) with \(j=2,\ldots, i-3\). Then there are four
different calculations are involved, namely:
For each \(j=2,\ldots, i-3\), we
must have either \(\{(4,j),(3,n),(2,n+1),\ldots,(2,i-1)\}\in
B\) for \(n=2,\ldots,j\) or
\(\{(4,j),(3,j+1)\}\in B\). Thus it
counts \(i-2\) possibilities as
whole.
Either \((2,o)\) or \((3,o)\) belongs to \(B\) for \(o=j+1,\ldots, i-1\). Thus it counts \(2^{i-j-1}\).v
Either \((2,i-1)\in B\) or \(\{(2,o),(3,o-1),\ldots,(3,i-1)\}\) for
\(o=i,\ldots, k+1\). Thus as a whole we
have \(k-i+3\) possibilities.
\(i\)-shelter having \((2,k+2)\) as the base point so it counts
\(\xi_1(b-k-2)\).
Keeping in view the nature of above four choices we have the
following description for this case. \[\label{eq5}
f_b(k,i)=\sum_{j=2}^{i-3}2^{i-j-1}(i-2)(k-i+3+\xi_1(b-k-2)).\tag{7}\]
Now again if \(\{(1,i),(5,k)\}\in B\)
where \(i=3,\ldots,k+2\). Then if \((4,k+1)\) then for each \((2,m)\in B\) with \(m=3,\ldots,k+1\) we have \[B=\{(1,i),(2,m),(3,n),(4,k+1),(5,k)\}\]
where \(n=m-1,\ldots,k+2\). Also for
\(k+2<n\leq b-2\), the element \((3,n)\) is replaced by \((3,n),(4,n-1),\ldots,(4,k)\). Thus for each
\(m\) we have \(b-m\) number of chain blockers thus total
number of chain blockers are given by \[f_c(k,i)=(k-i+3)(b-2)-(\frac{k^2-3k+2}{2}-\frac{i^2-7i+12}{2}).\]
Note that the number of chain blockers containing \((1,3)\) and \((1,2)\) is same so we add one additional
\(f_c(k,3)\) in the final calculations.
Now for \((5,k)\) and \((1,i)\) in \(B\) with \(4\leq
k\leq b-2\) we restrict \(6\leq i\leq
k+2\) and \(i-2\leq l\leq k\)
for \((4,l)\in B\). We have following
possibilities of calculations. For each \((4,l)\in B\) there must be at least one
element from the \(2^{\text{nd}}\) and
the \(3^{\text{rd}}\) column. Now there
are three types of possibilities. Namely:
\(\{(2,i-1),\ldots,(2,j),(3,j-1)\}\) belongs
to \(B\) for \(j=3,\ldots,i-3\).
\(\{(2,m),(3,n)\}\in B\) for
\(i-1\leq m\leq k+2\) and \(2\leq n\leq m\).
for \(\{(4,k+1),(3,k+2)\}\) the
number of chain blockers is given by \(\xi_1(b-k-2)\).
Thus total number for this subcase is given by: \[f_d(k,i)=\sum_{j=1}^{k-i+3}(k-1+\frac{j^2+j}{2})+(k-i+3)\xi_1(b-k-2).\]
Now finally the number of chain blockers containing \((1,i),(4,k+1),(5,k)\) and \(m,n\geq k+2\) is given by \(\xi_2(b-k-2)\) with \(\{(2,k+2),(3,k+2)\}\) as the base elements.
It completes the proof. ◻
Proposition 8. Let \(P=C_5\times C_b\) be a poset. Let \(B\) be a chain blocker containing \((5,k)\) and \((1,i)\) such that \(3\leq k\leq b-2\) and \(i\geq k+2\). Let \(\beta(b,\lambda_1,\lambda_2)\) be the
coefficient of \(\xi_1\) and \(\beta(b,\mu_1,\mu_2)\) be the coefficient
of \(\xi_2\). Then \[\begin{aligned}
% \nonumber to remove numbering (before each equation)
\nonumber \lambda_1 &=& g(k), \\
\nonumber \lambda_2 &=& 2g(k)+h(k), \\
\nonumber \mu_1 &=& h(k), \\
\nonumber \mu_2 &=& g(k)+h(k),
\end{aligned}\] where \[\begin{aligned}
% \nonumber to remove numbering (before each equation)
\nonumber g(k) &=& \sum_{j=0}^{k-1} 2^{k-1-i}(2+i), \\
\nonumber h(k) &=& \sum_{i=0}^{k-2}2^{k-i-2}(2+i)+1.
\end{aligned}\]
Proof. It follows from the proofs of Propositions 3-6 and
from the definitions of \(g(k)\) and
\(h(k)\). ◻
Theorem 1. Let \(\mathcal{D}(k,b)\) be the number of chain
blockers containing \((5,k)\) and \((1,i)\) for \(3\leq k\leq b-2\) and \(i\geq k+2\). Then \[\begin{aligned}
% \nonumber to remove numbering (before each equation)
\nonumber \mathcal{D}(k,b)) &=&
\mathcal{C}(k,b)+\sum_{q=k+3}^{b-1}(\beta(q-k-3,g(k),2g(k)+h(k))\xi_1(b-q)
\\
\nonumber&&+\beta(q-k-3,h(k),g(k)+h(k))\xi_2(b-q))\\
\nonumber&& + 2\beta(b-k-4,g(k),2g(k)+h(k)) \\
\nonumber&& + \beta(b-k-4,h(k),g(k)+h(k)) \\
\nonumber&&+ 2\beta(b-k-3,g(k),2g(k)+h(k)) \\
\nonumber&&+ 2\beta(b-k-3,h(k),g(k)+h(k)).
\end{aligned}\]
Proof. By using the above calculations and selecting the
elements one by one from both left end maximal chain and right end
maximal chain, we have the result. ◻
On combining all the results and after simplification, we have the
following theorem.
Theorem 2. Let \(\mathcal{T}(k,b)\) be the total number of
chain blockers of \(C_5 \times C_b\)
for \(b\geq 1\). Then \[\begin{aligned}
\nonumber \mathcal{T}(k,b)&=&
\mathcal{C}_{2,1}+\mathcal{C}_{3,1}+\mathcal{C}_{4,1}+\mathcal{C}_{5,1}+\mathcal{C}_{5,2}+\sum_{k=3}^{b-3}\mathcal{D}(k,b))+2\sum_{m=6}^{b+1}f_{bb}(b-2,m)\\
\nonumber &&+
2\sum_{n=4}^bf_c(b-2,n)+2\sum_{o=6}^bf_{dd}(b-2,o)\\
&&+5\sum_{p=0}^{b-4}(2+p)2^{b-4-p}+\frac{4}{3}b^3+3b^2 –
\frac{97}{3}b+40,
\end{aligned}\] where \[\begin{aligned}
\nonumber f_{bb}(k,i) &=&
\sum_{j=4}^{i-1}2^{i-j-1}(i-2)(k-i+3), \\
\nonumber
f_c(k,i)&=&(k-i+3)(b-2)-(\frac{k^2-3k+2}{2}-\frac{i^2-7i+12}{2}),
\\
\nonumber
f_{dd}(k,i)&=&\sum_{j=1}^{k-i+3}(k-1+\frac{j^2+j}{2}).
\end{aligned}\]
3. Applications
In this section we provide algebraic consequences associated to a
chain blocker \(B\) of \(P\). A simplicial complex \(\Delta\) on the vertex set \(V=[n]\) is a collection of subsets of \(2^{[n]}\) with the property that if \(A\in \Delta\) then \(\Delta\) contains all subsets of \(A\). The inclusionwise maximum elements of
\(\Delta\) are called facets. Let \(\{F_i,\ldots,F_r\}\) be the set of facets
of \(\Delta\). A minimal vertex cover
of \(\Delta\) is a subset \(A\subseteq V\) with the property that for
every facet \(F_i\) of \(\Delta\) there exist a vertex \(v\in A\) such that \(v\in F_i\) and \(A\) is minimal with this property.
Let \(\Delta_P\) be a simplicial
complex associated to a poset \(P\) in
such a way that elements of \(\Delta_P\) are exactly the chains in \(P\). The set of facets of \(\Delta_P\) are the maximal chains of \(P\) and hence each chain blockers of \(P\) is a minimal vertex cover of \(\Delta_P\). The simplicial complex \(\Delta_P\) is called the order complex.
Now we are ready to relate a poset \(P\) to its algebraic counterpart. Let \(S=k[x_1,\ldots,x_n]\) be the polynomial
ring over the field \(k\) and in \(n\) variables. Recall that a monomial ideal
in \(S\) is an ideal generated by
monomials \(u_i\). A monomial ideal is
called a squarefree monomial ideal if it is generated by the squarefree
monomials. Let \(I=I_1\cap \cdots \cap
I_r\) be an irredundant primary decomposition of \(I\), where ideals \(I_1,\ldots,I_r\) are called irreducible
primary components of \(I\). For more
details about primary decomposition see [11].
To each square free monomial ideal \(I\) one can associate a simplicial complex
\(\Delta\). One way of this association
is facet ideals and facet complex introduced by Sara Faridi [4]. A facet ideals \(I^{\mathcal{F}}(\Delta)\) of \(\Delta\) is an ideal generated by
squarefree monomial \(x_{i_1}\cdots
x_{i_t}\) where \(\{x_{i_1},\ldots,
x_{i_t}\}\) is a facet of \(\Delta\). Let \(I=\langle u_1,\ldots,u_r \rangle\) be a
squarefree monomial ideal. A facet complex \(\Delta^{\mathcal{F}}(I)\) of \(I\) is a simplicial complex over the vertex
set \(\{v_1,\ldots,v_n\}\) and set of
facets \(\{F_1,\ldots,F_r\}\), where
\(F_i=\{v_j: x_j\mid u_i,\,\,\ 1\leq j\leq
n\}.\)
It is well known that minimal vertex covers of \(\Delta^{\mathcal{F}}(I)\) correspond to the
irreducible primary components of \(I^{\mathcal{F}}(\Delta)\). Let \(I_P=I^{\mathcal{F}}(\Delta_P)\). Note that
\(I_P\) is also the path ideals of the
directed graph of Hasse diagram of \(P\). The path ideal was intorduced by Conca
and De Negri in [4]. Some
results of \(I_P\) were also studied in
[5]. Since the facets of
\(\Delta_P\) are the maximal chains of
\(P\), hence by definition of a chain
blocker we have the following proposition.
Proposition 9. Let \(P=C_a\times C_b\) be a poset and \(I_P\) is the path ideal of the directed
graph of the Hasse diagram of \(P\)
only if \(P\) is a pure poset, that is
all the maximal chains have the same length.
Following examples demonstrate the one to one correspondence given in
above proposition. By using the Alexander duality, the minimal prime
ideals of \(I_{P}\) are in one to one
correspondence with the minimal generators of the Stanley-Reisner ideal
of the Alexander dual of \(I_{P}\),
that is \(I_{P}^{\vee}\).
Example 1. Numbers of chain blockers in \(C_5 \times C_5, C_5 \times C_6,\) and \(C_5 \times C_7\) are given in table 1
below. In this table, we have verified the corresponding number of
irreducible primary components of \(I_P\).
Let \(P=C_5\times C_6\) be a
poset. Consider the ideal containing \(x_{54}\) in \(C_5
\times C_6\).
Since each irreducible primary components of \(I_P\) correspond to a chain blocker of
\(P\). Thus by Theorem 1 number of irreducible primary
components of \(I_P\) is given by \(205\). The same number is verified by the
Computer Algebra System CoCoA and Singular.
Table 1: No. of Chain Blockers and Their Corresponding No. of Primary Components of $I_P$ in $C_5 \times C_b$, $5 \leq b \leq 7$
poset
chain blockers containing \(ij\)
no. of chain blockers
no. of primary components of \(I_P\) containing \(x_ij\)
\(C_5 \times C_5\)
21
82
82
31
89
89
41
66
66
51
45
45
52
66
66
53
89
89
54
82
82
\(C_5 \times C_6\)
21
238
238
31
256
256
41
181
181
51
114
114
52
147
147
53
170
170
54
205
205
55
187
187
\(C_5 \times C_7\)
21
676
676
31
717
717
41
488
488
51
297
297
52
366
366
53
366
366
54
374
374
55
417
417
56
376
376
Acknowledgment
This research is supported by Higher Education Commission of Pakistan
under NRPU project “Properties of Ranking Ideals” via Grant No.\(20-3665/R\&D/HEC/14/699.\)
Conflict of
Interest
The authors declare no conflict of interest.
References:
Villareal, R., 2001. Monomial algebras.
Marcel Dekker Inc.
Eisenbud, D., Huneke, C. and Vasconcelos, W., 1992. Direct methods
for primary decomposition. Inventiones Mathematicae, 110,
pp.207–235.
Ha, H. T. and Morey, S., 2010. Embedded associated primes of powers
of square-free monomial ideals. Journal of Pure and Applied Algebra,
214(4), pp.301–308.
Conca, A. and Negri, E. D., 1999. \(M\)-sequence, graph ideals and ladder
ideals of linear type. Journal of Algebra, 211, pp.599–624.
Kubitzke, M. and Olteanu, A., 2014. Algebraic properties of classes
of path ideals of posets. Journal of Pure and Applied Algebra,
218(6), pp.1012–1033.
Ahmad, S., 2016. On the chain blockers of a poset. Mathematical
Reports, 18(68), pp.205–215.
Ahmad, S. and Welker, V., 2016. Chain blockers and convoluted Catalan
numbers. Order, 33(2), pp.347–358.
Catalan, E., 1887. Sur les nombres de Segner. Rendiconti del
Circolo Matematico di Palermo, 1, pp.190–201.
Tedford, S. J., 2011. Combinatorial interpretations of convolutions
of the Catalan numbers. Integers, 11, A3.
West, J., 1995. Generating trees and the Catalan and Schröder
numbers. Discrete Mathematics, 146, pp.247–262.
Faridi, S., 2002. The facet ideal of a simplicial complex.
Manuscripta Mathematica, 109(2), pp.159–174.
Citation
Sarfraz Ahmad, Muhammad Kamran Siddiqui, Muhammad Arfan Ali, Muhammed Nadeem. On the Shelter of a Poset & Its Algebraic Applications[J], Ars Combinatoria, Volume 159. 59-71. DOI: https://doi.org/10.61091/ars159-07.
