A Note on Even Cycles and Quasirandom Tournaments. Issue 3 (15th June 2012) - Kalyanasundaram, Subrahmanyam; Shapira, Asaf
Abstract A cycle <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tjjs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />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 <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tjh7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />vi+1 to <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tjmw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />vi. In this short article, we show that for every fixed even integer <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tjkb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />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.