3
$\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$
1
  • 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$ Aug 14, 2018 at 16:52

1 Answer 1

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$
10
  • 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$ Aug 16, 2018 at 7:38
  • 1
    $\begingroup$ @GerhardPaseman Ups! This is a small problem, which is corrected now. Thank you for noticing it. $\endgroup$ Aug 16, 2018 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$ Aug 16, 2018 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$ Aug 16, 2018 at 8:12
  • 1
    $\begingroup$ @GerhardPaseman So simple! $\endgroup$ Aug 16, 2018 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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