Abstract
For an orientation with vertices, let denote the maximum possible number of labeled copies of in an -vertex tournament. It is easily seen that as the latter is the expected number of such copies in a random tournament. For odd, let denote the maximum possible number of labeled copies of in an -vertex regular tournament. Adler et al. proved that, in fact, for the directed Hamilton cycle, and it was observed by Alon that already . Similar results hold for the directed Hamilton path . 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 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 -regular orientation with vertices, and in fact, for odd, .
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.