Cycles of a given length in tournaments
| Authors | |
|---|---|
| Year of publication | 2023 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Combinatorial Theory. Series B |
| MU Faculty or unit | |
| Citation | |
| Web | https://doi.org/10.1016/j.jctb.2022.07.007 |
| Doi | http://dx.doi.org/10.1016/j.jctb.2022.07.007 |
| Keywords | Tournament; Oriented cycle; Theory of combinatorial limits; Extremal graph theory |
| Description | We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let c(l) be the limit of the ratio of the maximum number of cycles of length l in an n-vertex tournament and the expected number of cycles of length l in the random n-vertex tournament, when n tends to infinity. It is well-known that c(3) = 1 and c(4) = 4/3. We show that c(l) = 1 if and only if l is not divisible by four, which settles a conjecture of Bartley and Day. If l is divisible by four, we show that 1 + 2 center dot (2/pi)(l) <= c(l) <= 1 + (2/pi+ o(1))(l) and determine the value c(l) exactly for l = 8. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length l when l is not divisible by four or l is an element of{4, 8}. |
| Related projects: |