Pairwise compatible Hamilton decompositions of \(K_n\) (Q1364230)

A Hamilton decomposition (respectively Hamilton path decomposition) of a complete graph is a partition of its edges into Hamilton cycles (respectively paths). Two such decompositions are compatible if they do not use the same pair of edges at any vertex. A simple counting argument reveals that there are at most \(2k-1\) pairwise compatible Hamilton decompositions of \(K_{2k+1}\) (respectively Hamilton path decompositions of \(K_{2k}\)). Kotzig asked whether this bound can be achieved for some \(k\) (it cannot for small values of \(k\)). This remains open, and in fact very little was known about lower bounds on the possible numbers of pairwise compatible decompositions. The author gives constructions showing that there are at least \(2k-2\) pairwise compatible Hamilton path decompositions of \(K_{2k}\). (This is just one short of the maximum possible number, as noted above.) For Hamilton decompositions of \(K_{2k+1}\), she also gives constructions providing lower bounds, which are roughly a third of \(2k-1\) when \(k\) is odd or \(2k-1\) is prime, and somewhat smaller otherwise.