On the number of 5-cycles in a tournament

2014/10/24 by Komarov, Natasha, Mackey, John
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1410.6828

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 (3)/(4)n \choose 5, the expected number 5-cycles in a random tournament (p=(1)/(2)), 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.

Related

• Cycles of a given length in tournaments
• On the number of 4-cycles in a tournament
• Cycles of length three and four in tournaments
• Computing the clique number of tournaments
• Minimizing cycles in tournaments and normalized q-norms