Maximal expansions of strongly minimal covers of hypergraphs

Question

Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E = V$. Moreover we assume that every $e\in E$ is contained in some maximal member $e'\in E$ (maximal with respect to $\subseteq$). Let $\text{Max}(E)$ be the set of maximal members of $E$.

A cover is a set $N\subseteq E$ with $\bigcup N = V$. If $N \subseteq E$ is a cover, we call a map $\mu:N\to \text{Max}(E)$ such that $\mu(n) \supseteq n$ for all $n \in N$ a maximal expansion map of $N$. The image $\text{im}(\mu)$ is called a maximal expansion. By (AC) every cover has a maximal expansion.

A cover $C$ is minimal if for $C' \subseteq C, C'\neq C$ we have $\bigcup C' \neq V$. The cover $C$ is strongly minimal if $|C\setminus K| \leq |K\setminus C|$ for all covers $K$ of the hypergraph $H$.

Question. Suppose $N$ is strongly minimal, $\mu: N\to \text{Max}(E)$ is a maximal expansion map and $M= \text{im}(\mu)$. If $M$ is minimal, is it automatically strongly minimal?

Answer 1

The answer is Yes.

Suppose $M$ is minimal, but not strongly minimal. Then there is $S\subseteq M, S \neq \emptyset$ and $K\subseteq E$ such that

• $\bigcup K \supseteq \bigcup S$;
• $\text{card}(K) < \text{card}(S)$.

Consider the set $S_N = \mu^{-1}(S) \subseteq N$. Since $N$ is strongly minimal, $\mu$ is injective. So $\text{card}(S_N) = \text{card}(S) > \text{card}(K)$ and moreover $\bigcup K \supseteq \bigcup S \supseteq \bigcup S_N$. This implies that $N$ is not strongly minimal, contradicting our assumption.