Premium
On the Number of 5‐Cycles in a Tournament
Author(s) -
Komarov Natasha,
Mackey John
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22130
Subject(s) - tournament , mathematics , combinatorics , upper and lower bounds , enhanced data rates for gsm evolution , order (exchange) , discrete mathematics , computer science , mathematical analysis , economics , telecommunications , finance
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 to3 4n 5, the expected number 5‐cycles in a random tournament ( p = 1 2 ), with equality (up to order of magnitude) for almost all tournaments.