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

DOI10.1017/S0963548317000153MaRDI QIDQ5366972zbMATH OpenOpenAlexFDO

Authors Raphael Yuster

Publication date 10 October 2017

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

Full work available at URL https://arxiv.org/abs/1511.07784

zbMATH Keywords

directed Hamilton cycle\(n\)-vertex tournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

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)gen!/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)ge(e-o(1))n!/2^n$ and it was observed by Alon that already $R(C_n)ge(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 $k$-regular orientation $H$ with $n$ vertices, $T(H)ge(e^k-o(1))n!/2^{e(H)}$ and in fact, for $n$ odd, $R(H)ge(e^k-o(1))n!/2^{e(H)}$.

Recommendations

• On the Number of Hamiltonian Cycles in a Tournament
• The number of oriantations having no fixed tournament
• On the maximum number of Hamiltonian paths in tournaments
• Paths and Cycles in Tournaments
• Hamiltonian Cycles in Regular Tournaments

Cites work

• scientific article; zbMATH DE number 3914351 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• A survey on Hamilton cycles in directed graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Hamiltonian Cycles in Regular Tournaments
• On a packing and covering problem
• On the Number of Hamiltonian Cycles in a Tournament
• On the maximal number of independent circuits in a graph
• On the maximum number of Hamiltonian paths in tournaments
• Problems and results in extremal combinatorics. III.
• The maximum number of Hamiltonian paths in tournaments

Cited in

(5)

• On the Number of Hamiltonian Cycles in a Tournament
• Bounds on the number of compatible \(k\)-simplices matching the orientation of the \((k-1)\)-skeleton of a simplex
• The number of oriantations having no fixed tournament
• On the maximum number of cyclic triples in oriented graphs
• Hamiltonian cycles above expectation in \(r\)-graphs and quasi-random \(r\)-graphs

This page was built for publication: On the maximum number of spanning copies of an orientation in a tournament

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366972)