pith. sign in

arxiv: 1410.6828 · v3 · pith:6VWDGAX3new · submitted 2014-10-24 · 🧮 math.CO

On the number of 5-cycles in a tournament

classification 🧮 math.CO
keywords cyclesnumbertournamentalmostfindformulafracmaximum
0
0 comments X
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.