# Tameable hypergraphs

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

• Thanks - will check it. And yes, "tame" is a typo, will amend. Mar 7, 2021 at 11:35

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

• Thank you for the generalisation, this looks great! Mar 7, 2021 at 14:11
• Thanks for checking it.
– bof
Mar 8, 2021 at 1:33