All known prime Erd\H{o}s-Hajnal tournaments satisfy \epsilon(H) = \Omega(\frac{1}{|H|^{5}\log(|H|)})

arXiv1410.7046MaRDI QIDQ6255809FDOQ6255809

Authors: Krzysztof Choromanski 

Publication date: 26 October 2014

Abstract: We prove that there exists $C>0$ such that $epsilon(H)geqfracC|H{|}^{5}log(|H|)$, where $epsilon(H)$ is the ErdH{o}s-Hajnal coefficient of the tournament $H$, for every prime tournament $H$ for which the celebrated ErdH{o}s-Hajnal Conjecture has been proven so far. This is the first polynomial bound on the EH coefficient obtained for all known prime ErdH{o}s-Hajnal tournaments, in particular for infinitely many prime tournaments. As a byproduct of our analysis, we answer affirmatively the question whether there exists an infinite family of prime tournaments $H$ with $epsilon(H)$ lower-bounded by $frac1extitpoly(|H|)$, where $extitpoly$ is a polynomial function. Furthermore, we give much tighter bounds than those known so far for the EH coefficients of tournaments without large homogeneous sets. This enables us to significantly reduce the gap between best known lower and upper bounds for the EH coefficients of tournaments. As a corollary we prove that every known prime ErdH{o}s-Hajnal tournament $H$ satisfies: $-5+o(1)leqfraclog(epsilon(H))log(|H|)leq-1+o(1)$. No lower bound on that expression was known before. We also show the applications of those results to the tournament coloring problem. In particular, we prove that for every known prime ErdH{o}s-Hajnal tournament $H$ every $H$-free tournament has extit{chromatic number} at most $O(n^{1-fracC|H{|}^{5}log(|H|)}log(n))$, where $C>0$ is some universal constant. The related coloring can be constructed algorithmically in the quasipolynomial time by following straightforwadly the proof of our main result. In comparison, the standard Ramsey theory gives only $O(fracnlog(n))$ bounds for the tournament chromatic number.

This page was built for publication: All known prime Erd\H{o}s-Hajnal tournaments satisfy $\epsilon(H) = \Omega(\frac{1}{|H|^{5}\log(|H|)})$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6255809)