Cycles of a given length in tournaments

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GRZESIK Andrzej KRÁĽ Daniel LOVASZ Laszlo M VOLEC Jan

Rok publikování 2023
Druh Článek v odborném periodiku
Časopis / Zdroj Journal of Combinatorial Theory. Series B
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://doi.org/10.1016/j.jctb.2022.07.007
Doi http://dx.doi.org/10.1016/j.jctb.2022.07.007
Klíčová slova Tournament; Oriented cycle; Theory of combinatorial limits; Extremal graph theory
Popis 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}.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info