Tameable hypergraphs

Question

Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$.

We say that $H$ is tameable if every independent set is contained in a maximal independent set. Every graph is tameable and, more generally, so is every hypergraph with finite edges.

There are easy examples of non-tameable hypergraphs, and I use this one given by user @bof in the comment section of this answer: Let $H=(\omega,[\omega]^\omega)$, where $[\omega]^\omega$ denotes the collection of infinite subsets of $\omega$. (The only independent subsets of this graph are the finite sets, and there is no maximal finite set.)

If $(P,\leq)$ is a poset, then with $\text{Max}(P)$ we denote the collection of maximal elements of $P$. (Note that $\text{Max}(\omega) = \varnothing$, for instance.)

Given a hypergraph $H=(V,E)$ we let $$\text{Tame}(H) = \{E'\subseteq E: (V, E') \text{ is tameable}\}.$$

Question. Given a hypergraph $H=(V,E)$ with $V\neq\varnothing\neq E$ and $\varnothing\notin E$, do we necessarily have $\text{Max}(\text{Tame}(H)) \neq \varnothing$?

Answer 1

No. For a counterexample let $H=(\omega,E)$ where $E=\{e_n:n\in\omega\}$ and $e_n=[n,\omega)=\{x\in\omega:x\ge n\}$.

If a subset $E'\subseteq E$ is finite then $(\omega,E')$ is tameable; every vertex cover contains a finite vertex cover which contains a minimal vertex cover, and (equivalently) every independent set is contained in a cofinite independent set which is contained in a maximal independent set.

If $E'\subseteq E$ is infinite then $(\omega,E')$ is not tameable; in fact, it has no minimal vertex cover and (equivalently) no maximal independent set, since the vertex covers are just the infinite subsets of $\omega$ and the independent sets are just the coinfinite subsets of $\omega$.

Thus $\operatorname{Tame}(H)=\{E'\subseteq E:E'\text{ is finite}\}$ and $\operatorname{Max}(\operatorname{Tame}(H))=\varnothing$.

More generally, if $H=(V,E)$ is a hypergraph ($\varnothing\notin E$), then $\operatorname{Max}(\operatorname{Tame}(H))=\varnothing$ except in the trivial case when $H$ is tameable and $\operatorname{Max}(\operatorname{Tame}(H))=\{E\}$.

Theorem. If $H=(V,E)$ is an untameable hypergraph (with nonempty edges), then $\operatorname{Max}(\operatorname{Tame}(H))=\varnothing$.

Since the vertex set $V$ is fixed throughout the discussion, to save typing I will identify a hypergraph with its edge set; so I am going to show that the untameable set $E$ has no maximal tameable subset. For some reason I find it easier to work with minimal vertex covers than maximal independent sets.

Proof. Assume for a contradiction that $E_0$ is a maximal tameable subset of $E$, and choose an edge $f\in E\setminus E_0$. Then $E_0\cup\{f\}$ is untameable, so there is a vertex cover $S$ of $E_0\cup\{f\}$ which contains no minimal vertex cover of $E_0\cup\{f\}$.

Since $S$ is a vertex cover of the tameable set $E_0$, $S$ contains a minimal vertex cover $S_0$ of $E_0$. Now $S_0$ can't be a vertex cover of $E_0\cup\{f\}$, as it would then be a minimal vertex cover of $E_0\cup\{f\}$, which is impossible since $S_0\subseteq S$.

Choose a vertex $y\in S\cap f$. Then $S_0\cup\{y\}$ is a vertex cover of $E_0\cup\{f\}$, but it can't be a minimal vertex cover of $E_0\cup\{f\}$ since $S_0\cup\{y\}\subseteq S$. Since $S_0$ is not a vertex cover of $E_0\cup\{f\}$, there is a vertex $x\in S_0$ such that $(S_0\setminus\{x\})\cup\{y\}$ is a vertex cover of $E_0\cup\{f\}$ and therefore of $E_0$.

Since $E_0$ is tameable, there is a set $S_1\subseteq(S_0\setminus\{x\})\cup\{y\}\subseteq S$ such that $S_1$ is a minimal vertex cover of $E_0$. Morever $y\in S_1$, as otherwise we would have $S_1\subseteq S_0\setminus\{x\}$, contradicting the fact that $S_0$ is a minimal vertex cover of $E_0$.

Thus $S_1$ is a vertex cover of $E_0\cup\{f\}$, and being a minimal vertex cover of $E_0$ it is a minimal vertex cover of $E_0\cup\{f\}$. Since $S_1\subseteq S$, this contradicts the fact that $S$ contains no minimal vertex cover of $E_0\cup\{f\}$.