4
$\begingroup$

Let $H=(V,E)$ be a hypergraph. We say that $C\subseteq E$ is a cover if $\bigcup C = V$. Let $H$ be a hypergraph with the following properties:

  1. $\bigcup E = V$,
  2. all members of $E$ are finite, and
  3. $d,e\in E$ with $d\subseteq e$ implies $d=e$.

Question. Does this imply that there is a minimal cover $C_0$ (that is, $C_0$ has the property that for all $c\in C_0$ the set $C_0\setminus \{c\}$ is no longer a cover)?

$\endgroup$
  • 2
    $\begingroup$ If $C\subset E$, then each element $c\in C$ is an element of $E$ and hence a subset of $V$. So, $\bigcup C$ is a subset of $V$ and cannot be equal to $E$. So I wonder if $\bigcup C=E$ in the definition of cover should be corrected to $\bigcup C=V$? If yes, then the condition (3) implies that $E$ is the unique (minimal) cover. So, a minimal cover always exists. Or I do not understand something? $\endgroup$ – Taras Banakh Aug 14 '18 at 14:42
  • 1
    $\begingroup$ While I agree with the correction V replaces E, I don't see condition 3 prescribing a minimal cover. In particular, cover half of V with three-sets, the other half with five-sets, and bridge the two halves with two-sets. This cover gives at least two smaller covers, and it might be possible to arrange no minimal cover through a clever selection. Gerhard "That Doesn't Quite Cover It" Paseman, 2018.08.14. $\endgroup$ – Gerhard Paseman Aug 14 '18 at 16:52
  • $\begingroup$ You are right @TarasBanakh it should be $\bigcup C = V$, sorry for my mistake! I have just corrected it. $\endgroup$ – Dominic van der Zypen Aug 16 '18 at 6:55
5
$\begingroup$

Let $V:=\omega\times\omega$ and $E=\{E_{n,m}:n,m\in\omega\}$ where $$E_{n,m}:=(\{0,\dots,n\}\times\{m\})\cup\{(2n,m+1)\}.$$ It seems that the hypergraph $(V,E)$ has no minimal cover.

A simplification of this example was suggested by Gerhard Paseman in his comment: Just take $V=\mathbb Z$ and $E=\{E_n,F_n:n\in\mathbb N\}$ where $E_n:=\{-2n\}\cup [0,n]$ and $F_n:=[-n,0]\cup\{2n\}$.

Added in Edit. I have just discovered that the Paseman's example is "isomorphic" to the example of @domotorp (Strongly minimal covers) given in 2015 to a similar question of Dominic van der Zypen.


The question of Dominic van der Zypen has positive answer if the cardinalities of hyperedges are upper bounded by some number.

Theorem. For any $n\in\mathbb N$, any set $V$ and family $E\subset[V]^{\le n}$ with $\bigcup E=V$ there exists a minimal subfamily $C\subset E$ such that $\bigcup C=V$.

Proof. For $n=1$ the assertion is trivial. Assume that for some $n\ge 2$ we have proved that any family $E\subset [V]^{<n}$ with $\bigcup E=V$ contains a minimal subfamily $C\subset E$ with $\bigcup C=V$.

Take any family $E\subset [V]^{\le n}$ with $\bigcup E=V$. Using Zorn's lemma, choose a maximal disjoint subfamily $D\subset E$. If the set $W:=V\setminus\bigcup D$ is empty, then $D$ is a required minimal cover of $V$.

So, we assume that $W$ is not empty. By the maximality of $D$, each hyperedge $e\in E\setminus D$ intersects the set $\bigcup D$, which implies that $E':=\{e\cap W:e\in E\setminus D\}\subset [W]^{<n}$. By the inductive assumption, the family $E'$ contains a minimal subfamily $C'\subset E'$ with $\bigcup C'=W$.

For every $c\in C'$ find a hyperedge $e_c\in E\setminus D$ such that $e_c\cap W=c$. Let $H:=\{e_c:c\in C'\}$ and $D':=\{e\in D:e\not\subset \bigcup H\}$. It can be shown that $C:=H\cup D'$ is a minimal subcover of $E$.

$\endgroup$
  • 1
    $\begingroup$ It looks like E_{n,2k} is minimal by looking at odd values of m. Gerhard "Seems Pretty Minimal At Odds" Paseman, 2018.08.16. $\endgroup$ – Gerhard Paseman Aug 16 '18 at 7:38
  • 1
    $\begingroup$ @GerhardPaseman Ups! This is a small problem, which is corrected now. Thank you for noticing it. $\endgroup$ – Taras Banakh Aug 16 '18 at 7:43
  • 2
    $\begingroup$ Indeed, by mirroring the construction you can let m range over a two element set instead of over omega. Gerhard "2N Is A Nice Touch" Paseman, 2018.08.16. $\endgroup$ – Gerhard Paseman Aug 16 '18 at 7:50
  • 2
    $\begingroup$ After your nice acknowledgement, it occurs to me that we have folded over the integers. I will let you do the formulation over Z. Gerhard "This Makes It Even Simpler" Paseman, 2018.08.16. $\endgroup$ – Gerhard Paseman Aug 16 '18 at 8:12
  • 1
    $\begingroup$ @GerhardPaseman So simple! $\endgroup$ – Taras Banakh Aug 16 '18 at 8:22

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.