论文标题
Erdös-Hajnal的猜想是新的无限锦标赛家庭
Erdös-Hajnal Conjecture for New Infinite Families of Tournaments
论文作者
论文摘要
Erdös-Hajnal的猜想指出，对于每个无方向的图$ h $，都存在$ε（h）> 0 $，以使得不包含$ h $的$ n $顶点上的每个无方向的图形都包含一个诱导的子格言，其中包含一个clique或稳定的大小$ n^{ε（h）} $。该猜想有一个指向的等效版本，指出每个锦标赛$ h $都存在$ε（h）> 0 $，这样每一个$ h- $ n- $ n- $ n- $ vertex Tournament $ t $ t $都包含订单的惯常子量，至少$ n^{ε（h）} $。众所周知，这种猜想是为了几个无限的锦标赛家庭。在本文中，我们建立了两个新的无限锦标赛家庭 - 带有蜘蛛的所谓星系家族和所谓的星号家族，我们证明了这两个家庭的猜想的正确性。
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 known to hold for a few infinite families of tournaments. In this paper we construct two new infinite families of tournaments - the family of so-called galaxies with spiders and the family of so-called asterisms, and we prove the correctness of the conjecture for these two families.
