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

DOI10.1017/S0963548317000153zbMATH Open1371.05111arXiv1511.07784OpenAlexW2963826071MaRDI QIDQ5366972FDOQ5366972

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: 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) g e n! / 2^{e (H)}

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_{n}

the directed Hamilton cycle,

T (C_{n}) g e (e - o (1)) n! / 2^{n}

and it was observed by Alon that already

R (C_{n}) g e (e - o (1)) n! / 2^{n}

. Similar results hold for the directed Hamilton path

P_{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

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