The Library
Cycles of a given length in tournaments
Tools
Grzesik, Andrzej, Král', Daniel, Lovász, László M. and Volec, Jan (2023) Cycles of a given length in tournaments. Journal of Combinatorial Theory, Series B, 158 (Part 1). pp. 117-145. doi:10.1016/j.jctb.2022.07.007 ISSN 0095-8956.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.jctb.2022.07.007
Abstract
We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let be the limit of the ratio of the maximum number of cycles of length ℓ in an n-vertex tournament and the expected number of cycles of length ℓ in the random n-vertex tournament, when n tends to infinity. It is well-known that and . We show that if and only if ℓ is not divisible by four, which settles a conjecture of Bartley and Day. If ℓ is divisible by four, we show that and determine the value exactly for . We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length ℓ when ℓ is not divisible by four or .
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Journal of Combinatorial Theory, Series B | ||||||
Publisher: | Elsevier | ||||||
ISSN: | 0095-8956 | ||||||
Official Date: | January 2023 | ||||||
Dates: |
|
||||||
Volume: | 158 | ||||||
Number: | Part 1 | ||||||
Page Range: | pp. 117-145 | ||||||
DOI: | 10.1016/j.jctb.2022.07.007 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |