5
$\begingroup$

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$.
$\endgroup$

1 Answer 1

1
$\begingroup$

Yes. For fixed $\beta$ we construct the hypergraph $G_\beta$ with edges $\{e_x\}_{x\in \beta}$, any two edges $e_x,e_y$ have unique common vertex $v_{x,y}$, and there are no other vertices. In this hypergraph the maximal matching has size 1 and the minimal transversal has size $\beta$, since any set consisting of $\gamma<\beta$ vertices intersects at most $2\gamma<\beta$ edges.

Now take $\alpha$ disjoint copies of $G_\beta$.

$\endgroup$

You must log in to answer this question.

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