Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 / 4

For each $A\in \mathcal{A}$, define over ${\mathbb{F}}_p$Replace every power $x_i^r$ with $r\ge 1$ by $x_i$; this does not change the values on characteristic vectors of sets and produces a multilinear polynomial of degree at most $m$.

At the characteristic vector of $B\in \mathcal{A}$,This is zero when $A\ne B$, whereasThe evaluation matrix is diagonal with nonzero diagonal, so the polynomials $P_A$ are linearly independent. The space of multilinear polynomials of degree at most $m$ has the monomial basis ${\prod }_{i\in S}{x}_i$ for $|S|\le m$ and dimension ${\sum }_{i=0}^m\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. Hence the modular intersection bound for a set family gives

Let $\mathcal{A}$ be an independent set in the graph. Every member has size $p^2\equiv 0(\mathrm{mod}p)$, while for distinct $A,B\in \mathcal{A}$, independence means $|A\cap B|$ is nonzero modulo $p$. Apply part i withThis givesMoreover,

Let $\mathcal{C}$ be a clique and choose the given prime $q$ with $p^2<q<2p^2$. For distinct $A,B\in \mathcal{C}$, the intersection size is a multiple of $p$ strictly below $p^2$. In ${\mathbb{F}}_q$, setThese are $p$ distinct residues because $q>p^2$, every off-diagonal intersection size lies in $E$, and the diagonal size $p^2$ does not. Part i, now over ${\mathbb{F}}_q$, yieldsThe subsets of a $p^3$-element set having size at most $p$ inject into its ordered $p$-tuples: list a nonempty subset increasingly and repeat its final element, while assigning the empty set one decreasing tuple not used in this way. The injection is not surjective, so

Put $k=p^{3p}$. Parts ii and iii give a graph with neither a clique nor an independent set of size $k$. Its number of vertices satisfies the standard binomial lower boundConsequently the modular-intersection graph Ramsey lower bound gives

For every fixed $C>0$,The first quantity exceeds the second when $p>3C$. Thus $p^{p^2}$ is eventually larger than $k^C$ for every fixed $C$, so this lower bound grows faster than every polynomial in $k$.