About structure of the set of perfect matchings of $K_{n,n}$

Question

1. Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure on this set? Some group that is known to may be act nicely on this set? (this might be a broad question, so feel free to just link to something you know that goes this way!)

2. Given a perfect matching of $K_{n,n}$ is there a systematic way to generate other perfect matchings (disjoint) from it?

3. How large a set of mutually disjoint perfect matchings of $K_{n,n}$ can be obtained ? And how to obtain such a set?

---

• That count of $\prod_{i=0}^{d-1} (n-i)!$ is what I think is the number of ways one can pick $d$ mutually disjoint perfect matchings of $K_{n,n}$ (the $k^{th}$ factor above corresponds to the number of ways the $k^{th}$ perfect matching can be chosen having made the previous choices)

• $d-1 = n$ is the largest $d$ for which the factor stops being defined. So naively I feel $d = n +1$ is the largest $d$ for which one can find $d$ mutually disjoint perfect matchings. Though I don't know if this d is the largest possible. (by cyclic permutations I seem to be able to generate atmost only $n$ mutually disjoint perfect matchings)

• I saw some related papers like, http://www.tau.ac.il/~nogaa/PDFS/mincg3.pdf and http://math.cmu.edu/~af1p/Texfiles/matchplusbip.pdf

• A related MO discussion, Postnikov's approach to perfect matchings of graphs

• Feel free to may be generalize any of the above questions to the case of more general bipartite graphs or general graphs!

Answer 1

Maybe I'll summarise everything from the comments as an answer.

Firstly, a perfect matching $M$ of $K_{n,n}$ can be identified with a permutation of the set $[n] = \{1,\ldots,n\}$ simply by numbering each side of the bipartition with $[n]$ and letting $\sigma$ be such that $(i,\sigma(i))$ is an edge of $M$.

Therefore $K_{n,n}$ has exactly $n!$ perfect matchings. It is not immediately clear to me as to whether there is anything gained by thinking of perfect matchings as opposed to just thinking of permutations.

Now move on to disjoint perfect matchings. Two perfect matchings, viewed as permutations $\sigma$, $\tau$ will be disjoint if and only if $\sigma^{-1} \tau$ has no fixed points and therefore is a derangement. If we simply label things so that $\sigma$ is the identity, then $\tau$ will be disjoint from it if and only if it itself is a derangement. Luckily we know the number of derangements, as it is the closest integer to $n!/e$, so we can count the number of disjoint pairs of perfect matchings.

Now we want to add a third perfect matching, disjoint from both. We can write down everything so far in an array, where each row is a permutation written in image format (in other words, just a list $\sigma(1)$, $\sigma(2)$, $\sigma(3)$, etc). So the first row can be the identity, just $1$, $2$, $3$, $\ldots$, $n$ and then the second row will be a derangement, and thus no column of the $2 \times n$ array we have constructed will have a repeated symbol. Adding a third perfect matching disjoint from the two first is precisely equivalent to adding another row to the array such that none of the columns of this $3 \times n$ array have repeated symbols.

This can be continued, until after $d$ pairwise disjoint perfect matchings, we have built a $d \times n$ Latin Rectangle. Simple counting shows that $d \leq n$ because by the time the $n \times n$ Latin square has been constructed every edge lies in a unique perfect matching already accounted for, so there are no more edges.

Counting Latin squares is a well-known very difficult problem, and there is no simple counting technique or formula that can accomplish this.