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.
$\endgroup$
4
  • 1
    $\begingroup$ Are there finiteness assumptions? Or can $V$ be any set? $\endgroup$
    – jmc
    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$ 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$ Jan 9, 2015 at 2:08
  • 1
    $\begingroup$ +1 for the strong minimality condition. $\endgroup$ Jan 9, 2015 at 2:33

1 Answer 1

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.

$\endgroup$
9
  • 1
    $\begingroup$ Nice! (A set $\ V:=(0;\frac 32)\ $ would be a smaller example :-). $\endgroup$ 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$ 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$ Jan 9, 2015 at 5:03
  • $\begingroup$ @Noah: See the update. $\endgroup$
    – domotorp
    Jan 9, 2015 at 7:52
  • 1
    $\begingroup$ The family $\big\{\{r\}\mid r\in\mathbb R\big\}$ is a minimal cover. $\endgroup$
    – Tri
    May 7, 2022 at 23:55

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.