




















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)} $. 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 size at least $ n^{ε(H)} $. Recently the conjecture was proved for all six-vertex tournaments, except $K_{6}$. In this paper we construct two infinite families of tournaments for which the conjecture is still open for infinitely many tournaments in these two families $-$ the family of so-called super nebulas and the family of so-called super triangular galaxies. We prove that for every super nebula $H_{1}$ and every $Δ$galaxy $H_{2}$ there exist $ε(H_{1},H_{2})$ such that every $\lbrace H_{1},H_{2}\rbrace$$-$free tournament $T$ contains a transitive subtournament of size at least $\mid$$T$$\mid^{ε(H_{1},H_{2})}$. We also prove that for every central triangular galaxy $H$ there exist $ε(K_{6},H)$ such that every $\lbrace K_{6},H\rbrace$$-$free tournament $T$ contains a transitive subtournament of size at least $\mid$$T$$\mid^{ε(K_{6},H)}$. And we give an extension of our results.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。