1School of Mathematical Sciences, Monash University, Melbourne, Australia 2Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland 3Faculty of Informatics, Masaryk University, Brno, Czech Republic 4Mathematics Institute and DIMAP, University of Warwick, Coventry, UK
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 533-539
Citer cet article
Timothy Fong Nam Chan; Andrzej Grzesik; Daniel Kráľ; Jonathan Andrew Noel; Timothy Fong Nam Chan; Andrzej Grzesik; Daniel Kráľ; Jonathan Andrew Noel. Cycles of length three and four in tournaments. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 533-539. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a28/
@article{AMUC_2019_88_3_a28,
author = {Timothy Fong Nam Chan and Andrzej Grzesik and Daniel Kr\'a\v{l} and Jonathan Andrew Noel and Timothy Fong Nam Chan and Andrzej Grzesik and Daniel Kr\'a\v{l} and Jonathan Andrew Noel},
title = { Cycles of length three and four in tournaments},
journal = {Acta mathematica Universitatis Comenianae},
pages = {533--539},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a28/}
}
TY - JOUR
AU - Timothy Fong Nam Chan
AU - Andrzej Grzesik
AU - Daniel Kráľ
AU - Jonathan Andrew Noel
AU - Timothy Fong Nam Chan
AU - Andrzej Grzesik
AU - Daniel Kráľ
AU - Jonathan Andrew Noel
TI - Cycles of length three and four in tournaments
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 533
EP - 539
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a28/
ID - AMUC_2019_88_3_a28
ER -
%0 Journal Article
%A Timothy Fong Nam Chan
%A Andrzej Grzesik
%A Daniel Kráľ
%A Jonathan Andrew Noel
%A Timothy Fong Nam Chan
%A Andrzej Grzesik
%A Daniel Kráľ
%A Jonathan Andrew Noel
%T Cycles of length three and four in tournaments
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 533-539
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a28/
%F AMUC_2019_88_3_a28
Linial and Morgenstern conjectured that, among all $n$-vertex tournaments with $d\binom{n}{3}$ cycles of length three, the number of cycles of length four is asymptotically minimized by a random blow-up of a transitive tournament with all but one part of equal size and one smaller part. We prove the conjecture for $d\ge 1/36$ by analyzing the possible spectrum of adjacency matrices of tournaments. We also demonstrate that the family of extremal examples is broader than expected and give its full description for $d\ge 1/16$.
