Premium
On the Density of Transitive Tournaments
Author(s) -
Coregliano Leonardo Nagami,
Razborov Alexander A.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22044
Subject(s) - tournament , mathematics , combinatorics , transitive relation , order (exchange) , sequence (biology) , discrete mathematics , finance , biology , economics , genetics
Abstract We prove that for every fixed k , the number of occurrences of the transitive tournament Tr k of order k in a tournament T n on n vertices is asymptotically minimized when T n is random. In the opposite direction, we show that any sequence of tournaments { T n } achieving this minimum for any fixed k ⩾ 4 is necessarily quasirandom. We present several other characterizations of quasirandom tournaments nicely complementing previously known results and relatively easily following from our proof techniques.