@article {IOPORT.06095993,
    author       = {Conlon, David and Fox, Jacob and Sudakov, Benny},
    title        = {Erd\H{o}s-Hajnal-type theorems in hypergraphs.},
    year         = {2012},
    journal      = {Journal of Combinatorial Theory. Series B},
    volume       = {102},
    number       = {5},
    issn         = {0095-8956},
    pages        = {1142-1154},
    publisher    = {Elsevier Science (Academic Press), San Diego, CA},
    doi          = {10.1016/j.jctb.2012.05.005},
    abstract     = {Summary: The Erd\H{o}s-Hajnal conjecture states that if a graph on $n$ vertices is $H$-free, that is, it does not contain an induced copy of a given graph $H$, then it must contain either a clique or an independent set of size $n^{\delta (H)}$, where $\delta (H)>0$ depends only on the graph $H$. Except for a few special cases, this conjecture remains wide open. However, it is known that an $H$-free graph must contain a complete or empty bipartite graph with parts of polynomial size. We prove an analogue of this result for 3-uniform hypergraphs, showing that if a 3-uniform hypergraph on $n$ vertices is $\mathcal{H}$-free, for any given $\mathcal{H}$, then it must contain a complete or empty tripartite subgraph with parts of order $c(\log n)^{\frac {1}{2}+\delta (\mathcal{H})}$, where $\delta (\mathcal{H})>0$ depends only on $\mathcal{H}$. This improves on the bound of $c(\log n)^{\frac {1}{2}}$, which holds in all 3-uniform hypergraphs, and, up to the value of the constant $\delta (\mathcal{H})$, is best possible. We also prove that, for $k\ge 4$, no analogue of the standard Erd\H{o}s-Hajnal conjecture can hold in k-uniform hypergraphs. That is, there are $k$-uniform hypergraphs $\mathcal{H}$ and sequences of $\mathcal{H}$-free hypergraphs which do not contain cliques or independent sets of size appreciably larger than one would normally expect.},
    identifier   = {06095993},
}