A note on even cycles and quasirandom tournaments

DOI10.1002/JGT.21671MaRDI QIDQ5325937zbMATH OpenOpenAlexFDO

Authors Subrahmanyam Kalyanasundaram, Asaf Shapira

Publication date 31 July 2013

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.0011

zbMATH Keywords

eigenvaluestournamentquasirandomness

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

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

Recommendations

• Cycles of a given length in tournaments
• Tournament quasirandomness from local counting
• On the density of transitive tournaments
• On explicit random-like tournaments
• No additional tournaments are quasirandom-forcing

Cites work

• Eigenvalues and expanders
• Quasi-Random Set Systems
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Quasi-random graphs
• Quasi-random hypergraphs
• Quasi-random tournaments
• Quasirandom Groups
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Relating singular values and discrepancy of weighted directed graphs

Cited in

(7)

• On the density of transitive tournaments
• 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

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)