The Library
Cycles of length three and four in tournaments
Tools
Tools
Tools
Chan, Timothy F. N., Grzesik, Andrzej, Králʼ, Daniel and Noel, Jonathan A. (2020) Cycles of length three and four in tournaments. Journal of Combinatorial Theory, Series A, 175 . 105276. doi:10.1016/j.jcta.2020.105276 ISSN 0097-3165.
|
PDF
WRAP-cycles-length-three-four-tournaments-Kral-2019.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (619Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jcta.2020.105276
Abstract
Linial and Morgenstern conjectured that, among all n-vertex tournaments with 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 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 .
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Combinatorial analysis, Cycles, Algebraic, Extremal problems (Mathematics) | ||||||||||||
| Journal or Publication Title: | Journal of Combinatorial Theory, Series A | ||||||||||||
| Publisher: | Elsevier BV | ||||||||||||
| ISSN: | 0097-3165 | ||||||||||||
| Official Date: | October 2020 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 175 | ||||||||||||
| Article Number: | 105276 | ||||||||||||
| DOI: | 10.1016/j.jcta.2020.105276 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| Date of first compliant deposit: | 19 September 2019 | ||||||||||||
| Date of first compliant Open Access: | 9 June 2021 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Related URLs: | |||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
