Intersection semilattices of maximal cliques

Let $G$ be a graph, then the maximal cliques of the graph form a sperner family whose meet subsemilattice closure is the semilattice $M(G)$ of intersections of maximal cliques.

Example. let $A$ be a semigroup, ring, semigroup, or semiring then the maximal commuting clique intersections form a meet subsemilattice of $Sub(A)$.

The intersections of maximal cliques of $A$ are precisely the commutative subalgebras determined by the commuting graph. They produce a number of examples of commutative subalgebras in noncommutative algebra. Additionally, $M(G)$ provides an important order-theoretic account of graph properties.

Order theoretic properties of the intersection semilattice

The order types of the intersection semilattices $M(G)$ generated by maximal cliques have a complete order-theoretic classification.

Definition. let $a$,$b$ be elements of a poset then we say that $a \sim b$ provided that $\exists z: a \subseteq z \text{ and } b \subseteq z$.

Theorem. let $L$ be a meet semilattice, then it is a semilattice of intersections of the maximal cliques of a graph iff it satisfies the following two conditions:

1. $L$ is generated by its maximal elements
2. $L$ satisfies the upper bound sharing property: let $C$ be any clique in the upper bound sharing graph $\sim$ then $\exists z : \forall c \in C : c \subseteq z$.

Proof. Neccessity of condition (1): the maximal cliques of a graph always form a sperner family by maximality, so their intersections must always be generated by an antichain. In a meet semilattice, this antichain is the set of all maximal elements.

Neccessity of condition (2): let $C_1,C_2 \in M(G)$ such that $C_1 \sim C_2$, then $C_1$ and $C_2$ are contained in some common clique $D$, which means that $C_1$ and $C_2$ are adjacent. Let $F$ be a family of cliques of $M(G)$ that pairwise share upper bounds, then $F$ is pairwise adjacent, so that $\cup F$ forms a clique. There must be at least one maximal clique $\cup F \subseteq Z$ such that $\forall C \in F : C \subseteq Z$.

Constructive proof of sufficiency: let $L$ be a meet semilattice that satisfies these conditions. Then let $F$ be the maximal principal ideals of $L$. By condition (1) $F$ forms a sperner family. We can reconstruct the primal graph of the set system $F$ by $x \sim y$ if $\exists S \in F : \{x,y\} \subseteq S$, but this is precisely the upper bound sharing graph of $L$.

Let $C$ be any maximal clique of the upper bound sharing graph, then by condition (2) there is some clique $Z$ in $F$ that contains $C$ so that $C \subseteq Z$. It follows that any $\sim$ clique is a clique in $F$. Let $S \in F$ then $S$ is a $\sim$ clique, because $S$ is contains any pair of its own elements, and it is maximal because it is in a family $F$ that contains all its own cliques. Therefore, $F$ forms a maximal cliques family. $\square$

Suborder of adjacency principal filters:

Let $x \in G$. Then the intersection of all cliques of $M(G)$ containing $x$ is the adjacency principal filter $\uparrow x$ of $x$. This is the smallest member of $M(G)$ containing $x$. \[ \uparrow : G \to M(G) \] The image of $\uparrow$ is the subset of $M(G)$ consisting of all adjacency principal filters. The kernel of $\uparrow$ is the adjacency equality relation of $G$. The condensation of $G$ is the quotient of $G$ with respect to adjacency equality.

Theorem. the join irreducibles (excluding the minimal element as the empty join) of $M(G)$ are necessarily adjacency principal filters.

Proof. let $S \in M(G)$ be a clique in $M(G)$. Then suppose that $S$ is not an adjacency principal filter, then $S$ doesn't have any elements unique to itself, so it is the union of all its predecessors. As it is a union it is join reducible. Then suppose that a join irreducible element that is not an adjacency principal filter, then it is union irreducible which means it is join irreducible which is a contradiction. $\square$

We have the following bounds the suborder of the adjacency principal filters of $M(G)$: (1) the filters must contain all join irreducibles and (2) they can include up to the entire set $G$. The suborder of $M(G)$ consisting of adjacency principal filters is an important source of information, because it determines a graph up to adjacency equality.

