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 is
$$
2^{1-\binom k3}.
$$
The expected number of monochromatic $k$-sets is therefore
$$
\binom Nk2^{1-\binom k3}
\le2^{1+k\log_2(eN/k)-\binom k3}.
$$
Take $N=\lfloor2^{ck^2}\rfloor$ with any sufficiently small absolute $c>0$. The exponent is negative for large $k$, since its leading terms are $ck^3-k^3/6$. Thus some colouring has no monochromatic $k$-set, proving
$$
\boxed{R^{(3)}(k)\ge2^{ck^2}.}
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-132/2/a/solution