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)$?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Do you assume the edges are finite? If not, there is an easy counterexample. $\endgroup$
    – Ilya Bogdanov
    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$
    – Dominic van der Zypen
    Commented Dec 6, 2021 at 20:11
  • $\begingroup$ Not sure - perhaps it is just not that obvious. $\endgroup$
    – Ilya Bogdanov
    Commented Dec 6, 2021 at 21:37
  • $\begingroup$ Not to me for one.. $\endgroup$
    – Dominic van der Zypen
    Commented Dec 7, 2021 at 5:50

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Fedor Petrov
    Commented Dec 7, 2021 at 7:43
  • $\begingroup$ @Fedor Yes I know, I merely wanted to share a bit prettier construction;) $\endgroup$
    – Ilya Bogdanov
    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)$.

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

You must log in to answer this question.

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