Cycles of a given length in tournaments

DOI10.1016/J.JCTB.2022.07.007zbMATH Open1505.05050arXiv2008.06577OpenAlexW3048982771MaRDI QIDQ2099412FDOQ2099412

Authors: A. Grzesik, Daniel Král', Jan Volec, László Miklós Lovász 

Publication date: 23 November 2022

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

Abstract: We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let $c(ell)$ be the limit of the ratio of the maximum number of cycles of length $ell$ in an $n$-vertex tournament and the expected number of cycles of length $ell$ in the random $n$-vertex tournament, when $n$ tends to infinity. It is well-known that $c(3)=1$ and $c(4)=4/3$. We show that $c(ell)=1$ if and only if $ell$ is not divisible by four, which settles a conjecture of Bartley and Day. If $ell$ is divisible by four, we show that $1+2cdotleft(2/piight{)}^{ell}lec(ell)le1+left(2/pi+o(1)ight{)}^{ell}$ and determine the value $c(ell)$ exactly for $ell=8$. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length $ell$ when $ell$ is not divisible by four or $ellin4,8$.

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

Recommendations

• Cycles of length three and four in tournaments
• On the number of 5-cycles in a tournament
• On the Number of Hamiltonian Cycles in a Tournament
• On the number of 4-cycles in a tournament
• On 5-cycles and 6-cycles in regular \(n\)-tournaments

zbMATH Keywords

extremal graph theorytournamentoriented cycletheory of combinatorial limits

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

• Large networks and graph limits
• ON THE METHOD OF PAIRED COMPARISONS
• Graph limits and exchangeable random graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Title not available (Why is that?)
• On Sets of Acquaintances and Strangers at any Party
• Regularity partitions and the topology of graphons
• Title not available (Why is that?)
• On the characteristic roots of tournament matrices
• The Maximum Number of Strongly Connected Subtournaments^*
• Cycles of length three and four in tournaments
• On the density of transitive tournaments
• On the number of 7-cycles in regular \(n\)-tournaments
• On 5-cycles and 6-cycles in regular \(n\)-tournaments
• On the number of 5-cycles in a tournament
• Title not available (Why is that?)
• On the maximum density of fixed strongly connected subtournaments
• Tournament quasirandomness from local counting
• No additional tournaments are quasirandom-forcing
• Decomposition of tournament limits
• Impartial digraphs

Cited In (18)

• A note on even cycles and quasirandom tournaments
• The shifted Turán sieve method on tournaments
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of 5-cycles in a tournament
• Quasirandom-Forcing Orientations of Cycles
• Directed simplices in higher order tournaments
• Longest cycles in almost regular 3-partite tournaments
• On the number of 4-cycles in a tournament
• On the number of 7-cycles in regular \(n\)-tournaments
• Cycles of length three and four in tournaments
• On 5-cycles and 6-cycles in regular \(n\)-tournaments
• Cycles in team tennis and other paired-element contests
• Cycles of length three and four in tournaments
• Minimizing cycles in tournaments and normalized \(q\)-norms
• Paths of given length in tournaments
• On 4-Cycles and 5-Cycles in Regular Tournaments
• Inducibility and universality for trees

This page was built for publication: Cycles of a given length in tournaments

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