Return to Answer

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\{y\}$. Since $S_1\subseteq S$, this contradicts the fact that $S$ contains no minimal vertex cover of $E_0\cup\{f\}$.

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\}$.

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$.

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\{y\}$. Since $S_1\subseteq S$, this contradicts the fact that $S$ contains no minimal vertex cover of $E_0\cup\{f\}$.

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 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 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$.

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$.