2
$\begingroup$

If $H= (V,E)$ is a hypergraph, a matching is a set $M\subseteq E$ such that $e_1\cap e_2 = \emptyset$ whenever $e_1\neq e_2 \in M$. The matching number $\mu(H)$ of a hypergraph $H=(V,E)$ with $V$ finite is the maximum number of elements a matching can have.

For infinite hypergraphs $H=(V,E)$, we let $$\mu(H) = \sup\{|M|:M\subseteq E\text{ is a matching}\}.$$ This definition agrees with the above definition for finite hypergraphs.

Question. If $H=(V,E)$ is a hypergraph with $V$ infinite, is there necessarily a matching $M_0\subseteq E$ such that $|M_0|=\mu(H)$?

$\endgroup$
4
  • 2
    $\begingroup$ Do you assume the edges are finite? If not, there is an easy counterexample. $\endgroup$ Commented Dec 6, 2021 at 14:26
  • $\begingroup$ That's right, I had no finiteness assumption. I'm happy to accept your counterexample as an answer. - I take it there cannot be a counterexample with just finite edges? $\endgroup$ Commented Dec 6, 2021 at 20:11
  • $\begingroup$ Not sure - perhaps it is just not that obvious. $\endgroup$ Commented Dec 6, 2021 at 21:37
  • $\begingroup$ Not to me for one.. $\endgroup$ Commented Dec 7, 2021 at 5:50

2 Answers 2

3
$\begingroup$

Let $(P,\leq)$ be a poset, let $H$ be the set of maximal chains in $P$ —- so $H$ will be the set of vertices. For $a\in P$, let $E_a$ denote the set of all chains in $H$ containing $a$; these sets are the edges.

Now, $E_a$ and $E_b$ are disjoint iff $a$ and $b$ are incomparable. So the edges are pairwise disjoint iff the corresponding elements form an antichain.

It remains to find a poset containing arbitrarily large antichains but having no infinite ones. One such example is $\mathbb Z_{\geq0}^2$ with a componentwise relation.

This provides a counterexample, if infinite edges are allowed.

$\endgroup$
2
  • 1
    $\begingroup$ If infinite edges are allowed, we could simply take the disjoint edges $A_{n1}, A_{n2}, \dots, A_{nn} $ for all $n=1,2, \dots$, and add vertices so that $A_{ni}$ and $A_{kj}$ for $n\ne k$ are not disjoint anymore. $\endgroup$ Commented Dec 7, 2021 at 7:43
  • $\begingroup$ @Fedor Yes I know, I merely wanted to share a bit prettier construction;) $\endgroup$ Commented Dec 7, 2021 at 9:47
4
$\begingroup$

I think if all edges are finite, then there is such a matching.

Let $M_0$ be a maximal matching (in the sense that no edge can be added to it; this exists by Zorn's Lemma). Let $\alpha_0$ be the cardinality of $M_0$, and let $V_0$ be the set of all vertices contained in some edge of $M_0$. By maximality of $M_0$, every edge contains some vertex in $V_0$. Since no two edges of any matching contain the same vertex in $V_0$, we conclude that $|M| \leq |V_0|$ for every matching $M$.

If $\alpha_0$ is finite, then so is $|V_0|$ and thus $|V_0|$ is a finite upper bound on the size of any matching. This clearly implies that there is a matching of size $\mu(H) < \infty$.

If $\alpha_0$ is infinite, then $|V_0| = \alpha_0$ (because all edges are finite). So any matching has cardinality at most $\alpha_0$ thus showing that $\mu(H) \leq \alpha_0 = |M_0| \leq \mu(H)$.

$\endgroup$
1
  • $\begingroup$ Thanks Florian for this additional answer - beautiful! $\endgroup$ Commented Dec 7, 2021 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.