A Note on Even Cycles and Quasi-Random Tournaments

Abstract

A cycle $C = \{ v_1, v_2, \ldots , v_1 \}$ 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 $v_{i+1}$ to $v_i$. In this short article, we show that for every fixed even integer $k\geq 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.

Publication
Journal of Graph Theory, Volume 73, Issue 3, pages 260–266
Date