RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB

 J. Graph Theory, 2017, Volume 85, Issue 1, Pages 12–21 (Mi jgt1)

On the density of transitive tournaments

L. N. Coreglianoa, A. A. Razborovb

a Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, SP, Brazil
b University of Chicago, Chicago, Illinois 60637

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\ge 4$ is necessarily quasi-random. We present several other characterizations of quasi-random tournaments nicely complementing previously known results and relatively easily following from our proof techniques.

 Funding Agency Grant Number Fundação de Amparo à Pesquisa do Estado de São Paulo 2013/23720-92014/15134-5 Russian Foundation for Basic Research Leonardo Nagami Coregliano: Contract grant sponsor: Fundacão de Amparo à Pesquisa do Estado de São Paulo (FAPESP); Contract grant numbers: 2013/23720-9 and 2014/15134-5. Work done while visiting the University of Chicago. Alexander A. Razborov: Contract grant sponsor: Russian Foundation for Basic Research Part of the work done while the author was at Steklov Mathematical Institute and Toyota Technological Institute at Chicago.

DOI: https://doi.org/10.1002/jgt.22044

Bibliographic databases:

ArXiv: 1501.04074
Revised: 11.03.2016
Language: