论文标题
森林和强大的Erdos-Hajnal财产
Forests and the Strong Erdos-Hajnal Property
论文作者
论文摘要
Alon等人提出的著名的未解决的Erdos和Hajnal的指导版本。指出，在每个比赛中都存在Epsilon（H）> 0，因此每个无h-fertex锦标赛都包含一个及时的秩序子赛，至少n^（epsilon（h））。如果存在c> 0，则锦标赛H具有强大的EH-Property > 1，存在不相交的顶点子集A和B，每个基数至少C | T | 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 et al. 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 c|T| 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 construct an infinite class of tournaments - the so-called spiral galaxies and we prove that every spiral galaxy has the strong EH-property.
