# Matching number in infinite hypergraphs

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

• Do you assume the edges are finite? If not, there is an easy counterexample. Commented Dec 6, 2021 at 14:26
• 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? Commented Dec 6, 2021 at 20:11
• Not sure - perhaps it is just not that obvious. Commented Dec 6, 2021 at 21:37
• Not to me for one.. Commented Dec 7, 2021 at 5:50

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.

• 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. Commented Dec 7, 2021 at 7:43
• @Fedor Yes I know, I merely wanted to share a bit prettier construction;) Commented Dec 7, 2021 at 9:47

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

• Thanks Florian for this additional answer - beautiful! Commented Dec 7, 2021 at 16:15