Lemma 1. let $P$ be a poset satisfying the ACC and let $a,b \in P$ such that $\exists z : a,b \subseteq z$ then $a,b$ both share common membership in some maximal principal ideal of $P$.
Proof. let $a,b \in P$ and consider the set of upper bounds $U = \{c : a,b \subseteq c\}$. Then $z \in U$ so $U$ is not empty. By the maximal condition implied by the ACC, $U$ has maximal elements. Let $m$ be a maximal element in $U$, then $m$ is maximal in $P$. It follows that the principal ideal $\downarrow m$ is a maximal principal ideal. $\square$
The maximal principal ideals of $P$ form a sperner family, which doesn't necessarily need to be a maximal cliques family. It is a maximal cliques family provided that there is no triple of elements all of which piecewise belong in separate maximal principal ideals, such as in the six element crown. It in order to effectively reason about the bound sharing graph, we need to relate maximal prinicpal ideals to maximal cliques.
Lemma 2. let $m$ be a maximal element of $P$. Then the maximal principal ideal $\downarrow m$ is a maximal clique in the bound sharing graph.
Proof. let $m$ be maximal then any $a \sim m$ means that $a,m \subseteq z$ but $m$ is maximal so this means $a,m \subseteq z \subseteq m$ which can be reduced to $a \subseteq m$. Therefore, the neighbourhood of $m$ consists of all the elements of its principal ideal. Every element of a principal ideal is a clique of the bound sharing graph. To see that this is a maximal clique, suppose $C$ isa larger clique then $\downarrow m$ then there exists $x \not\in \downarrow m$ such that $x \sim m$ which is a contradiction. $\square$
Let $G$ be a graph, and $M$ be its hypergraph of maximal cliques. Then the degree of a vertex of the graph $G$ is different from the degree of its maximal cliques hypergraph. This leads to the following important definition:
Definition. let $G$ be a graph and $x$ a vertex of $G$. Then the maximal clique degree of $x$ is the number of maximal cliques containing $x$.
An important special case is when a vertex has maximal cliques degree one. For example, in a cluster graph every vertex must have maximal cliques degree one. These vertices have the following characterization:
Theorem. let $G$ be a graph and $x$ a vertex of $G$. Then $x$ has maximal cliques degree one iff the neighbourhood of $x$ is a clique.
Proof. (1) every clique containing $x$ is contained in the neighbourhood of $x$, because every element of clique a containing $x$ must adjacent to $x$. Therefore, if the neighbourhood $N(x)$ is a clique it is a maximal clique, since any other clique must be contianed in it.
(2) conversely, let $x$ have maximal clique degree and suppose that its neighbourhood is not a clique. Then there are elements $y,z$ such that $x \sim y,z$ and $y \not\sim z$ then $\{x,y\}$ and $\{x,z\}$ must belong to separate maximal cliques, so $x$ is not maximal clique degrees one which is a contradiction. $\square$
We saw that with respect to the bound sharing graph, the maximal elements have maximal clique degree one and they generate the entire graph. This leads to the following characterisation of bound sharing graphs:
Theorem. let $G$ be a graph then $G$ is the bound sharing graph of a poset $P$ provided that $G$ satisfies one of the following two conditions:
- $G$ is generated by its principal adjacency filter maximal cliques
- Every edge of $G$ is contained in the clique neighbourhood of some element.
(2) conversely, let $G$ be a graph that satisfies either of these two equivalent conditions. Then we can construct a poset that has $G$ as its bound sharing graph. The elements with maximal clique degree greater then one will be our minimal elements. Then for each maximal clique $M$ of $G$ create a chain containing all the degree one elements of $M$ and make it greater then all the elements of maximal clique degree greater then one in $P$. $\square$
As an application, we will characterize the zero divisor graph of a finite semilattice $S$ in terms of bound sharing. In a finite semilattice $ab = 0$ means that $a,b$ do not share an upper bound less then $0$, so it translates into the characterization of the bound sharing graph.
Proposition. let $S$ be a finite semilattice, then the zero divisor graph $ab = 0$ is the complement of the upper bound sharing graph of non-zero elements with zero adjoined as a central element with loop.
Proof. let $S$ be a finite semilattice and $G$ its zero divisor graph. Then consider the complement $G^{C}$, we have $a \sim b$ in $G^{C}$ provided that $ab \not= 0$. First of all this means $a,b \not= 0$ so the complement can be restricted to the non-zero elements. Then among the non-zero elements $ab \not= 0$ means that there exists $z \not= 0$ such that $a,b \subseteq z$. It follows that $a,b$ share a non-zero upper bound.
In other words, they share an upper bound in the upper bound sharing graph of the poset with zero removed. Conversely, if they share a non-zero upper bound then their join cannot be zero, because their join is the least upper bound and the zero element is maximal. Finally, $ab = 0$ whenever $a = 0$ or $b = 0$ so we can adjoin $0$ as a central element and it has a loop because $0$ is idempotent. $\square$
The main application of these graphs is to characterize the bound sharing graphs of finite semilattices. As the principal filters of $S$ are also subsemilattices, all the different fibers $ab = x$ of a semilattice can be characterized in this way. So by this theorem, we have fully characterized the graph-theoretic properties of semilattices.
As an example, the fibers of any finite total order $T$ as a join semilattice are all star graphs whose central vertex has a loop. In a tree the fibers are always cocluster graphs, because the upper bound sharing graph of a forest is a cluster graph. Any finite graph satisfying these conditions can be formed as the fiber of a semilattice.
No comments:
Post a Comment