Ramsey-type theorems with forbidden subgraphs (Q5955193)

P. Erdős and A. Hajnal conjectured that for every finite graph \(H\) every \(H\)-free graph on \(n\) vertices contains a complete or empty subgraph of size \(n^{\varepsilon(H)}\). It is shown that if the conjecture holds for \(H_1\), \(H_2\) then it holds for the graph which is \(H_1\) with one vertex blown up to a copy of \(H_2\). The conjecture is shown to be equivalent to the statement that if \(T\) is a finite tournament then every \(T\)-free tournament on \(n\) vertices contains a transitive subtournament on \(n^{\varepsilon(T)}\) vertices. If \((T,<)\) is an ordered tournament on \(n\) vertices then there is a tournament \(T'\) on \(O(n^3 \log^2 n)\) vertices such that for every ordering \(<'\) of \(T'\), \((T,<)\) appears in \((T',<')\). If \(n_0\) is the largest integer such that \({N \choose n_0}\geq 2^{{n_0 \choose 2}}\), \(n=n_0-2\), for a sufficiently large number \(N\), then there is \(T'\) as above that works for every \((T,<)\) on \(n\) vertices.