On the number of 5-cycles in a tournament

DOI10.1002/JGT.22130zbMATH Open1375.05118arXiv1410.6828OpenAlexW2963441217MaRDI QIDQ4596320FDOQ4596320

Authors: Natasha Komarov, John Mackey 

Publication date: 1 December 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We find an exact formula for the number of directed 5-cycles in a tournament in terms of its edge score sequence. We use this formula to find both upper and lower bounds on the number of 5-cycles in any $n$-tournament. In particular, we show that the maximum number of 5-cycles is asymptotically equal to $frac34nchoose5$, the expected number 5-cycles in a random tournament ($p=frac12$), with equality (up to order of magnitude) for almost all tournaments. Note that this means that almost all $n$-tournaments contain the maximum number of $5$-cycles.

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

Recommendations

• On 5-cycles and 6-cycles in regular \(n\)-tournaments
• On the Number of Hamiltonian Cycles in a Tournament
• Cycles of a given length in tournaments
• On the number of 4-cycles in a tournament
• The number of oriantations having no fixed tournament

zbMATH Keywords

extremal combinatoricstournaments5-cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cited In (11)

• Bounds on the number of compatible \(k\)-simplices matching the orientation of the \((k-1)\)-skeleton of a simplex
• The shifted Turán sieve method on tournaments
• Structure theorem for \(U_{5}\)-free tournaments
• Quasirandom-Forcing Orientations of Cycles
• On the number of 4-cycles in a tournament
• On the number of 7-cycles in regular \(n\)-tournaments
• On 5-cycles and 6-cycles in regular \(n\)-tournaments
• The number of oriantations having no fixed tournament
• Cycles of a given length in tournaments
• Minimizing cycles in tournaments and normalized \(q\)-norms
• On 4-Cycles and 5-Cycles in Regular Tournaments

This page was built for publication: On the number of 5-cycles in a tournament

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