The directed Erdős–Hajnal conjecture for tournaments

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

1. Directed Erdős–Hajnal conjecture for tournaments

   Let $H$ be a tournament. A tournament is $H$-free if it does not contain an induced subtournament isomorphic to $H$, and a transitive subtournament is a subtournament containing no directed cycle. Directed Erdős–Hajnal conjecture. For every tournament $H$ there exists $\epsilon(H)>0$ such that every $H$-free tournament with $n$ vertices contains a transitive subtournament of size at least $n^{\epsilon(H)}$. Alon et al. proved that this tournament formulation is equivalent to the undirected Erdős–Hajnal conjecture; the conjecture itself remains open.

   source: Soukaina Zayat and Salman Ghazal, “Erdös-Hajnal Conjecture for New Infinite Families of Tournaments”, arXiv:2010.12329 (2022).