2011/07/29 by Subrahmanyam Kalyanasundaram, Asaf Shapira, A. Shapira +2
Computer Science · Mathematics · #Algorithms and Data Compression #Artificial Intelligence in Games #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1108.0011
openalex publication_date 2011/07/29 · arxiv created 2012/06/17 · arxiv updated 2012/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A cycle C=v1,v2,....,v1 in a tournament T is said to be even, if when walking along C, an even number of edges point in the wrong direction, that is, they are directed from vi+1 to vi. In this short paper, we show that for every fixed even integer k >= 4, if close to half of the k-cycles in a tournament T are even, then T must be quasi-random. This resolves an open question raised in 1991 by Chung and Graham