Counting Hamilton decompositions of oriented graphs

A Hamilton cycle in a directed graph G is a cycle that passes through every vertex of G⁠. A Hamilton decomposition of G is a partition of its edge set into disjoint Hamilton cycles. In the late 60s, Kelly conjectured that every regular tournament has a Hamilton decomposition. This conjecture was recently settled for large tournaments by Kühn and Osthus [13], who proved more generally that every r-regular n-vertex oriented graph G (without antiparallel edges) with r=cn for some fixed c>3/8 has a Hamilton decomposition, provided n=n(c) is sufficiently large. In this article, we address the natural question of estimating the number of such decompositions of G and show that this number is n^{(1−o(1))cn^2}⁠. In addition, we also obtain a new and much simpler proof for the approximate version of Kelly’s conjecture.