Premium
A Note on Even Cycles and Quasirandom Tournaments
Author(s) -
Kalyanasundaram Subrahmanyam,
Shapira Asaf
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21671
Subject(s) - tournament , combinatorics , mathematics , integer (computer science) , point (geometry) , discrete mathematics , computer science , geometry , programming language
A cycle C = { v 1 , v 2 , ... , 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 + 1to v i . In this short article, 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 quasirandom.This resolves an open question raised in 1991 by Chung and Graham 1991.