论文标题
关于七个Vertex锦标赛的Erdös-Hajnal猜想
About the Erdös-Hajnal conjecture for seven-vertex tournaments
论文作者
论文摘要
一个著名的尚未解决Erdös和hajnal的猜想指出，对于每一个无方向的图$ H $，存在$ε（h）> 0 $，以至于每$ n $ dertices上的每个无方向的图形都不包含$ h $作为诱导的子仪表包含一个clique或clique或稳定的大小$ n^{ε（该猜想有一个指向的等效版本，指出每个锦标赛$ h $都存在$ε（h）> 0 $，这样每一个$ h- $ n- $ n- $ n- $ vertex toram $ t $ t $都包含订单的惯常子量，至少$ n^{ε（h）} $。猜想的定向版本和无向版本对于小图（锦标赛）都是正确的。到目前为止，猜想仅针对一些特定的主要锦标赛，是根据So $ - $称为替代程序构建的锦标赛，可以构建更大的图表，以及所有五美元 - $ Vertex锦标赛。最近，这一猜想被证明了所有六美元 - $ VERTEX锦标赛，但有一个例外，但是关于所有七个$ - $ VERTEX锦标赛的猜想的正确性仍然开放。在本文中，我们证明了猜想的正确性，几个$ - $顶点锦标赛。
A celebrated unresolved conjecture of Erdös and Hajnal 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)} $. The 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)} $. Both the directed and the undirected versions of the conjecture are known to be true for small graphs (tournaments). So far the conjecture was proved only for some specific families of prime tournaments, tournaments constructed according to the so$-$called substitution procedure allowing to build bigger graphs, and for all five$-$vertex tournaments. Recently the conjecture was proved for all six$-$vertex tournament, with one exception, but the question about the correctness of the conjecture for all seven$-$vertex tournaments remained open. In this paper we prove the correctness of the conjecture for several seven$-$vertex tournaments.
