GRZESIK, Andrzej, Daniel KRÁĽ, Laszlo M LOVASZ and Jan VOLEC. Cycles of a given length in tournaments. Journal of Combinatorial Theory. Series B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2023, vol. 158, No 1, p. 117-145. ISSN 0095-8956. Available from: https://dx.doi.org/10.1016/j.jctb.2022.07.007. |
Other formats:
BibTeX
LaTeX
RIS
@article{2266377, author = {Grzesik, Andrzej and Kráľ, Daniel and Lovasz, Laszlo M and Volec, Jan}, article_location = {SAN DIEGO}, article_number = {1}, doi = {http://dx.doi.org/10.1016/j.jctb.2022.07.007}, keywords = {Tournament; Oriented cycle; Theory of combinatorial limits; Extremal graph theory}, language = {eng}, issn = {0095-8956}, journal = {Journal of Combinatorial Theory. Series B}, title = {Cycles of a given length in tournaments}, url = {https://doi.org/10.1016/j.jctb.2022.07.007}, volume = {158}, year = {2023} }
TY - JOUR ID - 2266377 AU - Grzesik, Andrzej - Kráľ, Daniel - Lovasz, Laszlo M - Volec, Jan PY - 2023 TI - Cycles of a given length in tournaments JF - Journal of Combinatorial Theory. Series B VL - 158 IS - 1 SP - 117-145 EP - 117-145 PB - ACADEMIC PRESS INC ELSEVIER SCIENCE SN - 00958956 KW - Tournament KW - Oriented cycle KW - Theory of combinatorial limits KW - Extremal graph theory UR - https://doi.org/10.1016/j.jctb.2022.07.007 N2 - 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}. ER -
GRZESIK, Andrzej, Daniel KRÁĽ, Laszlo M LOVASZ and Jan VOLEC. Cycles of a given length in tournaments. \textit{Journal of Combinatorial Theory. Series B}. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2023, vol.~158, No~1, p.~117-145. ISSN~0095-8956. Available from: https://dx.doi.org/10.1016/j.jctb.2022.07.007.
|