论文标题
星系和强大的Erdos-Hajnal属性
Galaxies and the Strong Erdos-Hajnal Property
论文作者
论文摘要
Alon，Pack和Solymosi提出的著名尚未解决的Erdos和Hajnal的同等定向版本指出，每个锦标赛中都存在Epsilon（H）> 0，因此每个H-Free N-Fertex锦标赛都包含订单的及至少n^（Epsilon（epsilon（h）））。如果存在c> 0，则锦标赛H具有强大的EH-Property > 1，存在不相交的顶点子集A和B，每个基数至少| t | n，A的每个顶点与B. Berger等人的每个顶点相邻。证明了C5表示的独特的五个胜利锦标赛，每个顶点都有两个Inneighbors，而两个Outeighbors具有强大的EH-Property。众所周知，与强大的EH-Property的每场比赛都有EH-Property。在本文中，我们证明可以按照后卫形成的图表进行订购的锦标赛是一片由树木组成的森林，该森林最多有两个边缘，而在顶点订购下的连续叶子则具有强大的EH-Property。
An equivalent directed version of the celebrated unresolved conjecture of Erdos and Hajnal proposed by Alon, Pack, and Solymosi states that for every tournament H there exists epsilon(H)>0 such that every H-free n-vertex tournament T contains a transitive subtournament of order at least n^(epsilon(H)). A tournament H has the strong EH-property if there exists c > 0 such that for every H-free tournament T with |T| > 1, there exist disjoint vertex subsets A and B, each of cardinality at least |T|n and every vertex of A is adjacent to every vertex of B. Berger et al. proved that the unique five-vertex tournament denoted by C5, where every vertex has two inneighbors and two outneighbors has the strong EH-property. It is known that every tournament with the strong EH-property also has the EH-property. In this paper we prove that tournaments that can be ordered in a way that the graph formed by the backedges is a forest consisting of trees with at most two edges and consecutive leaves under the vertex ordering has the strong EH-property.
