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$
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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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