On the maximum number of spanning copies of an orientation in a tournament

الأصل · EN

For an orientation H with n vertices, let T(H) denote the maximum possible number of labeled copies of H in an n-vertex tournament. It is easily seen that T(H) ≥ n!/2ᵉ⁽ʰ⁾ as the latter is the expected number of such copies in a random tournament. For n odd, let R(H) denote the maximum possible number of labeled copies of H in an n-vertex regular tournament. Adler et al. proved that, in fact, for H=Cₙ the directed Hamilton cycle, T(Cₙ) ≥ (e-o(1))n!/2ⁿ and it was observed by Alon that already R(Cₙ) ≥ (e-o(1))n!/2ⁿ. Similar results hold for the directed Hamilton path Pₙ. In other words, for the Hamilton path and cycle, the lower bound derived from the expectation argument can be improved by a constant factor. In this paper we significantly extend these results and prove that they hold for a larger family of orientations H which includes all bounded degree Eulerian orientations and all bounded degree balanced orientations, as well as many others. One corollary of our method is that for any k-regular orientation H with n vertices, T(H) ≥ (eᵏ-o(1))n!/2ᵉ⁽ʰ⁾ and in fact, for n odd, R(H) ≥ (eᵏ-o(1))n!/2ᵉ⁽ʰ⁾.