Skip to main content
3 of 3
edited tags

Sizes of matchings and transversals in hypergraphs

Let $H=(V,E)$ be a hypergraph. We call $H$ proper if $E\neq\emptyset, \emptyset \notin E$ and for no $e_1\neq e_2\in E$ we have $e_1\subseteq e_2$. A matching is a set $M$ of pairwise disjoint edges (members of $E$), and $T\subseteq V$ is said to be a transversal if $T\cap e \neq \emptyset$ for all $e\in E$.

It is easy to see that any transversal has at least the cardinality of any matching.

Given infinite cardinals $\alpha < \beta$ is there a proper hypergraph $H=(V,E)$ with the following properties?

  1. there is a matching of size $\alpha$, and no matching has cardinality larger than $\alpha$, and
  2. $\beta$ is the minimum size of a transversal of $H$.