Cycles of length three and four in tournaments

DOI10.1016/J.JCTA.2020.105276MaRDI QIDQ778712zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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

Cites work

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

Cited in

(11)

• scientific article; zbMATH DE number 5371651 (Why is no real title available?)
• scientific article; zbMATH DE number 5240517 (Why is no real title available?)
• Longest cycles in almost regular 3-partite tournaments
• Quasirandom-Forcing Orientations of Cycles
• 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)