On the Number of 5‐Cycles in a Tournament |
| |
| Authors: | Natasha Komarov John Mackey |
| |
| Institution: | 1. DEPARTMENTS OF MATHEMATICS, COMPUTER SCIENCES, AND STATISTICS, ST. LAWRENCE UNIVERSITY, CANTON, NY;2. DEPARTMENT OF MATHEMATICS, CARNEGIE MELLON UNIVERSITY, PITTSBURGH, PA |
| |
| 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  , the expected number 5‐cycles in a random tournament ( ), with equality (up to order of magnitude) for almost all tournaments. |
| |
| Keywords: | extremal combinatorics tournaments 5‐cycles cycles graph theory |
|
|
, the expected number 5‐cycles in a random tournament (
), with equality (up to order of magnitude) for almost all tournaments.