Cycles of a given length in tournaments

J 2023

Cycles of a given length in tournaments

GRZESIK, Andrzej, Daniel KRÁĽ, Laszlo M LOVASZ a Jan VOLEC

Základní údaje

Originální název

Cycles of a given length in tournaments

Autoři

GRZESIK, Andrzej (616 Polsko), Daniel KRÁĽ (203 Česká republika, garant, domácí), Laszlo M LOVASZ (348 Maďarsko) a Jan VOLEC (203 Česká republika)

Vydání

Journal of Combinatorial Theory. Series B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2023, 0095-8956

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 1.400 v roce 2022

Kód RIV

RIV/00216224:14330/23:00130429

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1016/j.jctb.2022.07.007

UT WoS

000901805500006

Klíčová slova česky

Turnaj; Orientovaná kružnice; Teorie kombinatorických limit; Extremální teorie grafů

Klíčová slova anglicky

Tournament; Oriented cycle; Theory of combinatorial limits; Extremal graph theory

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 7. 4. 2024 22:53, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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

Návaznosti

MUNI/I/1677/2018, interní kód MU

Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)

Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities

Citovat

GRZESIK, Andrzej, Daniel KRÁĽ, Laszlo M LOVASZ a Jan VOLEC. Cycles of a given length in tournaments. Journal of Combinatorial Theory. Series B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2023, roč. 158, č. 1, s. 117-145. ISSN 0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2022.07.007.

@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 a Jan VOLEC. Cycles of a given length in tournaments. \textit{Journal of Combinatorial Theory. Series B}. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2023, roč.~158, č.~1, s.~117-145. ISSN~0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2022.07.007.

Podrobný výpis o publikaci