A Note on Even Cycles and Quasirandom Tournaments. Issue 3 (15th June 2012)

• Record Type: Journal Article
• Authors: Kalyanasundaram, Subrahmanyam; Shapira, Asaf
• Is Part Of: Journal of graph theory. Volume 73:Issue 3(2013)
• Page Start: 260
• Page End: 266
• Publication Date: 2012-06-15
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21671
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A cycle <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tjjs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21671:jgt21671-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>C</mml:mi><mml:mo>=</mml:mo><mml:mo>{</mml:mo><mml:msub><mml:mi>v</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:msub><mml:mi>v</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:mo>...</mml:mo><mml:mo>, </mml:mo><mml:msub><mml:mi>v</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>}</mml:mo></mml:mrow></mml:math> in a tournament <italic>T</italic> is said to be even, if when walking along <italic>C</italic>, 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21671:jgt21671-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>v</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math> to <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4tjmw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21671:jgt21671-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>v</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:math>. 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21671:jgt21671-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math>, if close to half of the <italic>k</italic>‐cycles in a tournament <italic>T</italic> are even, then <italic>T</italic> must be quasirandom.This resolves an open question raised in 1991 by Chung and Graham 1991.</p> </abstract>