4
$\begingroup$

$\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.

$\endgroup$
9
  • 1
    $\begingroup$ I assume "a family $C$ of subsets of $F$" means a collection of hyperedges, rather than a collection of hyperedge sets ("subsets of $F$")? $\endgroup$ May 14 at 9:47
  • 1
    $\begingroup$ I have edited the definition of "cover." Thanks. $\endgroup$
    – Tri
    May 14 at 17:36
  • 2
    $\begingroup$ 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. $\endgroup$
    – bof
    May 14 at 20:54
  • 1
    $\begingroup$ Thank you. I'll have to think about why it's clear. ;-) $\endgroup$
    – Tri
    May 14 at 23:54
  • 1
    $\begingroup$ Can you clarify your comment @bof? $\endgroup$ May 15 at 7:50

1 Answer 1

1
$\begingroup$

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<D$ 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<C_2<\dots$ 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.

$\endgroup$
6
  • $\begingroup$ @bof mathoverflow.net/questions/193352/… $\endgroup$
    – Tri
    May 15 at 12:18
  • 1
    $\begingroup$ I added my interpretation of minimal to my answer. $\endgroup$
    – domotorp
    May 15 at 17:11
  • $\begingroup$ 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. $\endgroup$
    – bof
    May 15 at 18:02
  • $\begingroup$ @Tri Is there a definition of "minimal cover" in that other question? $\endgroup$
    – bof
    May 15 at 18:07
  • $\begingroup$ @bof Probably not. My definition of "minimal" is with respect to set-inclusion. $\endgroup$
    – Tri
    May 16 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.