7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks - will check it. And yes, "tame" is a typo, will amend. $\endgroup$ – Dominic van der Zypen Mar 7 at 11:35
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you for the generalisation, this looks great! $\endgroup$ – Dominic van der Zypen Mar 7 at 14:11
  • 1
    $\begingroup$ Thanks for checking it. $\endgroup$ – bof Mar 8 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.