论文标题
锦标赛和埃德斯·哈纳尔（Erdös-Hajnal）猜想
Tournaments and the Erdös-Hajnal Conjecture
论文作者
论文摘要
著名的Erdös-Hajnal的猜想指出，对于每个无方向的图$ h $，都存在$ε（h）> 0 $，以使得不包含$ h $的$ n $顶点上的每个无向图作为诱导的子级包含一个clique或稳定的大小$ n^{ε（h）} $。该猜想有一个指示的等效版本，指出每个锦标赛$ h $都存在$ε（h）> 0 $，因此每个$ h $ h $ n $ n $ n $ -vertex tournament $ t $ t $都包含一个传递订单子订单子，至少包含$ n^{ε（h）} $。对于少数无限的锦标赛家庭，这种猜想被证明是如此。在本文中，我们建立了一个新的无限锦标赛家族，$ - $ $ $由所谓的Flotilla-Galaxies家族，我们证明了每次Flotilla-Galaxy锦标赛的猜想的正确性。
The celebrated Erdös-Hajnal conjecture states that for every undirected graph $H$ there exists $ ε(H) > 0 $ such that every undirected graph on $ n $ vertices that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $ n^{ε(H)} $. This conjecture has a directed equivalent version stating that for every tournament $H$ there exists $ ε(H) > 0 $ such that every $H$-free $n$-vertex tournament $T$ contains a transitive subtournament of order at least $ n^{ε(H)} $. This conjecture is proved for few infinite families of tournaments. In this paper we construct a new infinite family of tournaments $-$ the family of so-called flotilla-galaxies and we prove the correctness of the conjecture for every flotilla-galaxy tournament.
