Perfect 1-factorization of $K_{2n}$

Question

For context, $K_{2n}$ is the complete graph on $2n$ vertices (i.e. every pair of vertices have an edge joining them). A $1-$factor (also known as a perfect matching) is a subgraph whose vertices all have degree 1 (and a minimal number of vertices with degree 0). A 1-factorisation is a decomposition of the graph into distinct 1 factors.

My question is then how to find a 1-factorisation for $K_{2n}$ and if there's an easy way to visualise such a decompositon.

After some effort, I'm able to find 1-factorisation for $K_2,K_4,K_6,K_8$. I've written a program that confirms this up to $n=20$. However, even after all that, there doesn't seem to be a clear algorithm on how to proceed, or even why it should be true.

Any hints or reference would be greatly appreciated.

Answer 1

In your title you talk ask about perfect 1-factorisations. For those interested, let $\mathcal{F} = \{F_1, F_2, \cdots, F_r\}$ be a 1-factorisation of an r-regular graph. Two 1-factors $F_i, F_j$ are perfect if the graph obtained from $F_1\cup F_j$ is a single connected component, $i < j$. If every pair of 1-factors in $\mathcal{F}$ is perfect, then $\mathcal{F}$ is perfect.

Now to the question as it pertains to perfect 1-factorisations. For the family of graphs, $K_{2n}$, no general existence results exists, although three infinite families are known. These three families exist only for specific orders. Particularly when $2n-1$ is prime (pattern construction and derived from atomic Latin squares) and when $n$ is prime (even starter derived construction).

I am slightly unsure what you mean when you say you wrote and algorithm to "confirms this up to $n=20$". But generally finding these things as the graphs get large is difficult. As we are unsure if perfect 1-factorisations exist for all n, we can only really say that finding one of these things for any order is equivalent to counting them which is known to be hard.

Here are some (sporadic) references which may have some answers to your questions:

D. Bryant, B. Maenhaut, and I. M. Wanless. New families of atomic Latin squares and perfect 1-factorisations. Journal of Combinatorial Theory, Series A, 113(4):608–624, 2006.

J. H. Dinitz and D. K. Garnick. There are 23 nonisomorphic perfect one-factorizations of $K_{14}$ . Journal of Combinatorial Designs, 4(1):1–4, 1996.

P. Kaski and P. Östergård. There are 1, 132, 835, 421, 602, 062, 347 nonisomorphic one-factorizations of $K_{14}$. Journal of Combinatorial Designs, 2008.

A. J. Wolfe. A perfect one-factorization of $K_{52}$. Journal of Combinatorial Designs, 17(2):190–196, 2009.

P.S. There is a great survey article by Alexander Rosa called "Perfect 1-factorizations" published in Mathematica Slovaca

Answer 2

Turning "@Lord Shark the Unkown" into an answer, from wikipedia :

One method for constructing a $1$-factorization of a complete graph on an even number of vertices involves placing all but one of the vertices on a circle, forming a regular polygon, with the remaining vertex at the center of the circle. With this arrangement of vertices, one way of constructing a $1$-factor of the graph is to choose an edge $e$ from the center to a single polygon vertex together with all possible edges that lie on lines perpendicular to $e$. The $1$-factors that can be constructed in this way form a $1$-factorization of the graph.

In math/programming language : name your vertices $u,v_0, v_1,\ldots,v_{2n-2}$, set $u$ as your center, the others forming the polygon. Then

1. The first $1$-factor is $(uv_0)$ and all edges $(v_{k}v_{2n-1-k})$ with $k=1,\ldots,n-1$
2. The second one is $(uv_1)$ and all edges $(v_{1+k}v_{2n-k \mod 2n-1})$ with $k=1,\ldots,n-1$

and so on, the $i^{\text{th}}$ $1$ factor being, $(uv_i)$ and all edges $(v_{i+k}v_{i-k})$ with $k=1,\ldots,n-1$ and both indexes being taken $\mod 2n-1$, where $i$ goes from $0$ to $2n-2$