Publication details

CYCLES OF LENGTH THREE AND FOUR IN TOURNAMENTS

Authors

CHAN Timothy Fong Nam GRZESIK Andrzej KRÁĽ Daniel NOEL Jonathan Andrew

Year of publication 2019
Type Article in Periodical
Magazine / Source Acta Mathematica Universitatis Comenianae
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1222
Keywords Tournaments; extremal combinatorics
Description Linial and Morgenstern conjectured that, among all n-vertex tournaments with d((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 >= 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 >= 1/16.