The local theory of tournaments

The Erd\H{o}s-Hajnal conjecture states that for every graph H there exists an injection of H into G for every large graph G whose largest homogeneous subset (clique or anti-clique) is sub-polynomial in |G|. We formulate a local version of this conjecture, and prove it for all 3-vertex graphs H. We prove the tournament analog for all 4-vertex tournaments H.

We initiate the study of the 4-local profiles of tournaments, and derive some bounds on these sets. In particular, given the number of cycles of length 3, which tournaments minimize the number of cycles of length 4? Given the number of transitive triangles, which tournaments minimize the number of transitive quadruples? We state a conjecture, and derive an almost matching bound. We show that these two questions are equivalent, and describe some related questions. For example: Can the cyclic triangles be uniformly distributed along the edges of a large tournament?  (answer: No, except for trivial cases).

 

Joint Work with Nati Linial.