A note on even cycles and quasirandom tournaments
From MaRDI portal
Publication:5325937
DOI10.1002/JGT.21671zbMATH Open1269.05044arXiv1108.0011OpenAlexW1631946858MaRDI QIDQ5325937FDOQ5325937
Authors: Subrahmanyam Kalyanasundaram, Asaf Shapira 
Publication date: 31 July 2013
Published in: Journal of Graph Theory (Search for Journal in Brave)
Abstract: 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+1} to v_i. 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
Full work available at URL: https://arxiv.org/abs/1108.0011
Recommendations
Cites Work
- Eigenvalues and expanders
- Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
- Quasi-random graphs
- Quasi-random hypergraphs
- Quasirandom Groups
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Quasi-Random Set Systems
- Quasi-random tournaments
- Relating singular values and discrepancy of weighted directed graphs
Cited In (7)
- No additional tournaments are quasirandom-forcing
- On the maximum density of fixed strongly connected subtournaments
- Natural quasirandomness properties
- Tournament quasirandomness from local counting
- On explicit random-like tournaments
- Extremal results on feedback arc sets in digraphs
- On the density of transitive tournaments
This page was built for publication: A note on even cycles and quasirandom tournaments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5325937)
