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

preprint2015arXivOpen access

Abstract

For an orientation HH with nn vertices, let T(H)T(H) denote the maximum possible number of labeled copies of HH in an nn-vertex tournament. It is easily seen that T(H)≥n!/2e(H)T(H) \ge n!/2^{e(H)} as the latter is the expected number of such copies in a random tournament. For nn odd, let R(H)R(H) denote the maximum possible number of labeled copies of HH in an nn-vertex regular tournament. Adler et al. proved that, in fact, for H=CnH=C_n the directed Hamilton cycle, T(Cn)≥(e−o(1))n!/2nT(C_n) \ge (e-o(1))n!/2^{n} and it was observed by Alon that already R(Cn)≥(e−o(1))n!/2nR(C_n) \ge (e-o(1))n!/2^{n}. Similar results hold for the directed Hamilton path PnP_n. 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 HH 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 kk-regular orientation HH with nn vertices, T(H)≥(ek−o(1))n!/2e(H)T(H) \ge (e^k-o(1))n!/2^{e(H)} and in fact, for nn odd, R(H)≥(ek−o(1))n!/2e(H)R(H) \ge (e^k-o(1))n!/2^{e(H)}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.