1
$\begingroup$

Let $H=(V,E)$ be a hypergraph. A set $M\subseteq E$ consisting of mutually disjoint members of $E$ is said to be a matching. We say $S\subseteq V$ is matchable if there is a matching $M$ such that $\bigcup M = S$.

One might think thatZorn's Lemma implies that every matchable set is contained in a maximal matchable set (with respect to $\subseteq$), but this is false: If $H = (\mathbb{N}, E)$ with $E = \big\{\{0,\ldots, n\}: n\in \mathbb{N}\big\}$, then $E$ is exactly the collection of matchable sets in $H$, and there are no maximal matchable sets in $H$.

Question. Let $n$ be a positive integer. If $H=(V,E)$ is a hypergraph such that every member of $E$ has at most $n$ elements, is there necessarily a maximal matchable set $S\subseteq V$?

$\endgroup$
1
  • $\begingroup$ That's right @MikhailTikhomirov - I have corrected it just now! Thank you also to Peter, and apologies for my mistake. $\endgroup$ May 3, 2022 at 13:26

1 Answer 1

2
$\begingroup$

Let $n = 2$, and $H$ be the complete bipartite graph with halves $V_1$ a copy of $\mathbb{N}$ and $V_2$ a copy of $\mathbb{R}$. Let $r(M)$ be an element of $V_2$ not covered by a matching $M$. If $M$ doesn't cover an $x \in V_1$, extend $M$ with $(x, r(M))$, otherwise increment every $V_1$-endpoint in $M$, and add $(1, r(M))$. This shows no $S$ is maximal.

$\endgroup$

You must log in to answer this question.

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