Skip to main content
edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Source Link

Optimal pseudotransversals

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?