On the number of 5-cycles in a tournament

DOI10.1002/JGT.22130MaRDI QIDQ4596320zbMATH OpenOpenAlexFDO

Authors Natasha Komarov, John Mackey

Publication date 1 December 2017

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

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

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)

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.

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

Cited in

(11)

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