id: 06095993
dt: j
an: 06095993
au: Conlon, David; Fox, Jacob; Sudakov, Benny
ti: Erdős-Hajnal-type theorems in hypergraphs.
so: J. Comb. Theory, Ser. B 102, No. 5, 1142-1154 (2012).
py: 2012
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: Ramsey theory; Erdős-Hajnal conjecture; hypergraphs
ci: 
li: doi:10.1016/j.jctb.2012.05.005
ab: Summary: The Erdő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^{δ(H)}$, where $δ(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}+δ(\mathcal{H})}$, where $δ(\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 $δ(\mathcal{H})$, is best possible.  We also
    prove that, for $k\ge 4$, no analogue of the standard Erdő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.
rv: