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

The uniform hypergraph Ramsey number $R^{(r)}(k)$ is the least $N$ such that every red-blue colouring of the $r$-element subsets of an $N$-element set contains a $k$-element set all of whose $r$-subsets have one colour.

Colour each triple of an $N$-element set independently and uniformly red or blue. For a fixed $k$-set, the probability of being monochromatic isThe expected number of monochromatic $k$-sets is thereforeTake $N=\lfloor 2^{c{k}^2}\rfloor$ with any sufficiently small absolute $c>0$. The exponent is negative for large $k$, since its leading terms are $c{k}^3-k^3/6$. Thus some colouring has no monochromatic $k$-set, proving

We use the Erdős-Rado selection argument. PutStarting with a sufficiently large reservoir, choose vertices $v_1,\dots ,v_m$ in order. After choosing $v_j$, successively halve the remaining reservoir for each $i<j$ so that the colour ofis constant as $x$ ranges over the final reservoir. The total number of halvings is at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$, so $2^{\left(\genfrac{}{}{0ex}{}{m}{2}\right)}+m$ initial vertices suffice.

Colour the pair $ij$, for $i<j<m$, by the stabilized colour of $\{v_i,v_j,v_{\ell }\}$ for $\ell >j$. Among $v_1,\dots ,v_{m-1}$, the definition of $R^{(2)}(k-1)$ gives a monochromatic set of $k-1$ vertices. Adjoining $v_m$ gives a monochromatic $k$-set for the original triple colouring. HenceThe binomial upper bound for a Ramsey number gives $R^{(2)}(k-1)<2^{2k}$, so the right-hand side is at mostfor an absolute $C>0$.

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