4
$\begingroup$

Let $H=(V,E)$ be a hypergraph, that is $V$ is a set and $E\subseteq \mathcal{P}(V)$. We say that $C\subseteq E$ is a cover of $H$ if $\bigcup C = V$.

A cover $M\subseteq E$ is said to be strongly minimal if for every cover $C$ of $H$ we have $$\text{card}(M\setminus C)\leq \text{card}(C\setminus M).$$

Is there a hypergraph $H=(V,E)$ with the following properties?

  1. $\bigcup E = V$;
  2. $e\in E$ and $e'\subseteq e$ implies $e'\in E$;
  3. for all $e\in E$ there is $m\in E$ such that $e\subseteq m$ and $m$ is maximal in $E$ with respect to set inclusion;
  4. $H$ does not have a strongly minimal cover.
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Are there finiteness assumptions? Or can $V$ be any set? $\endgroup$
    – jmc
    Commented Jan 7, 2015 at 10:09
  • $\begingroup$ Good point. For finite $V$ there is always a strongly minimal cover in the setting above. So if there is an example without strongly minimal cover, $V$ must be infinite. $\endgroup$
    – Dominic van der Zypen
    Commented Jan 7, 2015 at 11:07
  • 1
    $\begingroup$ I think that the Question would be easier to read if stated without a hypergraph (without $\ H),\ $ simply about a family $\ E\ $ of subsets of $\ V$. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jan 9, 2015 at 2:08
  • 1
    $\begingroup$ +1 for the strong minimality condition. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jan 9, 2015 at 2:33

1 Answer 1

Reset to default
4
$\begingroup$

Maybe I misunderstood something, but consider the following simple example. Let $V=(0,\infty)$ and let the maximal edges be the (open) unit intervals, except $(0,1)$. Any cover contains a sequence converging to $0$, so in fact there isn't any minimal cover at all.

Update: Noah asked whether there is an example where all edges are finite. Here I give such an example. Take $V=\{\frac 1i\mid i\in \mathbb N\} \cup \{-\frac 1i\mid i\in \mathbb N\}$. For any $n\in \mathbb N$ we define two maximal edges. The first is $\{\frac 1i\mid i\le n\} \cup \{-\frac 1n\}$ and the second is $\{-\frac 1i\mid i\le n\} \cup \{\frac 1n\}$ (note that these are the same for $n=1$, but this won't matter). Again there isn't any minimal cover.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Nice! (A set $\ V:=(0;\frac 32)\ $ would be a smaller example :-). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jan 9, 2015 at 2:37
  • $\begingroup$ What happens if we require every element of $E$ to be finite? Then nothing like this works, but it's not clear that there isn't some other example. $\endgroup$
    – Noah Schweber
    Commented Jan 9, 2015 at 3:34
  • $\begingroup$ At least one can modify @domotorp example by considering rationals only: $\ V:=(0;\infty)\cap\mathbb Q);\ $ and it's enough to consider as maximal edges the intervals $\ (a;a+1)\cap\mathbb Q\ $ such that $\ a>0\ $ and $\ a\in \mathbb Q.\ $ Thus domotorp's example becomes countable with countable many maximal edges. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jan 9, 2015 at 5:03
  • $\begingroup$ @Noah: See the update. $\endgroup$
    – domotorp
    Commented Jan 9, 2015 at 7:52
  • 1
    $\begingroup$ The family $\big\{\{r\}\mid r\in\mathbb R\big\}$ is a minimal cover. $\endgroup$
    – Tri
    Commented May 7, 2022 at 23:55

You must log in to answer this question.

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