Theorem. let $L$ be a semilattice with subset $S$ consisting of adjacency principal filters. Then all graphs having $S$ as a suborder of $M(G)$ equal to $L$ have the same condensation.

Proof. let $\uparrow : G \to L$ be the principal adjacency filter function for the semilattice $L$. Then we can recover $M(G)$ by recursion. \[ f(l) = \uparrow^{-1}(l) \cup \bigcup_{i \subset l} f(i)\] Then since the graph $G$ can be recovered by its maximal cliques, every graph $G$ can then be defined by its $\uparrow$ function. The adjacency equality of $G$ is the kernel of $\uparrow$, which has no effect up to condensation. Condensed graphs are therefore determined by the image of $\uparrow$ which is a suborder of $M(G)$. $\square$

Corollary. the condensation types of graphs are determined by the images of $\uparrow$, which are subobjects of the semilattice $L$.

There are generally multiple condensation types associated to a given order type $L$. This is demonstrated below.

Example 1. the cyclic graph $C_4$ it has a maximal cliques intersection semilattice of the following form, with the adjacency principal filters highlighted: the following larger graph has the same intersection order type but it has a different set of principal adjacency filters Example 2. the path graph $P_4$ has an intersection semilattice that looks like this the following larger graph has a semilattice with more adjacency principal filters In fact, every graph of with this semilattice order type has the condensation of either a path, gem, bull, or the above larger graph.

Theorem. let $G$ be a graph then $G$ is trivially perfect (e.g $P_4,C_4$-free) iff $M(G)$ is a lower tree

Proof. let $G$ be a trivially perfect graph, then removal of the center always disconnects the graph into connected components. The class of trivially perfect graphs is hereditary, so this can be applied recursively to get a lower tree decomposition of $G$. In the other direction, if the minimal element of $M(G)$ is a cut vertex, it can be removed to get connected components. In a lower tree this can be applied again recursively, to get a trivially perfect graph. $\square$

We can recover the clique graph of a graph, provided that we have the order type of $M(G)$ and its suborder of adjacency principal filters.

Proposition. let $G$ be a graph, with $M(G)$ its semilattice of intersections of maximal cliques, with $S$ its set of adjacency principal filters. Then if the minimal element of $M(G)$ is in $S$ the clique graph is a complete graph, otherwise it is equal to the independence graph of the maximal elements: two elements are independent provided they meet at the minimal element.

A graph is a clique graph provided that it has a Helly edge covering of its cliques. The Helly property of the independence graph of any semilattice $M(G)$ follows from the upper bound sharing property.

Graph theoretic properties:

The intersection semilattice has an order type and a suborder of adjacency principal filters, but it also contains additional data as a set system such as the clique number of the graph, which would not be recordered otherwise.

Proposition. the clique number of $G$ is equal to the rank of $M(G)$

A quick look at some of the set-theoretic properties of a selected assortment of classes of graphs is presented below:

$G$	$M(G)$
Empty graph	Rank one family
Complete graph	Unique family
Cluster graph	Pairwise disjoint family
Cocluster graph	Convex family
Triangle free graph	Rank two family
Cotriangle free graph	Cotriangle free maxima intersections
Trivially perfect graph:	Lower tree ordered family

In a cluster graph, the maximal cliques correspond to connected components so that $M(G)$ is a pairwise disjoint family. In a cocluster graph, the cocluster is the graph join of empty graphs, which means that is convex from the maximal cliques of $G$ to the center.

Another case where we might want to compute $M(G)$ is when dealing with a $G$ composed from certain basic graph operations:

• Graph coproducts: $M(C_1 + C_2) = M(C_1) \cup M(C_2) \cup \{\emptyset\}$.
• Graph join: $M(\overline{\overline{C_1} + \overline{C_2}} ) = \{x \cup y: x \in C_1, y \in C_2\}$
• Graph products: $M(G \times H) = \{ C_1 \times C_2 : C_1 \in M(G), C_2 \in M(H) \}$

The computation of $M(G)$ from the elementary graph operations, can aid in the computation of $M(G)$ for certain graphs $G$. Although emerging as a subsemilattice of $Sub(A)$ for certain algebraic structures, $M(G)$ also encodes a great deal about information about graphs in general.

References:
[1] Clique graphs

[2] Trivially perfect graphs