# Strongly minimal covers for clique hypergraphs of graphs

$$\DeclareMathOperator\Cliq{Cliq}$$A hypergraph $$H$$ is a pair consisting of a set $$V$$ of vertices and a family of subsets of $$V$$ called edges. One class of examples is obtained by taking a graph $$G=(V,E)$$ with set of vertices $$V$$ and set of edges $$E$$ where $$H=(V,\Cliq (G) )$$. Here $$e\in \Cliq(G)$$ if and only if for all $$v,w\in e$$ such that $$v\ne w$$ we have $$\{v,w\}\in E$$.

If $$H=(V,F)$$ is a hypergraph, a cover is a subset $$C$$ of $$F$$ such that $$\bigcup C=V$$. The cover is strongly minimal if for any cover $$D$$, $$|C\setminus D|\le|D\setminus C|$$.

Please give an example of a hypergraph stemming from the cliques of a graph as above that has no strongly minimal cover.

A related post with a nice example by domotorp is here.

Edit: I had an incorrect definition of "cover" before. Thanks to Mikhail Tikhomirov for leading me to look at it again.

• I assume "a family $C$ of subsets of $F$" means a collection of hyperedges, rather than a collection of hyperedge sets ("subsets of $F$")? May 14 at 9:47
• I have edited the definition of "cover." Thanks.
– Tri
May 14 at 17:36
• You are asking whether every graph has a strongly minimal covering by cliques. An equivalent (perhaps more natural) question is whether every graph has a strongly minimal cover by anticliques (independent sets). It seems clear that every locally finite graph has a strongly minimal cover by anticliques.
– bof
May 14 at 20:54
• Thank you. I'll have to think about why it's clear. ;-)
– Tri
May 14 at 23:54
• Can you clarify your comment @bof? May 15 at 7:50

I can prove the following weaker statement, which was not true in the other version:
Every hypergraph stemming from the cliques of a graph has a minimal cover, where I define a cover as minimal if the union of no two of its hyperedges is a hyperedge.

The proof follows from Zorn's lemma.
Define a poset $$P$$ on the covers such that $$C if for every clique $$c\in C$$ there is a clique $$d\in D$$ such that $$c\subset d$$.
$$P$$ satisfies the conditions of Zorn's lemma, as in any chain $$C_1 we can consider all clique-chains $$c_1\subset c_2\subset\ldots$$ where $$c_i\in C_i$$, and let $$C=\{c\mid c=\cup c_i$$ for some such clique-chain$$\}$$.
A maximal element of $$P$$, guaranteed to exist by Zorn's lemma, is necessarily a minimal cover.

• – Tri
May 15 at 12:18
• I added my interpretation of minimal to my answer. May 15 at 17:11
• Instead of defining a partial order on the covers, you can simply define a partial order on the cliques themselves, and use Zorn's lemma to show that every vertex is in a maximal clique. This shows that the set of all maximal cliques is a cover. Of course it's minimal, since the union of two maximal cliques is notv a clique.
– bof
May 15 at 18:02
• @Tri Is there a definition of "minimal cover" in that other question?
– bof
May 15 at 18:07
• @bof Probably not. My definition of "minimal" is with respect to set-inclusion.
– Tri
May 16 at 12:48