Unavoidable tournaments

详细信息    查看全文

• 作者：Asaf Shapira^a ; ¹ ; ^{asafico@tau.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Raphael Yuster^b ; ^{raphy@math.haifa.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Tournament ; Coloring
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：116
• 期：Complete
• 页码：191-207
• 全文大小：414 K

文摘

A basic result in Ramsey theory states that any tournament contains a “large” transitive subgraph. Since transitive tournaments contain only transitive subgraphs, it is natural to ask which subgraphs must appear in any large tournament that is “far” from being transitive. One result of this type was obtained by Fox and Sudakov who characterized the tournaments that appear in any tournament that is ϵ-far from being transitive. Another result of this type was obtained by Berger et al. who characterized the tournaments that appear in any tournament that cannot be partitioned into a bounded number of transitive sets.

In this paper we consider the common generalization of the above two results, namely the tournaments that must appear in any tournament that is ϵ-far from being the union of a bounded number of transitive sets. Our main result is a precise characterization of these tournaments.