Cardinality of a set of mutually disjoint perfect matchings of $K_\omega$

Question

If $G=(V,E)$ is a simple, undirected graph, we say that $M\subseteq E$ is a perfect matching if the members of $M$ are pairwise disjoint and $\bigcup M = V$. Let $K_\omega$ be the complete graph on $\omega$.

Let ${\frak M}$ be a class of perfect matchings on $K_\omega$ such that whenever $M_1\neq M_2\in{\frak M}$ we have $M_1\cap M_2 = \emptyset$.

What is the largest possible value that $|{\frak M}|$ can have?

Answer 1

It's reasonably clear that there can be at most countably many disjoint perfect matchings, since each matching must contain an edge adjacent to each vertex and there are only countably many such edges.

Conversely it's not to hard to build a countable family of perfect matchings in the following manner:

Our aim will be to inductively construct sets $(M_i(t) \colon i < \omega)$ such that for all $t < \omega$

• $M_i(t)$ is a matching for all $i < \omega$;
• $M_i(t) \supseteq M_i(t-1)$ for all $i < \omega$;
• $M_i(t) \cap M_j(t) = \emptyset$ for all $i,j< \omega$;
• $M_i(k)$ is finite and covers the vertices $\{1,\ldots,t\}$ for all $k \leq t$
• $M_i(k) = \emptyset$ for all $k > t$.

Taking $M_i := \bigcup_{t < \omega} M_i(t)$ gives a family of edge sets which are matchings by the first property, pairwise disjoint by the third, and perfect matchings by fourth property.

The inductive step is relatively easily; given $(M_i(t) \colon i <\omega)$ we need to add at most one edge to each $M_i(k)$ with $k \leq t$ so that $M_i(k)$ covers the vertex $t+1$, and we need to find a matching $M_i(t+1)$ which covers all the vertices $\{1,2,\ldots, t+1\}$.

However, since we've only used finitely many edges up to this point, we can just choose all of these edges greedily and continue.

Answer 2

The maximum possible value of $|\mathfrak M|$ is $\aleph_0$.

$|\mathfrak M|$ can't be uncountable, since it's a collection of disjoint subsets of the countable set $E$.

Let $K_\omega$ be the complete graph on the vertex set $\mathbb Z$. Let $M_n=\{\{x,y\}\in\binom{\mathbb Z}2:x+y=n\}$. Then $\mathfrak M=\{M_{2k+1}:k\in\mathbb Z\}$ is a collection of pairwise disjoint perfect matchings with $|\mathfrak M|=\aleph_0$.

More generally, if $G$ is a countable graph in which each vertex has infinite degree, then $E(G)$ is the union of $\aleph_0$ disjoint perfect matchings. First, it is easy to see that such a graph has a perfect matching, call it $M_1$, which may be made to contain a prescribed edge $e_1\in E(G)$. Next, since the spanning subgraph $G-E(G_1)$ is still a countable graph in which each vertex has infinite degree, we can find a perfect matching $M_2$ which is disjoint from $M_1$ and contains a prescribed edge $e_2\in E(G)\setminus M_1$. Continuing in this way, we can get an infinite sequence of disjoint perfect matchings whose union is $E(G)$.

Likewise for any infinite cardinal $\kappa$, if $G$ is a $\kappa$-regular graph of order $\kappa$, then $\kappa$ is the maximum possible cardinality of a collection $\mathfrak M$ of pairwise disjoint perfect matchings of $G$, and such an $\mathfrak M$ can be chosen to be a partition of $E(G)$.