Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T08:45:33.635Z Has data issue: false hasContentIssue false

On the Maximum Number of Spanning Copies of an Orientation in a Tournament

Part of:Graph theory

Published online by Cambridge University Press:  06 June 2017

RAPHAEL YUSTER*
Affiliation:
Department of Mathematics, University of Haifa, Haifa 31905, Israel (e-mail: raphy@math.haifa.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For an orientation H with n vertices, let T(H) denote the maximum possible number of labelled copies of H in an n-vertex tournament. It is easily seen that T(H) ≥ n!/2e(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 labelled copies of H in an n-vertex regular tournament. In fact, Adler, Alon and Ross proved that for H=C n , the directed Hamilton cycle, T(C n ) ≥ (e−o(1))n!/2n , and it was observed by Alon that already R(C n ) ≥ (e−o(1))n!/2n . 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 fixed k, every k-regular orientation H with n vertices satisfies T(H) ≥ (e k −o(1))n!/2e(H), and in fact, for n odd, R(H) ≥ (e k −o(1))n!/2e(H).

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2017