Quasi-Carousel Tournaments

2015/03/13 by Leonardo Nagami Coregliano, Coregliano, Leonardo Nagami
Mathematics · #05C20 #05C35 (Primary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C20 #msc:05C35

paper · pdf · doi:10.48550/arxiv.1503.04124

26 pages, 5 figures; corrected proofs of Lemma 3.2 and Proposition 4.1

arxiv created 2015/04/15 · arxiv updated 2015/04/16

Abstract

A tournament is called locally transitive if the outneighbourhood and the inneighbourhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments W₄ and L₄, which are the only tournaments up to isomorphism on four vertices containing a unique 3-cycle. On the other hand, a sequence of tournaments (T_n)_n∈ℕ with |V(T_n)| = n is called almost balanced if all but o(n) vertices of T_n have outdegree (1/2 + o(1))n. In the same spirit of quasi-random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of W₄ and L₄ in T_n goes to zero as n goes to infinity.

Related

• On the Density of Transitive Tournaments
• Tournament quasirandomness from local counting
• Forcing Quasirandomness in a Regular Tournament
• Tiling transitive tournaments and their blow-ups
• Cycles of length three and four in tournaments