Cycles of length three and four in tournaments

DOI10.1016/J.JCTA.2020.105276zbMATH Open1442.05073arXiv1902.00572OpenAlexW2981264517MaRDI QIDQ778712FDOQ778712

Authors: Timothy F. N. Chan, A. Grzesik, Jonathan A. Noel, Daniel Král' 

Publication date: 3 July 2020

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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 $dge1/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 $dge1/16$.

Full work available at URL: https://arxiv.org/abs/1902.00572

Recommendations

• Minimizing cycles in tournaments and normalized \(q\)-norms
• On the number of 4-cycles in a tournament
• Cycles of a given length in tournaments
• On disjoint cycles of the same length in tournaments
• Disjoint 3-cycles in tournaments: a proof of the Bermond-Thomassen conjecture for tournaments

zbMATH Keywords

extremal combinatoricscyclestournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38)

Cites Work

• Limits of dense graph sequences
• Large networks and graph limits
• Title not available (Why is that?)
• The number of cliques in graphs of given order and size
• Lower bounds on the number of triangles in a graph
• On Sets of Acquaintances and Strangers at any Party
• Quick approximation to matrices and applications
• The clique density theorem
• On the Minimal Density of Triangles in Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the characteristic roots of tournament matrices
• Asymptotic structure of graphs with the minimum number of triangles
• On the number of 4-cycles in a tournament
• Quasi-random tournaments

Cited In (11)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Quasirandom-Forcing Orientations of Cycles
• Longest cycles in almost regular 3-partite tournaments
• On the number of 4-cycles in a tournament
• Cycles of length three and four in tournaments
• Cycles in team tennis and other paired-element contests
• Cycles of a given length in tournaments
• Minimizing cycles in tournaments and normalized \(q\)-norms
• On 4-Cycles and 5-Cycles in Regular Tournaments
• Inducibility and universality for trees

This page was built for publication: Cycles of length three and four in tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778712)