Efficient Generation of One-Factorizations through Hill Climbing

It is well known that for every even integer $n$, the complete graph $K_n$ has a one-factorization, namely a proper edge coloring with $n-1$ colors. Unfortunately, not much is known about the possible structure of large one-factorizations. Also, at present we have only woefully few explicit constructions of one-factorizations. Specifically, we know essentially nothing about the {\em typical} properties of one-factorizations for large $n$. Suppose that ${\mathcal{C}}_{\mathrm{n}}$ is a graph whose vertex set includes the set of all order-$n$ one-factorizations and that $\Psi: V(\cal C_{\rm n})\to \mathbb R$takesitsminimumpreciselyattheone-factorizations\mathrm{.}Given$\cal C_{\rm n}$and$\Psi$, we can generate one-factorizations via hill climbing. Namely, by taking a walk on ${\mathcal{C}}_{\mathrm{n}}$ that tends to go from a vertex to a neighbor of smaller $\mathrm{\Psi }$. For over 30 years, hill-climbing has been essentially the only method for generating many large one-factorizations. However, the validity of such methods was supported so far only by numerical evidence. Here, we present for the first time hill-climbing algorithms that provably generate an order-$n$ one-factorization in $\text{polynomial}(n)$ steps regardless of the starting state, while all vertex degrees in the underlying graph are appropriately bounded. We also raise many questions and conjectures regarding hill-climbing methods and concerning the possible and typical structure of one-factorizations.