4
$\begingroup$

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such that $|T\cap e| = 1$ for all $e\in E$.

It is easy to see that transversals need not exist: Take $V = \{0,1,2\}$ and let $E$ be the collection of $2$-element subsets of $V$.

A pseudotransversal is a set $T\subseteq V$ such that $T\cap e\neq \emptyset$ for all $e\in E$. We call $$G_T:=\{e\in E:|T\cap e| =1\}$$ the set of good members of $E$ with respect to $T$. We say that that a pseudotransversal $T$ is optimal if for all pseudotransversals $T_1$ with $G_T\subseteq G_{T_1}$ we have $G_T=G_{T_1}$.

Question. Does every hypergraph $H=(V,E)$ allow for an optimal pseudotransversal?

$\endgroup$

1 Answer 1

4
$\begingroup$

No, here is an example of a hypergraph with no optimal transversal.

Let $V=\omega$ (the set of nonnegative integers), and let $$E=\{\{0\}\} \cup\{\{0,n\};n\ge 1\} \cup \{\{i; i\ge n\}; n\in \omega\}.$$

In other words, $E$ consists of the singleton $\{0\}$, all pairs containing $0$, and all intervals $[n,\infty]$.

If $T$ is a pseudotransversal, then $0\in T$, and so $T$ intersects all the pairs $\{0,n\}$. Also $T$ must be infinite to intersect all the intervals $[n,\infty]$. But now for every nonzero $n\in T$, the set $T\setminus \{n\}$ is still a pseudotransversal, and $G_{T\setminus \{n\}} \setminus G_T$ contains the pair $\{0,n\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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