CHAN, Timothy F. N., Andrzej GRZESIK, Daniel KRÁĽ and Jonathan A. NOEL. Cycles of length three and four in tournaments. Journal of Combinatorial Theory, Series A. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2020, vol. 175, No 105276, p. 1-23. ISSN 0097-3165. Available from: https://dx.doi.org/10.1016/j.jcta.2020.105276.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Cycles of length three and four in tournaments
Authors CHAN, Timothy F. N., Andrzej GRZESIK, Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution) and Jonathan A. NOEL.
Edition Journal of Combinatorial Theory, Series A, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2020, 0097-3165.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 1.192
RIV identification code RIV/00216224:14330/20:00118501
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1016/j.jcta.2020.105276
UT WoS 000546725100012
Keywords in English Tournaments; Cycles; Extremal combinatorics
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 26/4/2021 06:29.
Abstract
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. (C) 2020 Elsevier Inc. All rights reserved.
PrintDisplayed: 1/8/2024 12:22