论文标题
锦标赛和强大的Erdős-Hajnal财产
Tournaments and the Strong Erdős-Hajnal Property
论文作者
论文摘要
一个猜想的Alon，Pach和Solymosi等同于著名的Erdős-Hajnal的猜想，他指出，对于每个锦标赛而言，存在$ε（S）> 0 $，如果$ t $是$ n $ n $ vertex的锦标赛，则不包含$ s $ s $ s $ as the $ subtount $，那么$ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t》至少包含一个频繁的零件。 $ n^{ε（s）} $ VERTICES。让$ C_5 $是独特的五个vertex锦标赛，每个顶点都有两个inneneighbors和两个超过两个。对于$ S = C_5 $的情况，已知Alon-Pach-Solymosi猜想是正确的。 Here we prove a strengthening of this result, showing that in every tournament $T$ with no subtorunament isomorphic to $C_5$ there exist disjoint vertex subsets $A$ and $B$, each containing a linear proportion of the vertices of $T$, and such that every vertex of $A$ is adjacent to every vertex of $B$.
A conjecture of Alon, Pach and Solymosi, which is equivalent to the celebrated Erdős-Hajnal Conjecture, states that for every tournament $S$ there exists $ε(S)>0$ such that if $T$ is an $n$-vertex tournament that does not contains $S$ as a subtournament, then $T$ contains a transitive subtournament on at least $n^{ε(S)}$ vertices. Let $C_5$ be the unique five-vertex tournament where every vertex has two inneighbors and two outneighbors. The Alon-Pach-Solymosi conjecture is known to be true for the case when $S=C_5$. Here we prove a strengthening of this result, showing that in every tournament $T$ with no subtorunament isomorphic to $C_5$ there exist disjoint vertex subsets $A$ and $B$, each containing a linear proportion of the vertices of $T$, and such that every vertex of $A$ is adjacent to every vertex of $B$.
