On the number of 5-cycles in a tournament


الملخص بالإنكليزية

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.

تحميل البحث