1 Introduction
In recent years, there has been a growing interest in the study of zero-divisor graphs of ordered structures. One of the main reasons is that this is a tool to study other graphs associated with algebraic structures, such as the zero-divisor graph of reduced commutative rings, the intersection graph of ideals, the comaximal ideal graph, the nilpotent graph and the annihilating ideal graph.
The concept of a zero-divisor graph was introduced by Beck [Reference Beck3] to colour commutative rings with unity. He considered a simple graph
$G(R)$
whose vertices are the elements of R and two distinct elements x and y are adjacent if and only if
$xy=0$
. Anderson and Livingston [Reference Anderson and Livingston1] modified this definition of the zero-divisor graph by changing the vertex set to the set of nonzero zero-divisors with the same adjacency.
In [Reference Halaš and Jukl7], Halaš and Jukl introduced the zero-divisor graph of a poset with the least element
$0$
: the elements of the poset are the vertices and there is an edge between two vertices x and y if
$0$
is the only element lying below x and y. They obtained similar results for the zero-divisor graph of a poset as Beck did in [Reference Beck3].
The definition of the zero-divisor graph of a poset, originally introduced in [Reference Halaš and Jukl7] and later modified by Lu and Wu [Reference Lu and Wu12] (see also Joshi [Reference Joshi8]), is stated as follows.
Definition 1.1. Let P be a poset with
$0$
. Define a zero-divisor of P to be any element of the set
$Z(P)=\{a\in P \ |$
there exists
$b\in P\setminus \{0\}$
such that
$\{a,b\}^\ell =\{0\}\}$
. The zero-divisor graph of P is the graph
$\Gamma (P)$
whose vertices are the elements of
$Z(P)\setminus \{0\}$
, and two vertices a and b are adjacent if and only if
$\{a,b\}^\ell =\{0\}$
. Here,
$\{a,b\}^\ell =\{x\in P\ | \ x \leq a, b\}$
.
In [Reference Villarreal15], Villarreal studied the ideal associated with graphs, calling it the edge ideal. He discovered the class of Cohen–Macaulay graphs. In combinatorial commutative algebra, Cohen–Macaulay rings play a vital role, so it is important to find a class of simplicial complexes whose Stanley–Reisnar ring (face ring) is Cohen–Macaulay. A graph
$\Gamma $
is said to be Cohen–Macaulay, vertex decomposable, well-covered/unmixed/pure or Gorenstein if the independence complex of
$\Gamma $
has that property. The independence complex of a graph
$\Gamma $
is defined in the next section.
In [Reference Liu and Wu11], Liu and Wu proved that Boolean graphs are Cohen–Macaulay. In the first part of this paper, we show that the zero-divisor graph of a Boolean poset possesses the Cohen–Macaulay property, and thus generalise the result of Liu and Wu.
Theorem 1.2. If P is a Boolean poset, then
$\Gamma (P)$
is Cohen–Macaulay.
In the second part, we prove the converse of this theorem for a special class of posets. This result generalises the main theorem of Asir et al. [Reference Asir, Cheri, Pournaki and Poursoltani2].
Theorem 1.3. Let
$ \mathbf { P}=\prod _{i=1}^{n}P_i \ (n\geq 3)$
, where the
$P_i$
are finite bounded posets such that
$Z(P_i)=\{0\}$
for all i and
$2\leq |P_1|\leq |P_2|\leq \cdots \leq |P_n|$
. Then, the following statements are equivalent:
-
(1)
$\Gamma (\mathbf {P})$
is Cohen–Macaulay; -
(2)
$\Gamma (\mathbf {P})$
is well-covered; -
(3)
$|P_i|=2$
for all
$i=1,2,\ldots ,n$
; -
(4)
$\mathbf {P}$
is a Boolean lattice; -
(5)
$\mathbf {P}$
is a Boolean poset.
2 Preliminaries
2.1 Combinatorial commutative algebra and graph theory
A simplicial complex
$\Delta $
on a set V is a collection of subsets of V such that for every
$B \in \Delta $
and every
$A \subseteq B$
, we also have
$A \in \Delta $
. The elements of
$\Delta $
are called faces. The set V is called the vertex set of
$\Delta $
and its elements are called the vertices.
A face F of
$\Delta $
is called a facet if there is no face
$B \in \Delta $
such that
$F \subset B$
. The set of all facets of
$\Delta $
is denoted by
$\mathcal {F}(\Delta )$
. The complex
$\Delta $
is called a simplex if it has exactly one facet.
The dimension of a face A is defined by
$\operatorname {dim}(A)=|A|-1$
. The dimension of the simplicial complex
$\Delta $
is the maximum dimension of any of its faces and is denoted by
$\operatorname {dim}(\Delta )$
. A simplicial complex
$\Delta $
is called pure if all facets of
$\Delta $
have the same dimension; otherwise, it is called nonpure. A pure simplicial complex is also called well-covered.
In what follows, we consider the simplicial complex of independent vertex sets of a graph
$\Gamma $
, denoted by
$\Delta _{\Gamma }$
. The faces of
$\Delta _{\Gamma }$
are precisely the independent sets of
$\Gamma $
and the facets of
$\Delta _{\Gamma }$
are the maximal independent sets of
$\Gamma $
.
Let
$S=\mathbb {K}[x_1,\ldots ,x_n]$
be the polynomial ring in n variables over a field
$\mathbb {K}$
and let
$\Delta $
be a simplicial complex on the vertex set
$[n]=\{1, 2, \ldots , n\}$
. For a subset
$F \subseteq [n]$
, denote
$x_F = \prod _{i \in F} x_i$
.
The Stanley–Reisner ideal of
$\Delta $
over
$\mathbb {K}$
is the ideal
$I_\Delta \subseteq S$
generated by all squarefree monomials
$x_F$
corresponding to subsets
$F \notin \Delta $
. The corresponding Stanley–Reisner ring is defined by
$ \mathbb {K}[\Delta ] = S / I_\Delta. $
A simplicial complex
$\Delta $
is said to be Cohen–Macaulay (respectively Gorenstein) over
$\mathbb {K}$
if its Stanley–Reisner ring
$\mathbb {K}[\Delta ]$
is a Cohen–Macaulay ring (respectively a Gorenstein ring).
Let
$\Gamma =(V,E)$
be a finite simple graph with the vertex set V. The edge ideal of
$\Gamma $
, denoted by
$I(\Gamma )$
, is the squarefree monomial ideal in the polynomial ring
${S=\mathbb {K}[x_1,\ldots ,x_n]}$
defined by
$ I(\Gamma )=( x_i x_j : \{i,j\} \in E ). $
That is, each edge
$\{i,j\}$
of the graph corresponds to a quadratic squarefree monomial
$x_i x_j$
and the edge ideal is generated by all such monomials.
The connection with Stanley–Reisner theory arises through the independence complex of
$\Gamma $
. The independence complex, denoted by
$\Delta _{\Gamma }$
, is the simplicial complex whose faces are the independent sets of
$\Gamma $
. Since the minimal nonfaces of
$\Delta _{\Gamma }$
are precisely the edges of
$\Gamma $
, the Stanley–Reisner ideal of
$\Delta _{\Gamma }$
coincides with the edge ideal of
$\Gamma $
, that is,
$ I_{\Delta _{\Gamma }} = I(\Gamma ). $
Consequently, the Stanley–Reisner ring of the independence complex is given by
$ \mathbb {K}[\Delta _{\Gamma }] = S/I(\Gamma ). $
A subset C of the vertex set
$V(\Gamma )$
of a graph
$\Gamma $
is called a vertex cover of
$\Gamma $
if for every
$v\in V(\Gamma ) $
, there exists at least one vertex
$u\in C$
such that v is adjacent to u in
$\Gamma .$
A vertex cover C of graph
$\Gamma $
is called minimal if there does not exist any cover of
$\Gamma $
which is inside
$C.$
A subset I of the vertex set
$V(\Gamma ) $
is called an independent set if the induced subgraph of
$\Gamma $
on I is an empty graph (a graph without edges). An independent set I is called maximal if for any
$v\in V(\Gamma )\setminus I$
, the induced subgraph on
$I\cup \{v\}$
is not an empty graph. Note that the set of independent sets of
$\Gamma $
forms a simplicial complex.
Definition 2.1. A graph
$\Gamma $
is said to be well-covered if all of its maximal independent sets have the same cardinality. Well-covered graphs are also called pure.
A graph
$\Gamma $
is called very well-covered if it is well-covered, has no isolated vertices and the number of vertices of
$\Gamma $
is exactly twice the size of a maximal independent set.
Let
$\Gamma $
be a graph and let
$v \in V(\Gamma )$
. A vertex
$w \in V(\Gamma )$
is called a complement of v in
$\Gamma $
if v is adjacent to w, and no vertex is adjacent to both v and w, that is, the edge
$v-w$
is not an edge of any triangle in
$\Gamma $
. In such a case, we write
$v \perp w$
. We say that
$\Gamma $
is complemented if every vertex has a complement. An end is a vertex that is adjacent to precisely one other vertex. (For more details, see [Reference Joshi and Khiste9, Reference Liu and Wu11].)
2.2 Basics of poset theory
For the basic terminology, we follow Devhare et al. [Reference Devhare, Joshi and LaGrange4]. We also state some results used to prove our main theorems.
Let P be a poset. For any subset
$A \subseteq P$
, the upper cone of A is the set defined by
$A^{u} = \{b \in P \mid b \ge a \text { for all } a \in A \}$
, and the lower cone of A is given by
${A^{\ell } = \{b \in P \mid b \le a \text { for all } a \in A \}}$
. For a single element
$a \in P$
, we write
$a^{u}$
and
$a^{\ell }$
instead of
$\{a\}^{u}$
and
$\{a\}^{\ell }$
, respectively. The notation
$A^{u\ell }$
means
$(A^{u})^{\ell }$
and, similarly, one defines
$A^{\ell u}$
.
An element
$a \in P$
is called an atom if
$a> 0$
and there is no
$b \in P$
satisfying
${0 < b < a}$
. The poset P is said to be atomic if each nonzero element
$b \in P \setminus \{0\}$
contains an atom
$a \in P$
with
$a \le b$
.
A poset P is bounded if it has both a least element
$0$
and a greatest element
$1$
. In a bounded poset, an element
$a' \in P$
is called a complement of
$a \in P$
when
$\{a,a'\}^{\ell } = \{0\}$
and
$\{a,a'\}^{u} = \{1\}$
. An element
$b \in P$
is a pseudocomplement of a if
$\{a,b\}^{\ell } = \{0\}$
and b is the maximum element with this property; that is, b is the pseudocomplement of a exactly when
$a^{\perp } = b^{\ell }$
, where
$a^{\perp } = \{ x \in P \mid \{x,a\}^{\ell } = \{0\} \}$
. Pseudocomplements, when they exist, are unique; the pseudocomplement of a is denoted by
$a^{*}$
.
A bounded poset is called complemented (respectively pseudocomplemented) if every element has a complement
$a'$
(respectively a pseudocomplement
$a^{*}$
).
A poset P is said to be distributive if
$\{ \{a\} \cup \{b,c\}^{u} \}^{\ell } = \{ \{a,b\}^{\ell } \cup \{a,c\}^{\ell } \}^{u\ell }$
for all
$a,b,c \in P$
. This notion extends the classical definition of distributivity in lattices: a lattice is distributive in the usual sense if and only if it is distributive as a poset. A bounded poset that is both distributive and complemented is called Boolean (see [Reference Halaš6]). Every Boolean algebra is therefore a Boolean poset, though the converse does not necessarily hold.
It is a standard fact that in a Boolean poset, complementation coincides with pseudocomplementation [Reference Joshi and Khiste9, Lemma 2.4]. Thus, if P is Boolean, it is pseudocomplemented and each
$x \in P$
has a unique complement
$x'$
. For any undefined terminology, we refer to [Reference Devhare, Joshi and LaGrange4, Reference Grätzer5, Reference West18].
Next, we present several results on Cohen–Macaulay graphs and the zero-divisor graph of a Boolean poset P, which will be essential in proving our main results.
Lemma 2.2 [Reference Mahmoudi, Mousivand, Crupi, Rinaldo, Terai and Yassemi13, Lemma 3.1]
Let
$\Gamma $
be a very well-covered graph with
$2 h$
vertices. Then, the following conditions are equivalent.
-
(1) The graph
$\Gamma $
is Cohen–Macaulay. -
(2) There is a relabelling of vertices
$V(\Gamma )=\{x_1, \ldots , x_h, y_1, \ldots , y_h\}$
such that the following five conditions hold:-
(a)
$\{x_1, \ldots , x_h\}$
is a minimal vertex cover of
$\Gamma $
and
$\{y_1, \ldots , y_h\}$
is a maximal independent set of
$\Gamma $
; -
(b)
$\{x_1, y_1\}, \ldots ,\{x_h, y_h\} \in E(\Gamma )$
; -
(c) if
$\{z_i, x_j\},\{y_j, x_k\} \in E(\Gamma )$
, then
$\{z_i, x_k\} \in E(\Gamma )$
for distinct
$i, j, k$
and for
${z_i \in \{x_i, y_i\}}$
; -
(d) if
$\{x_i, y_j\} \in E(\Gamma )$
, then
$\{x_i, x_j\} \notin E(\Gamma )$
; -
(e) if
$\{x_i, y_j\} \in E(\Gamma )$
, then
$i \leq j$
.
-
Theorem 2.3 [Reference Joshi and Khiste9, Theorem 2.4]
If P be a Boolean poset, then every vertex of
$\Gamma (P)$
has a unique complement in
$\Gamma (P).$
Lemma 2.4 [Reference Joshi and Khiste9, Lemma 2.2]
Let P be a Boolean poset. Then,
$b \ (\ne 1)$
is an atom if and only if its complement
$b'$
is the unique end adjacent to b in
$\Gamma (P)$
.
3 Cohen–Macaulayness of the zero-divisor graph of a Boolean poset
It is well known that every Cohen–Macaulay graph is necessarily well-covered (see, for example, [Reference Stanley14, Reference Villarreal16]). Consequently, to investigate the Cohen–Macaulayness of the zero-divisor graph
$\Gamma (P)$
, it is essential first to determine whether
$\Gamma (P)$
is well-covered. The following theorem provides the well-coveredness of
$\Gamma (P)$
in case P is a Boolean poset.
Throughout the paper, unless otherwise specified,
${P}$
denotes a finite Boolean poset with at least two atoms.
Theorem 3.1. The zero-divisor graph of a Boolean poset is very well-covered.
Proof. Let
$\Gamma (P)$
be a zero-divisor graph of a Boolean poset P. We prove that all maximal independent vertex sets of
$\Gamma (P)$
have the same cardinality, namely
${|V(\Gamma (P))|}/{2}$
. Consequently,
$\Gamma (P)$
is very well-covered.
Since P is a Boolean poset, every element has a unique complement. Hence,
$|V(\Gamma (P))| = 2t$
, where t is the number of complementary pairs in P. Moreover, for each vertex
$a \in V(\Gamma (P))$
, its complement
$a'$
also belongs to
$V(\Gamma (P))$
. Thus, the vertex set can be decomposed as
$$ \begin{align*} V(\Gamma(P)) = B \cup B', \quad B = \{a_1,a_2,\ldots,a_t\}, \quad B' = \{a_1',a_2',\ldots,a_t'\}, \end{align*} $$
with
$B \cap B' = \varnothing $
. It follows that the cardinality of any independent set cannot exceed the number of complementary pairs. In particular, if
$S = \{a_1,a_2,\ldots ,a_s\}$
is an independent set of
$\Gamma (P)$
, then
$$ \begin{align*} |S| \leq t. \end{align*} $$
We now show that if
$|S| < t$
, then S can be extended to a larger independent set until
$|S| = t$
. Since
$|S| < t$
, there exists at least one complementary pair
$\{a_{s+1},a_{s+1}'\}$
such that
$$ \begin{align*} \{a_{s+1},a_{s+1}'\} \cap S = \varnothing. \end{align*} $$
We claim that at least one of
$S \cup \{a_{s+1}\}$
or
$S \cup \{a_{s+1}'\}$
remains an independent set.
Suppose in contrast that neither is independent. Then, there exist distinct vertices
$a_i,a_j \in S$
such that
$$ \begin{align*} \{a_i,a_{s+1}\}^\ell = \{0\} \quad \text{and} \quad \{a_j,a_{s+1}'\}^\ell = \{0\} \end{align*} $$
for some
$i,j \in \{1,2,\ldots ,s\}$
. If
$a_i = a_j$
, then
$\Gamma (P)$
would contain a triangle
$$ \begin{align*} a_{s+1} - a_i\ (=a_j) - a_{s+1}' - a_{s+1}, \end{align*} $$
contradicting Theorem 2.3, since
$a_{s+1}'$
is the complement of
$a_{s+1}$
in
$\Gamma (P)$
.
Thus,
$a_i \neq a_j$
. As P is pseudocomplemented, the relations
$\{a_i,a_{s+1}\}^\ell = \{0\}$
and
$\{a_j,a_{s+1}'\}^\ell = \{0\}$
imply that
$a_i \leq a_{s+1}'$
and
$a_j \leq a_{s+1}$
. However, since
$\{a_{s+1},a_{s+1}'\}^\ell = \{0\}$
, we obtain
$\{a_i,a_j\}^\ell = \{0\}$
, which contradicts the assumption that
$a_i$
and
$a_j$
are both in the independent set S.
Hence, at least one of
$a_{s+1}$
or
$a_{s+1}'$
can be added to S, enlarging it. By repeating this process, S can always be extended until
$|S| = t$
. Therefore, every maximal independent set of
$\Gamma (P)$
has size
$t = {|V(\Gamma (P))|}/{2}$
, and hence,
$\Gamma (P)$
is very well-covered.
Example 3.2. In Figure 1, P denotes a Boolean poset and
$\Gamma (P)$
is the corresponding zero-divisor graph. Consider the simplicial complex of independent sets of
$\Gamma (P)$
, denoted by
$\Delta _{\Gamma (P)}$
. We have
$$ \begin{align*} \Delta_{\Gamma(P)} = \langle \{q_1,q_2',q_3',q_4'\}, \{q_2,q_1',q_3',q_4'\}, \{q_3,q_1',q_2',q_4'\}, \{q_4,q_1',q_2',q_3'\}, \{q_1',q_2',q_3',q_4'\} \rangle. \end{align*} $$
It is evident that all facets of
$\Delta _{\Gamma (P)}$
have the same cardinality. Therefore,
$\Delta _{\Gamma (P)}$
is a well-covered simplicial complex. Hence,
$\Gamma (P)$
is well-covered.
The Boolean poset P and its zero-divisor graph
$\Gamma (P)$
.
To prove that
$\Gamma (P)$
is a Cohen–Macaulay graph, we introduce the following definition for elements of a Boolean poset P.
Definition 3.3. The weight (wt) of an element x in a finite bounded poset P is defined as the number of atoms lying below x.
The weight of an element x will be denoted by wt(x). Clearly, every atom has weight 1 and the weight of a poset P, denoted by wt(P), is the weight of the greatest element 1 ∈ P. The weight of a vertex v ∈Γ(P) is defined as the weight of the element v in P.
Let
$B_i$
be the set of all elements in P with weight
$k-i$
, where k is the number of atoms of a Boolean poset P. One can verify that
$B_1$
and
$B_3$
are nonempty and
$B_2$
is empty in the case of the Boolean poset depicted in Figure 1.
Lemma 3.4. Let P be a Boolean poset and let
$x \in P$
. Then,
$x^{\prime }$
is the complement of x if and only if
$ \operatorname {wt}(x^{\prime }) = \operatorname {wt}(P)-\operatorname {wt}(x) \ \text {and}\ \{x,x^{\prime }\}^{\ell }=\{0\}. $
Proof. Let P be a Boolean poset with atoms
$\{p_1, p_2, \ldots , p_k\}$
and let
$x \in P$
have
$\operatorname {wt}(x) = t$
. As
$\operatorname {wt}(x) = t$
, consider the set
$\{p_{i_1}, p_{i_2}, \ldots , p_{i_t}\}$
of t atoms lying below x, where
$\{i_1, i_2, \ldots , i_t\} \subseteq \{1, 2, \ldots , k\}$
. Similarly, let
$\{p_{j_1}, p_{j_2}, \ldots , p_{j_{\operatorname {wt}(x')}}\}$
be the set of atoms lying below
$x'$
, the unique complement of x.
Now, suppose that
$\operatorname {wt}(x')> k - t$
. Then, there exists at least one atom, say
$p_s$
, that is common to both sets
$\{p_{i_1}, p_{i_2}, \ldots , p_{i_t}\}$
and
$\{p_{j_1}, p_{j_2}, \ldots , p_{j_{\operatorname {wt}(x')}}\}$
. Hence,
$p_s \leq x$
and
$p_s \leq x'$
, which implies that
$\{p_s\} \subseteq \{x, x'\}^{\ell } \neq \{0\}$
and contradicts the fact that
$x'$
is the complement of x. Therefore,
$\operatorname {wt}(x') \leq k - t$
.
Next, suppose
$\operatorname {wt}(x') < k - t$
. Then, there exists an atom
$p_q$
that is not below either x or
$x'$
. Consequently,
$\{x, p_q\}^{\ell } = \{0\} = \{x', p_q\}^{\ell }$
, which implies that the edge x–
$x'$
forms an edge of a triangle and contradicts Theorem 2.3. Thus,
$\operatorname {wt}(x') = k - t = \operatorname {wt}(P) - \operatorname {wt}(x)$
. Clearly,
$\{x, x'\}^\ell =\{0\}$
. Thus, the condition is verified.
Conversely, suppose
$\operatorname {wt}(x') = \operatorname {wt}(P)-\operatorname {wt}(x) = k - t$
and
$\{x,x'\}^{\ell } = \{0\}$
. Then, no atom lies below both x and
$x'$
, and the total number of atoms below x and
$x'$
is
$t+(k-t)=k$
.
Finally, let
$y \in \{x, x'\}^{u}$
. Then, y must lie above all k atoms of P and hence,
$y = 1$
. Therefore,
$\{x, x'\}^{u} = \{1\}$
, showing that
$x'$
is a complement of x. Since P is Boolean, this complement is unique.
Let P be a poset with
$0$
. The poset P is called weakly section semi-complemented if, for
$a, b \in P$
and
$a<b$
, there exists
$c \in P$
such that
$0<c \leq b$
and
$\{a,c\}^{\ell }=\{0\}$
. Further, P is said be section semi-complemented if, for
$a, b \in P$
with
$b \not \leq a$
, there exists
$c \in P$
such that
$0<c \leq b$
and
$\{a,c\}^{\ell }=\{0\}$
. Clearly, every section semi-complemented poset is weakly section semi-complemented. A finite bounded section semi-complemented poset is called atomistic.
Lemma 3.5. Every uniquely complemented poset is weakly section semi-complemented.
Proof. Let P be a uniquely complemented poset and let
$a < b$
for
$a, b \in P$
. Consider the complement
$a'$
of a in P. If
$\{a', b\}^\ell =\{0\}$
, then a will have two complements namely
$a'$
and b, as we have
$\{1\}=\{a, a'\}^u \subseteq \{b, a'\}^u$
. Hence,
$\{a', b\}^\ell \not =\{0\}$
. Choose any
$c \in \{a', b\}^\ell =\{0\}$
. Then,
$0< c \leq b$
and
$\{c,a\}^\ell =\{0\}$
. This shows that every uniquely complemented poset is weakly section semi-complemented.
The converse of Lemma 3.5 is not true (see Waphare and Joshi [Reference Waphare and Joshi17, Figure 1]).
Corollary 3.6. Let P be a Boolean poset and
$a, b \in P$
such that
$a < b$
. Then,
$\operatorname {wt}(a) < \operatorname {wt}(b)$
.
Proof. In the proof of Lemma 3.5, take any atom below c, say p. Then, p will be below b but not a. Thus,
$\operatorname {wt}(a) < \operatorname {wt}(b)$
.
Waphare and Joshi [Reference Waphare and Joshi17, Figure 1] show that a uniquely complemented poset need not be section semi-complemented. However, for a Boolean poset, this assertion is true.
Lemma 3.7. Every Boolean poset P is section semi-complemented. In particular, if P is finite, then it is atomistic.
Proof. Suppose
$a \nleq b$
. We claim that
$\{a,b'\}^{\ell } \setminus \{0\} \neq \varnothing $
. Suppose in contrast that
$\{a,b'\}^{\ell } = \{0\}$
. Then, we have
$a \leq b"=b$
, which is a contradiction, as P is a Boolean poset and, hence, it is pseudocomplemented. Hence,
$\{a,b'\}^{\ell } \setminus \{0\} \neq \varnothing $
. Therefore, there exists a nonzero element
$c \in P$
such that
$c \leq a$
and
$c \leq b'$
, giving
$c \nleq b$
.
Since P is finite, there exists an atom p with
$0 < p \leq c$
. Then,
$p \leq a$
and
$p \leq b'$
, that is,
$\{p, b\}^\ell =\{0\}$
.
With the above preparation, we are ready to prove Theorem 1.2 restated as follows.
Theorem 3.8. If P is a Boolean poset, then
$\Gamma (P)$
is Cohen–Macaulay.
Proof. Let P be a Boolean poset and
$\operatorname {wt}(P)=k.$
By Theorem 3.1, the cardinality of every maximal independent set is equal to the number of complementary pairs in P, say t. Also, note that
$t={|V(\Gamma (P))|}/{2}$
. If
$k=2$
, then
$\Gamma (P)$
is
$K_2$
and in this case, the result is true. Hence, assume that
$k>2$
.
First, let us construct a maximal independent set B of
$\Gamma (P).$
Suppose that the weight k of the poset is odd. For
$1\leq i\leq {(k-1)}/{2}$
, define
$B_i$
to be the set of all elements in P with weight
$k-i.$
Let
$B_1=\{y_1,y_2,\ldots ,y_k\}$
be the set of elements of weight
$k-1$
. Clearly,
$B_1\neq \emptyset $
, as P has at least two atoms and
$B_1$
contains all the dual atoms of P. For
$2\leq i\leq k-2$
, there is no guarantee that P contains an element of weight
$k-i$
, so some
$B_i$
may be empty.
Now, suppose that k is even. For
$i={k}/{2}$
, define the set
$B_i=\widehat {B}$
. If there are complementary pairs of weight
${k}/{2}$
, then the set
$B_i=\widehat {B}$
contains one element from each complementary pair.
Now, set
$$ \begin{align*} B = \begin{cases} B_1 \cup B_2 \cup \cdots \cup B_{{(k-1)}/{2}} & \text{if } k \text{ is odd},\\[4pt] B_1 \cup B_2 \cup \cdots \cup B_{{(k-2)}/{2}} \cup \widehat{B} & \text{if }k \text{ is even.} \end{cases} \end{align*} $$
We claim that the set B is a maximal independent set.
Suppose that k is even. Observe that the weight of each element in B is greater than or equal to
${k}/{2}$
. Let
$x,y\in B$
. Then,
$\operatorname {wt}(x)+\operatorname {wt}(y)\geq k$
. If equality holds, then necessarily
$\operatorname {wt}(x)=\operatorname {wt}(y)={k}/{2}$
. For x and y to be adjacent, we must have
$\{x,y\}^{\ell }=\{0\}$
, in which case, Lemma 3.4 implies that x and y form a complementary pair. However, by the construction, B contains one element from each complementary pair having weight
${k}/{2}$
, which gives a contradiction. Thus, equality does not hold. If
$\operatorname {wt}(x)+\operatorname {wt}(y)> k$
, then the sets of atoms lying below x and y intersect, and hence,
$\{x,y\}^{\ell }\neq \{0\}$
. Hence, x and y are not adjacent.
Now, assume that k is odd. Then, all the elements of B are of weight greater than or equal to
${(k+1)}/{2}$
and so any two elements
$x,y\in B$
satisfy
$\operatorname {wt}(x)+\operatorname {wt}(y)> k$
. Therefore, the sets of atoms below x and y intersect, which implies
$\{x,y\}^{\ell }\neq \{0\}$
. Thus, x and y are not adjacent.
This shows that B is an independent set. Next, we prove B is a maximal independent set. Let
$y\in V(\Gamma (P))\setminus B$
. Clearly,
$0<\operatorname {wt}(y)\leq {k}/{2}$
if k is even. If
$\operatorname {wt}(y)={k}/{2}$
, then by Lemma 3.4 and the construction of B,
$\operatorname {wt}(y^{\prime })={k}/{2}$
and
$y^{\prime }\in B$
. Since
$y'$
is the complement of y, we have
$\{y,y'\}^{\ell }=\{0\}$
, so y and
$y^{\prime }$
are adjacent. If
$\operatorname {wt}(y)=l< {k}/{2}$
, clearly,
$y^{\prime }$
is in P with
$\operatorname {wt}(y^{\prime })=k-l$
. As
$l<{k}/{2}$
, this gives
$\operatorname {wt}(y^{\prime })>{k}/{2}$
, by the construction, so
$y^{\prime }\in B$
. Again,
$\{y,y'\}^{\ell }=\{0\}$
, so y is adjacent to
$y'$
. This shows that we cannot extend the independent set B, when k is even.
Now, assume that k is odd. Then, B contains all elements of weight greater than or equal to
${(k+1)}/{2}$
. Thus, the element
$y\in V(\Gamma (P))\setminus B$
has weight at most
${(k-1)}/{2}$
. By Lemma 3.4, y has a unique complement
$y'\in B$
and
$\{y,y'\}^{\ell }=\{0\}$
, so y is adjacent to
$y'$
.
This proves the claim that B is the maximal independent set of
$\Gamma (P)$
.
As B admits no natural order, we impose one by listing the elements of
$B_1, B_2, \ldots $
successively and, when k is even, listing
$\widehat {B}$
last. The ordering within each subset is arbitrary and serves only for labelling purposes. With this relabelling, write
$$ \begin{align*} B=\{x_1^{\prime},x_2^{\prime},\ldots,x_t^{\prime}\}. \end{align*} $$
Introduce the set
$$ \begin{align*} A=V(\Gamma(P))\setminus B=\{x_1,x_2,\ldots,x_t\} \end{align*} $$
such that
$x_i^{\prime }$
is the complement of
$x_i$
for all
$i=1,2,\ldots ,t$
and
$V(\Gamma (P))=A\cup B$
.
To complete the proof and show that
$\Gamma (P)$
is Cohen–Macaulay, we show that this labelling satisfies the conditions given in Lemma 2.2.
Condition (a). Since the complement of any maximal independent set is a minimal vertex cover, the set A is a minimal vertex cover of
$\Gamma (P).$
Condition (b). Since
$\{x_i,x_i^{\prime }\}^{\ell }=\{0\}$
, it follows that
$x_i$
is adjacent to
$x_i^{\prime }$
in
$\Gamma (P)$
for each
$i=1,2,\ldots ,t$
.
Condition (c). Assume that
$\{z_i,x_j\}, \{x_j^{\prime },x_k\} \in E(\Gamma (P))$
for
$z_i \in \{x_i, x_i^\prime \}$
. Then,
$\{z_i,x_j\}^\ell =\{0\}=\{x_k, x_j^\prime \}^\ell $
. Since P is Boolean, it is pseudocomplemented and unique complementation coincides with pseudocomplementation, and so
$x_j^{\prime }$
is the pseudocomplement of
$x_j$
. Further,
$\{z_i,x_j\}^\ell =\{0\}$
, so
$z_i\leq x_j^{\prime }$
. Similarly,
$x_k\leq x_j^{\prime \prime }=x_j.$
This implies that
${\{z_i,x_k\}^{\ell }=\{0\}.}$
Therefore,
$\{z_i,x_k\}$
is an edge in
$\Gamma (P)$
.
Condition (d). Suppose
$\{x_i,x_j^{\prime }\}\in E(\Gamma (P))$
. Then,
$\{x_i,x_j^{\prime }\}^\ell =\{0\}$
. This gives
$x_i \leq x_j^{\prime \prime }=x_j$
. Hence,
$\{x_i,x_j\}\notin E(\Gamma (P))$
.
Condition (e). Assume that
$\{x_i,x_j^{\prime }\}\in E(\Gamma (P))$
. Then,
$\{x_i,x_j^{\prime }\}^\ell =\{0\}$
. We claim that
$i\leq j$
. Suppose, for a contradiction, that
$i>j$
. By the relabelling,
$\operatorname {wt}(x_i^\prime ) \leq \operatorname {wt}(x_j^\prime )$
. As
$x_i^\prime $
is the unique complement of
$x_i$
in P,
$\operatorname {wt}(x_i)+\operatorname {wt}(x_i^\prime )=k$
and so
$\operatorname {wt}(x_i)+\operatorname {wt}(x_j^\prime )\geq k$
. If equality holds, then Lemma 3.4 together with
$\{x_i,x_j'\}^{\ell }=\{0\}$
implies that
$x_j^\prime $
is a complement of
$x_i$
, which contradicts uniqueness. If
$\operatorname {wt}(x_i)+\operatorname {wt}(x_j^\prime )> k$
, then the sets of atoms below
$x_i$
and
$x_j'$
intersect, and hence,
$\{x_i,x_j^\prime \}^{\ell }\neq \{0\}$
, which contradicts
$\{x_i,x_j^\prime \}\in E(\Gamma (P))$
. Hence,
$i\leq j$
.
All the conditions of Lemma 2.2 are satisfied and
$\Gamma (P)$
is Cohen–Macaulay.
As an immediate consequence of the above result, we have the following result proved by Liu and Wu in [Reference Liu and Wu11].
Corollary 3.9. The zero-divisor graph of a Boolean algebra (equivalently Boolean ring) is Cohen–Macaulay.
Since the simplicial complex of independent sets of a graph G coincides with the simplicial complex of cliques in its complement
$G^c$
, we further deduce the following corollary.
Corollary 3.10. The complement
$\Gamma ^c(P)$
of the zero-divisor graph of a Boolean poset P is Cohen–Macaulay with its clique complex.
In general, the converses of Theorems 3.1 and 3.8 do not hold. The following example serves as a counterexample.
Example 3.11. Consider a bounded poset P, having three atoms say
$a,b,c$
covered by
$1$
. This is not a Boolean poset, but the corresponding zero-divisor graph is the complete graph
$K_3$
. Hence, it is well-covered and Cohen–Macaulay.
Next, we prove the converse of Theorem 3.8 for a special class of posets. For this purpose, we introduce some notation and definitions given in [Reference Khandekar and Joshi10], which we will use to prove the results.
The direct product of posets
$P_1,\ldots ,P_n$
is the poset
$\textbf {P}=\prod _{i=1}^nP_i$
with
$\leq $
defined such that
$a\leq b$
in
$\textbf {P}$
if and only if
$a_{i}\leq b_{i}$
(in
$P_i$
) for every
$i\in \{1,\ldots ,n\}$
. If
$\emptyset \neq A\subseteq \prod _{i=1}^nP_i$
, then
$A^u=\{b\in \prod _{i=1}^nP_i\ | \ b_{i}\geq a_{i}$
for every
$a\in A$
and
$i\in \{1,\ldots ,n\}\}$
. Similarly, we have
$A^\ell =\{b\in \prod _{i=1}^nP_i \ | \ b_{i}\leq a_{i}$
for every
$a\in A$
and
$i\in \{1,\ldots ,n\}\}$
.
Throughout the rest of this section,
$ \mathbf { P}=\prod _{i=1}^{n}P_i$
with
$n\geq 2$
, where the
$P_i$
are finite bounded posets such that
$Z(P_i)=\{0\}$
for all i and
$2\leq |P_1|\leq |P_2|\leq \cdots \leq |P_n|$
. Since the
$P_{i}$
are finite bounded posets, they are atomic. Note that
$Z(P_i)=0$
if and only if
$P_i$
has a unique atom. In that case, let
$q_{_i}\in P_i$
be the unique atom of
$P_i$
.
We denote the elements of
$ \mathbf { P}$
by bold letters. Let
$\mathbf {x}=(x_{1},x_{2},\ldots ,x_{n})\in \mathbf { P} $
, where
$x_i\in P_i$
. In particular,
$\mathbf {q}_{_1},\mathbf {q}_{_2},\ldots , \mathbf {q}_{_n}$
are the only atoms of
$ \mathbf { P}$
and we have
${\mathbf {q}_{_{i}}=(0,\ldots ,0,q_{_i},0,\ldots ,0)}$
. We observe that
$(0,0,\ldots ,0),(1,1,\ldots ,1)\in \mathbf { P}$
are the least and the greatest elements of
$ \mathbf { P}$
denoted by
$\mathbf {0}$
and
$\mathbf {1}$
, respectively. We set
$D = \mathbf {P}\setminus Z(\mathbf {P}).$
The elements
$d \in D $
are the dense elements of
$\mathbf {P}$
.
Theorem 3.12. Let
$ \mathbf { P}=\prod _{i=1}^{2}P_i$
, where the
$P_i$
are finite bounded posets such that
$Z(P_i)=\{0\}$
for each i and
$2\leq |P_1|\leq |P_2|$
. Then, the following statements are equivalent:
-
(1)
$\Gamma (\mathbf {P})$
is Cohen–Macaulay; -
(2)
$|P_1|=|P_2|=2$
, therefore,
$\mathbf {P}$
is a Boolean lattice.
Proof.
$(1)\Rightarrow (2)$
. Observe that
$\Gamma (\mathbf {P})$
is a complete bipartite graph
$K_{|P_1|-1,|P_2|-1}$
, which is Cohen–Macaulay only if
$|P_1|=|P_2|=2.$
$(2)\Rightarrow (1)$
. If
$|P_1|=|P_2|=2$
, then
$\Gamma (\mathbf {P})=K_2$
, which is Cohen–Macaulay.
Lemma 3.13. Let
$ \mathbf { P}=\prod _{i=1}^{n}P_i \ (n\geq 3)$
, where the
$P_i$
are finite bounded posets such that
$Z(P_i)=\{0\}$
for all i and
$2\leq |P_1|\leq |P_2|\leq \cdots \leq |P_n|$
. Let
$\mathbf {q}_1, \mathbf {q}_2, \ldots , \mathbf {q}_n$
be all the atoms of
$\mathbf {P}$
. For
$1\leq i<j<k\leq n$
, define
$$ \begin{align*} \mathfrak{J}_{i,j,k} \;= \{\, \mathbf{x} \in \mathbf{P} \mid \mathbf{x} \in \{\mathbf{q}_i,\mathbf{q}_j\}^u \ \text{or}\ \mathbf{x} \in \{\mathbf{q}_j,\mathbf{q}_k\}^u \ \text{or}\ \mathbf{x} \in \{\mathbf{q}_i,\mathbf{q}_k\}^u \}\setminus D. \end{align*} $$
Then,
$\mathfrak {J}_{i,j,k}$
is a maximal independent set in
$\Gamma (\mathbf {P})$
.
Proof. Let
$\mathbf {x},\mathbf {y}\in \mathfrak {J}_{i,j,k}$
. We first show that
$\{\mathbf {x},\mathbf {y}\}^{\ell }\neq \{\mathbf {0}\}$
. It suffices to consider two cases.
Case I. Assume that
$\mathbf {x},\mathbf {y}\in \{\mathbf {q}_i,\mathbf {q}_j\}^u$
. Then,
$\{\mathbf {q}_i,\mathbf {q}_j\}\subseteq \{\mathbf {x},\mathbf {y}\}^{\ell }\neq \{\mathbf {0}\}.$
Case II. Assume that
$\mathbf {x}\in \{\mathbf {q}_i,\mathbf {q}_j\}^u$
and
$\mathbf {y}\in \{\mathbf {q}_j,\mathbf {q}_k\}^u$
. Then,
$\{\mathbf {q}_j\}\subseteq \{\mathbf {x},\mathbf {y}\}^{\ell }\neq \{\mathbf {0}\}.$
In both cases,
$\{\mathbf {x},\mathbf {y}\}^{\ell }\neq \{\mathbf {0}\}$
, which means no two vertices of
$\mathfrak {J}_{i,j,k}$
are adjacent in
$\Gamma (\mathbf {P})$
. Hence,
$\mathfrak {J}_{i,j,l}$
is an independent set.
Next, we prove maximality of
$\mathfrak {J}_{i,j,k}$
. Let
$\mathbf {w}=(x_1,x_2,\ldots ,x_n)\in V(\Gamma (\mathbf {P}))\setminus \mathfrak {J}_{i,j,k}$
. Then,
$\mathbf {w}\notin \{\mathbf {q}_i,\mathbf {q}_j\}^u$
,
$\mathbf {w}\notin \{\mathbf {q}_j,\mathbf {q}_k\}^u$
and
$\mathbf {w}\notin \{\mathbf {q}_i,\mathbf {q}_k\}^u$
. Without loss of generality, assume that
$ \mathbf {q}_i \nleq \mathbf {w} $
and
$\mathbf {q}_j \nleq \mathbf {w}$
, so that
$x_i=0=x_j$
. Consider the element
${\mathbf {x}=(0,\ldots ,0,q_i,\ldots ,q_j,0,\ldots ,0)}$
. Then,
$\mathbf {x}\in \{\mathbf {q}_i,\mathbf {q}_j\}^u \subseteq \mathfrak {J}_{i,j,k}$
. Further,
$\{\mathbf {x},\mathbf {w}\}^\ell = \{0\}$
. This means
$\mathbf {x}$
and
$\mathbf {w}$
are adjacent in
$\Gamma (\mathbf {P})$
. Therefore,
$\mathbf {w}$
is adjacent to at least one vertex of
$\mathfrak {J}_{i,j,k}$
, so that
$\mathfrak {J}_{i,j,k}\cup \{\mathbf {w}\}$
is not an independent set. Hence,
$\mathfrak {J}_{i,j,k}$
is a maximal independent set in
$\Gamma (\mathbf {P})$
.
The proof of the next result follows the same ideas as the proof of [Reference Asir, Cheri, Pournaki and Poursoltani2, Theorem 3.5], but rewritten in the language of poset theory.
Theorem 3.14. Let
$ \mathbf { P}=\prod _{i=1}^{n}P_i \ (n\geq 3)$
, where the
$P_i$
are finite bounded posets such that
$Z(P_i)=\{0\}$
for all i and
$2\leq |P_1|\leq |P_2|\leq \cdots \leq |P_n|$
. Then, the zero-divisor graph
$\Gamma (\mathbf {P})$
is well-covered if and only if
$|P_i|=2$
for all
$i=1,2,\ldots ,n$
.
Proof. If
$|P_i|=2$
for all
$i=1,2,\ldots ,n$
, then P is a Boolean poset. By Theorem 3.1, it follows that
$\Gamma (P)$
is well-covered.
Conversely, suppose that
$\Gamma (\mathbf {P})$
is well-covered, that is, all its maximal independent sets have the same cardinality.
Let
$\mathbf {q}_{_1},\mathbf {q}_{_2},\ldots , \mathbf {q}_{_n}$
be the atoms of
$\mathbf {P}$
. For each atom
$\mathbf {q}_i$
, consider the maximal independent set
$\mathfrak {J}_i=\{\mathbf {q}_i\}^u\setminus D=\{(x_1,\ldots ,x_k)\in \mathbf {P}\mid x_i\neq 0\}\setminus D$
, where D denotes the set of dense elements of
$\mathbf {P}$
. Since
$ |D|=(|P_1|-1)(|P_2|-1)\cdots (|P_n|-1), $
we obtain
$ |\mathfrak {J}_i|=\bigl (|P_1||P_2|\cdots (|P_i|-1)\cdots |P_n|\bigr )-\bigl ((|P_1|-1)(|P_2|-1)\cdots (|P_n|-1)\bigr ). $
As
$\Gamma (\mathbf {P})$
is well-covered,
$|\mathfrak {J}_i|=|\mathfrak {J}_j|$
for all
$i\neq j$
. Substituting the expressions for
$|\mathfrak {J}_i|$
and
$|\mathfrak {J}_j|$
, and simplifying gives
$(|P_i|-1)|P_j|=(|P_j|-1)|P_i|$
, that is,
$|P_i|=|P_j|$
. Hence,
$|P_1|=|P_2|=\cdots =|P_n|=\alpha $
(say).
It remains to show that
$\alpha =2$
. Consider the maximal independent set
$\mathfrak {J}_{1,2,3} $
from Lemma 3.13. Write
$\mathfrak {J}_{1,2,3}=A\cup B\cup C$
, where
$A=\{\mathbf {x}\in \mathbf {P}\mid \mathbf {x}\in \{\mathbf {q}_1,\mathbf {q}_2\}^u\}\setminus D$
,
$B=\{\mathbf {x}\in \mathbf {P}\mid \mathbf {x}\in \{\mathbf {q}_2,\mathbf {q}_3\}^u\}\setminus D$
and
$C=\{\mathbf {x}\in \mathbf {P}\mid \mathbf {x}\in \{\mathbf {q}_1,\mathbf {q}_3\}^u\}\setminus D$
. By the principle of inclusion–exclusion,
$$ \begin{align*} |\mathfrak{J}_{1,2,3}|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|. \end{align*} $$
Note that
$$ \begin{align*} |A|=|B|=|C|=(\alpha-1)^2\alpha^{n-2}-(\alpha-1)^n \end{align*} $$
and
$$ \begin{align*} |A\cap B|=|A\cap C|=|B\cap C|=|A\cap B\cap C|=(\alpha-1)^3\alpha^{n-3}-(\alpha-1)^n. \end{align*} $$
Thus,
$$ \begin{align*} |\mathfrak{J}_{1,2,3}|=3((\alpha-1)^2\alpha^{n-2}-(\alpha-1)^n)-2((\alpha-1)^3\alpha^{n-3}-(\alpha-1)^n). \end{align*} $$
However,
$$ \begin{align*} |\mathfrak{J}_1|=(\alpha-1)\alpha^{n-1}-(\alpha-1)^n. \end{align*} $$
Since,
$\Gamma (\mathbf {P})$
is well-covered,
$|\mathfrak {J}_{1,2,3}|=|\mathfrak {J}_1|$
. Equating the two expressions,
$$ \begin{align*} 3(\alpha-1)^2\alpha^{n-2}-2(\alpha-1)^3\alpha^{n-3}=(\alpha-1)\alpha^{n-1}. \end{align*} $$
Dividing through by
$\alpha ^{n-3}>0$
, we obtain
$$ \begin{align*} 3(\alpha-1)\alpha-2(\alpha-1)^2-\alpha^2=0, \end{align*} $$
which simplifies to
$ \alpha -2=0. $
Thus,
$\alpha =2$
, which completes the proof.
Proof of Theorem 1.3
$(1)\Rightarrow (2)$
. Every Cohen–Macaulay graph is well-covered.
$(2)\Rightarrow (3)$
. This follows from Theorem 3.14.
$(3)\Rightarrow (4)$
. Let
$ \mathbf { P}=\prod _{i=1}^{n}P_i$
(
$n\geq 3$
), where
$|P_i|=2$
for all
$i=1,2,\ldots ,n.$
Then, each
$P_i$
is a
$2$
-element chain, so that
$\mathbf {P}$
is a Boolean lattice.
$(4)\Rightarrow (5)$
. Every Boolean lattice is a Boolean poset.
$(5)\Rightarrow (1)$
. From Theorem 3.8,
$\Gamma (\mathbf {P})$
is Cohen–Macaulay.
Acknowledgement
The authors sincerely thank the referee for a meticulous evaluation of the manuscript. The constructive feedback provided was instrumental in improving the final presentation of the paper.
