On the number of 5-cycles in a tournament
classification
🧮 math.CO
keywords
cyclesnumbertournamentalmostfindformulafracmaximum
read the original 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 $\frac{3}{4}{n \choose 5}$, the expected number 5-cycles in a random tournament ($p=\frac{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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.