Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 2 / c / Solution

The blue hypergraph in the question is the three-edge hypergraph $K_4^{(3)-}$. The Erdős-Hajnal bound for the three-edge hypergraph on four vertices states that every $K_4^{(3)-}$-free three-uniform hypergraph on $N$ vertices has an independent set of size at leastIts proof exposes vertices successively and studies their link graphs. A blue triangle in a link is exactly a blue $K_4^{(3)-}$, so all links are triangle-free; applying the Shearer independence bound for a triangle-free graph in dyadic degree ranges either adds vertices to the independent set or leaves a reservoir whose logarithm decreases by only $O(\log \log N)$ per selected vertex. Iteration yields the displayed lower bound.

Now take $N=k^{Ck}$. For sufficiently large $C$,Thus, if there is no blue copy of $H$, the blue hypergraph has an independent $k$-set, which is a red $K_k^{(3)}$. Therefore