Clique decompositions that are maximal with respect to refinement

Question

If $X$ is a non-empty set and ${\cal A}, {\cal B}$ are covers, then we say that ${\cal A} \leq_{\text{fin}} {\cal B}$ if for all $A\in {\cal A}$ there is $B\in{\cal B}$ such that $A\subseteq B$ and we say that ${\cal A}$ refines ${\cal B}$.

Let $G=(V,E)$ be a simple, undirected graph. A clique decomposition is a set ${\cal C} \subseteq {\cal P}(V)$ such that

1. $\emptyset \notin {\cal C}$,
2. $C\in {\cal C}$ and $x\neq y \in C$ imply that $\{x,y\}\in E$ (that is every member of ${\cal C}$ is a clique),
3. $\bigcup {\cal C} = V$, and
4. $e=\{x,y\} \in E \implies$ there is $C\in{\cal C}$ such that $x,y\in C$.

The collection of all edges plus the isolated points is a clique decomposition, and it is easily seen to be minimal with respect to refinement amongst all clique decompositions. Does the collection of clique decompositions also have maximal elements with respect to refinement? (The answer is yes for finite graphs, but I don't know about infinite graphs.)

Answer 1

Sure. Given the way that you have asked it, simply take the set of all cliques: every singleton point, every edge, all finite and infinite cliques. That is surely maximal.

All you really need is the set of all maximal cliques, those not properly contained in any other clique. You must have those and you are free to include any others if you like.

If the points are the positive integers with edges defined by divisibility then the cover consists of all cliques $1,p_1,p_1p_2,p_1p_2p_3,\cdots$ where $p_1,p_2,p_3,\cdots$ is an infinite sequence of primes (which need not be distinct.)

Perhaps you would like to add the condition that every clique in the cover has an edge not contained in any other clique of the cover (i.e. dropping any one clique makes the set not be a cover.) Even then there are maximal covers but you might end up using the axiom of choice to order the vertices. Then you could build a greedy maximal cover where each clique starts with the vertices of the "first" edge not yet covered and grows by adding the next vertex adjacent to all those already chosen. Alternately, you could use Zorn's lemma on your partially ordered set of covers.