-1
$\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 transversal basis is a set $B\subseteq V$ such that $|B\cap e|\leq 1$ for all $e\in E$. Setting $I_B:=\{e\in E:B\cap e\neq \emptyset\}$, we say that that a transversal basis $B$ is good if for all transversal bases $B_1$ with $I_{B}\subseteq I_{B_1}$ we have $I_B=I_{B_1}$.

Question. Does every hypergraph $H=(V,E)$ have an good transversal basis?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Let $V=\mathbb Z,E=\{\{m\in\mathbb Z:m\geq n\}:n\in\mathbb Z\}$. It's clear every transversal basis has at most one element, but no basis $\{k\}$ is good, since $\{k+1\}$ intersects more sets from $E$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .