pith. sign in

arxiv: 1410.7044 · v1 · pith:HHCC3UI7new · submitted 2014-10-26 · 🧮 math.CO

Excluding pairs of tournaments

classification 🧮 math.CO
keywords everytournamentsconjectureleasttransitiveconstantcontaincontains
0
0 comments X
read the original abstract

The Erd\H{o}s-Hajnal conjecture states that for every given undirected graph $H$ there exists a constant $c(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $|V(G)|^{c(H)}$. The conjecture is still open. Its equivalent directed version states that for every given tournament $H$ there exists a constant $c(H)>0$ such that every $H$-free tournament $T$ contains a transitive subtournament of order at least $|V(T)|^{c(H)}$. We prove in this paper that $\{H_{1},H_{2}\}$-free tournaments $T$ contain transitive subtournaments of size at least $|V(T)|^{c(H_{1},H_{2})}$ for some $c(H_{1},H_{2})>0$ and several pairs of tournaments: $H_{1}$, $H_{2}$. In particular we prove that $\{H,H^{c}\}$-freeness implies existence of the polynomial-size transitive subtournaments for several tournaments $H$ for which the conjecture is still open ($H^{c}$ stands for the \textit{complement of $H$}). To the best of our knowledge these are first nontrivial results of this type.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.