Definition. Let $G$ be a graph then subsets $S$ and $T$ are strongly adjacent iff \[ \forall s \in S, t \in T: s \sim t \] Let $\wp(S)^2$ be the product lattice of the power set of $S$. Then it can shown that strong adjacency is hereditary within this lattice.
Proposition. let $(A,B) \subseteq (C,D)$ then $C \sim D \Rightarrow A \sim B$.
Proof. $ (a,b) \in (A,B) \implies (a,b) \in (C,D) \implies a \sim b $ $\square$
The centralizer of a set $S$ is merely the largest set that is strongly adjacent to it. Thusly, we have the following two identities on strong adjacency:
Proposition. let $A \sim B$ then $A \subseteq Centralizer(B)$ and $B \subseteq Centralizer(A)$.
The centralizer is the intersection of all centralizers of individual elements, so it is a semilattice homomorphism from unions to intersections.
Lemma 1. $A \subseteq Centralizer(Centralizer(A))$
Proof. the centralizer of a set is the largest set that forms a strongly adjacent pair with it. Therefore, $(A,Centralizer(A))$ form a strongly adjacent pair. The centralizer of a set must be larger then any set that forms a strongly adjacent pair with it so $A \subseteq Centralizer(Centralizer(A))$. $\square$
Lemma 2. the centralizer : $\wp(G) \to \wp(G)$ is antitone.
Proof. let $S \subseteq T$ be subsets of $G$ then \[ Centralizer(T) = Centralizer(S) \cap Centralizer(T-S) \subseteq Centralizer(S) \] Therefore, $Centralizer(T) \subseteq Centralizer(S)$. $\square$
Lemma 3. $Centralizer(Centralizer(Centralizer(A))) \subseteq Centralizer(A)$.
Proof. by lemma 1 we have that $A \subseteq Centralizer(Centralizer(A))$. By lemma two, application of centralizer to both sides reverses this inequality. $\square$
These three basic lemmas are the building blocks for the characterization theorem of the centralizer function and its associated centralizer lattice.
Definition. let $Centralizer : \wp(A) \to \wp(A)$ be the centralizer function. The the centralizer lattice $L$ is the image of this function.
The centralizer function can clearly be restricted to the centralizer lattice, which produces a special action which is the subject of our theorem today.
Theorem. the edges of the centralizer function on $L$ are the maximal strongly adjacent pairs of $G$
Proof. (1) let $(A,B)$ be a maximal strongly adjacent pair, then $A \subseteq Centralizer(B)$ and $B \subseteq Centralizer(A)$ by the definition of centralizers. By maximality, $Centralizer(B) \subseteq A$ and $Centralizer(A) \subseteq B$. Thusly, $Centralizer(A) = B$ and $Centralizer(B) = A$ so that $A$ and $B$ are both centralizers of one another.
(2) let $L$ be the centralizer lattice and let $C \in L$. It will be shown that $(C,Centralizer(C))$ forms a strongly adjacent pair. By the fact that $C$ is a centralizer there exists $A$ such that $C=Centralizer(A)$. Then consider the pair $(Centralizer(A),Centralizer(Centralizer(A))$. The later of these is maximal by the definition of the centralizer. The former is maximal by lemma three. $\square$
Not only does this describe the effect of the centralizer function, it describes it on the level of individual edges and it relates it to strong adjacency. By the fact that strong adjacency is hereditary, we could expect that it was fully determined by its maximal elements. These are precisely the edges of the centralizer action on the centralier lattice.
The relation of strong adjacency is symmetric, so the set of all maximal strongly adjacent pairs is symmetric. The centralizer action merely switches between the two elements of a strongly adjacent pair. It follows that it is an involution. As the centralizer is antitone, it forms a isomorphism from $L$ to its dual.
Corollary. the centralizer lattice is self-dual
This is the one thing we can say for sure about the centralizer lattices of graphs in general. The centralizer lattice is generated by all element centralizers, so one other issue worthy of examination is the meet irreducibles of a centralizer lattice.
Proposition. let $centralizer(a) = centralizer(B)$ then a is a lower bound of each $B$ in the adjacency preorder.
Proof. let $b \in B$ then by the fact that the centralizer is antitone, $centralizer(B) \subseteq centralizer(b)$ so by simple substitution $centralizer(a) \subseteq centralizer(b)$ whence $a \subseteq b$ with respect to the adjacency preordering. $\square$
Corollary. let $G$ be a graph with upper forest adjacency preorder, then the element centralizers are all meet irreducible elements of the centralizer lattice
Obvious examples where this is the case include triangle free graphs without leaf nodes and trivially perfect graphs. The key to constructing centralizer lattices of trivially perfect graphs is the following construction.
Definition. let $F$ be a family of lattices then the lattice theoretic disjoint union of $F$ is simply the lattice completion of the disjoint union of $F$ as posets.
The lattice congruence constructed by all identifying all the connected components and bounds separately has a height three lattice quotient.
Proposition. the centralizer lattices of trivially perfect graphs are precisely the graphs constructed from the single element lattice and repeated application of the lattice theoretic disjoint union.
Example. the following graph
has a centralizer lattice of the form
The centralizer lattices of trivially perfect graphs are planar. The centralizer lattices of graphs constructed from graph joins, like cographs can also be computed but they don't have as nice of depictions as they grow much faster. The centralizers in product graphs can also be determined componentwise.
See also:
Intersection semilattices of maximal cliques
No comments:
Post a Comment