Cycles of a given length in tournaments

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.

Basic information

• Original name: Cycles of a given length in tournaments
• Authors: GRZESIK, Andrzej (616 Poland), Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution), Laszlo M LOVASZ (348 Hungary) and Jan VOLEC (203 Czech Republic).
• Edition: Journal of Combinatorial Theory. Series B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2023, 0095-8956.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10101 Pure mathematics
• Country of publisher: Netherlands
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• Impact factor: Impact factor: 1.400 in 2022
• RIV identification code: RIV/00216224:14330/23:00130429
• Organization unit: Faculty of Informatics
• Doi: http://dx.doi.org/10.1016/j.jctb.2022.07.007
• UT WoS: 000901805500006
• Keywords (in Czech): Turnaj; Orientovaná kružnice; Teorie kombinatorických limit; Extremální teorie grafů
• Keywords in English: Tournament; Oriented cycle; Theory of combinatorial limits; Extremal graph theory
• Tags: International impact, Reviewed

Abstract

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}.

Links

• MUNI/I/1677/2018, interní kód MU: Name: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)

Investor: Masaryk University, MASH - MUNI Award in Science and Humanities