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.

Improve this question
$\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$
    – Mikhail Tikhomirov
    Commented May 14, 2022 at 9:47
  • 1
    $\begingroup$ I have edited the definition of "cover." Thanks. $\endgroup$
    – Tri
    Commented May 14, 2022 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
    Commented May 14, 2022 at 20:54
  • 1
    $\begingroup$ Thank you. I'll have to think about why it's clear. ;-) $\endgroup$
    – Tri
    Commented May 14, 2022 at 23:54
  • 1
    $\begingroup$ Can you clarify your comment @bof? $\endgroup$
    – Dominic van der Zypen
    Commented May 15, 2022 at 7:50

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .