RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
Main page
About this project
Software
Classifications
Links
Terms of Use

Search papers
Search references

RSS
Current issues
Archive issues
What is RSS






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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-9
2014/15134-5
Russian Foundation for Basic Research
Leonardo Nagami Coregliano: Contract grant sponsor: Fundacão de Amparo à Pesquisa do Estado de Sã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
Received: 10.02.2015
Revised: 11.03.2016
Language:

Linking options:
  • http://mi.mathnet.ru/eng/jgt1

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:68

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020