On the Number of 5‐Cycles in a Tournament. Issue 3 (27th March 2017)

• Record Type: Journal Article
• Authors: Komarov, Natasha; Mackey, John
• Is Part Of: Journal of graph theory. Volume 86:Issue 3(2017)
• Page Start: 341
• Page End: 356
• Publication Date: 2017-03-27
• Subjects: extremal combinatorics -- tournaments -- 5‐cycles -- cycles -- graph theory; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22130
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We find a formula for the number of directed 5‐cycles in a tournament in terms of its edge scores and use the formula to find 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 5, the expected number 5‐cycles in a random tournament ( p = 1 2 ), with equality (up to order of magnitude) for almost all tournaments.