Cycles of a given length in tournaments

DOI10.1016/J.JCTB.2022.07.007MaRDI QIDQ2099412zbMATH OpenOpenAlexFDO

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)

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

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)

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

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

Cites work

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

Cited in

(18)

• A note on even cycles and quasirandom tournaments
• The shifted Turán sieve method on tournaments
• scientific article; zbMATH DE number 5371651 (Why is no real title available?)
• scientific article; zbMATH DE number 5240517 (Why is no real title available?)
• On the number of 5-cycles in a tournament
• Longest cycles in almost regular 3-partite tournaments
• Quasirandom-Forcing Orientations of Cycles
• Directed simplices in higher order 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)