Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 12 (Techniques in Combinatorics)

Let $Z$ be a real random variable with finite expectation $m$ and finite variance ${\sigma }^2$. The Chebyshev inequality isThe proof is the pointwise comparisonTaking expectations and using the definition of variance givesDivision by the positive number $t^2$ proves the Chebyshev inequality, including the case ${\sigma }^2=0$. Equivalently, this is the Markov inequality applied to the nonnegative random variable $(Z-m{)}^2$.

Write $p=p(n)$ and let $T$ be the triangle count in a binomial random graph. For every three-element set $S$ of vertices, let $I_S$ be the indicator random variable that its three edges are present. ThenFor two distinct triples $S,R$, their indicator random variables are independent random variables unless they share an edge. Sharing just one vertex still leaves the sets of relevant edges disjoint. If they share an edge, their union has five edges, and thereforeThere are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)$ unordered pairs of distinct triangles in a graph sharing an edge: choose that edge, and then choose their two additional vertices. The variance of a sum consequently gives the exact formulaFor sufficiently large $n$, the hypothesis $np\to \infty$ ensures $p>0$, so $\mu >0$. Dropping negative terms and simplifying the binomial coefficients,Here $n^{2}p=n(np)\to \infty$ as well. The event $T\ge 2\mu$ implies $|T-\mu |\ge \mu$. Applying the Chebyshev inequality from part (i) gives the requested conclusion:Thus the triangle count is concentrated around its expectation throughout this range of the binomial random graph.

Use normalized Fourier analysis on a finite abelian group, identifying $A$ with its indicator function $a=1_A$ on the cyclic group ${\mathbb{Z}}_n$. The conventions areThe last operation is normalized convolution on a finite group. With these conventions the Fourier coefficients on a finite abelian group use a normalized average, while sums over frequencies use counting measure.

Expanding the normalized convolution on a finite group and putting $z=x-y$ givesFor the translation of a function $g(x)=f(x-u)$, putting $z=x-u$ yieldsThe two transforms are thereforeThe negative sign in the translation factor follows from the negative sign in our Fourier coefficient on a finite abelian group convention.

Since $a$ is an indicator function of density of a finite subset $\alpha$, the triangle inequality gives $|\hat{a}(r)|\le {\mathbb{E}}_{x}a(x)=\alpha$ for every frequency. Also, character orthogonality and the Parseval identity on a finite group giveFor completeness, the character orthogonality used here iswhich follows by summing a finite geometric series. Expanding the squared Fourier coefficients on a finite abelian group and using this identity proves the displayed Parseval identity on a finite group directly.

Combining the uniform bound with that identity gives the fourth-moment boundIn particular, the Lp norm on the frequency side here is a sum, not a normalized average. This is the fourth Fourier moment bound for an indicator function.

For the physical-space L2 norm use $\Vert h{\Vert }_2^2={\mathbb{E}}_x|h(x){|}^2$. By part (i) and the Parseval identity on a finite group,Split this sum into the large spectrum $K$ and its complement. Because $u$ belongs to the Bohr set in the question, for $r\in K$,Consequently the contribution from $K$ is at most ${\epsilon }^2{\sum }_r|\hat{a}(r){|}^4\le {\epsilon }^2{\alpha }^3$ by part (ii). Outside $K$, $|\hat{a}(r)|<\theta$, and $|1-{\omega }^{-ru}|\le 2$. Thus that contribution is at mostAdding the estimates provesThe argument also covers empty $A$ or empty $K$. As usual the radius and threshold are nonnegative; a negative radius makes the premise empty whenever $K$ is nonempty. The estimate expresses Bohr-set almost periodicity of a convolution: a translation of a function by an element of the Bohr set barely changes the large Fourier coefficients on a finite abelian group, while the small ones have little total energy.

An additive form of the Plünnecke inequality is the following. If $A,B$ are nonempty finite subsets of an abelian group and $|A+B|\le K|A|$, then there is one nonempty $X\subseteq A$ such that, simultaneously for every integer $m\ge 0$,Here $mB$ is an iterated sumset and $0B=\{0\}$. In particular, its Plünnecke-Ruzsa inequality consequence isWe prove both statements, so that the sumset and difference set formulations are covered.

Choose a nonempty $X\subseteq A$ minimizing the ratio $|X+B|/|X|$, and denote this minimum by $\kappa$. Such a minimizer exists because $A$ is finite, and $\kappa \le K$. Every $Z\subseteq X$ satisfies $|Z+B|\ge \kappa |Z|$, with the empty case also valid. We first prove the Petridis minimal-growth lemmafor every finite nonempty $C$.

List $C=\{c_1,\dots ,c_t\}$. Let $U_i=X+\{c_1,\dots ,c_i\}$ and $U_0=\varnothing$. DefineThe new points of $U_i$ are exactly $X_i+c_i$, so $|X+C|={\sum }_i|X_i|$. Since $Z_i+c_i\subseteq U_{i-1}$, the sumset $Z_i+B+c_i$ is already contained in $U_{i-1}+B$. It follows that the new points introduced into $U_i+B$ are contained inAs $Z_i+B\subseteq X+B$, their number is at mostSumming these increments proves the Petridis minimal-growth lemma. Taking $C=(m-1)B$ for $m\ge 1$ and iterating now givesThis proves the Plünnecke inequality with the same minimizing set $X$ for every $m$.

To obtain the difference set bound, we also prove the required Ruzsa triangle inequality. For finite $U,V,Z$ with $Z\ne \varnothing$, choose one representation $d=u_d-v_d$ of each $d\in U-V$. The mapis an injection: the sum of the output coordinates recovers $d$, and the first coordinate then recovers $z$ because $u_d$ was fixed. ThusUse $U=kB$, $V=\ell B$, and $Z=-X$. The already proved Plünnecke inequality yieldsThis finishes the proof of the stated Plünnecke-Ruzsa inequality. The use of an abelian group is essential in commuting the translates and sumsets in the minimal-growth argument.

We derive the triangle removal lemma from the permitted Szemerédi regularity lemma, then turn a corner in an integer grid into a triangle in a graph.

The triangle removal lemma says that for every $\eta >0$ there are $\rho >0$ and $N_0$ such that a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. Here triangles in a graph are unordered triples of distinct vertices. We prove this consequence with the necessary quantitative dependence.

We may assume $0<\eta <1$. Put $d=\eta /4$, choose an integer $m_0\ge 4/\eta$, and chooseApply the Szemerédi regularity lemma to obtain an exceptional class $V_0$ of size at most $\epsilon N$ and equal-sized classes $V_1,\dots ,V_k$ of size $L$, where $m_0\le k\le M$, and at most $\epsilon k^2$ pairs are not regular pairs of vertex sets. The constant $M$ depends only on these chosen parameters. Delete all edges incident with $V_0$, all edges within a class, all edges between irregular pairs, and all edges between pairs whose edge density of a bipartite graph is less than $d$. The respective costs are at mostTheir sum is at most $\eta N^2/2$, hence certainly at most $\eta N^2$.

If a triangle in a graph survives, it lies in three distinct classes whose three pairs are $\epsilon$-regular pairs of vertex sets of edge density of a bipartite graph at least $d$ in the original graph. We now check the needed regular triangle counting lemma. In the first class all but at most $2\epsilon L$ vertices have at least $(d-\epsilon )L$ neighbours in each of the other two classes; otherwise the definition of a regular pair of vertex sets would be violated. For each such vertex $v$, its two neighbour sets each have size at least $\epsilon L$, so their mutual edge density of a bipartite graph is at least $d-\epsilon$. It follows that the original three classes contain at leasttriangles in a graph. The elementary lower bound holds because $\epsilon \le 1/4$ and $\epsilon \le d/4$. Also $L=(N-|V_0|)/k\ge N/(2M)$. Thus a surviving triangle in a graph implies at least $d^3{N}^3/(64M^3)$ original triangles in a graph. Set $\rho =d^3/(128M^3)$ and take $N_0$ large enough for the Szemerédi regularity lemma. Fewer than $\rho N^3$ original triangles in a graph force the cleaned graph to be triangle-free, proving the triangle removal lemma.

Now suppose $0<\delta \le 1$ and $A\subseteq [n{]}^2$. Use the tripartite graph encoding of a grid to construct a tripartite graph with disjoint labelled classesFor each $(a,b)\in A$, put in the three edges joining $a\in X$, $b\in Y$, and $a+b\in Z$. These yield $|A|$ canonical triangles in a graph. They are pairwise edge-disjoint triangles: an $XY$ edge determines $(a,b)$ directly, an $XZ$ edge determines $b=z-a$, and a $YZ$ edge determines $a=z-b$. Any deletion making the graph triangle-free must therefore remove at least $|A|$ edges.

On the other hand, an arbitrary triangle in a graph with labels $(x,y,z)$ gives three points of $A$:Writing $d=z-x-y$, these are $(x,y),(x,y+d),(x+d,y)$. If $d\ne 0$, they form the required corner in an integer grid. If there is no such corner in an integer grid, every triangle in a graph is canonical, and the total number is precisely $|A|\le n^2$.

Apply the triangle removal lemma with $\eta =\delta /32$. The constructed graph has $N=4n$ vertices. For sufficiently large $n$, $N\ge N_0$ andIn the absence of a corner in an integer grid, the triangle removal lemma would destroy all triangles in a graph by deleting at mostedges, contradicting the pairwise edge-disjoint triangles. Every sufficiently large grid therefore has the asserted corner in an integer grid in every subset of positive fixed density of a finite subset. For $\delta >1$ there is no eligible subset, so the assertion is vacuous. This proves the corners theorem, including the stipulated nonzero displacement; no positivity of $d$ was required.

Apply the polynomial method in combinatorics to the finite-field Kakeya set $A$. We will actually obtain the stronger estimateLet $\mathcal{P}$ be the vector space over the prime field ${\mathbb{F}}_p$ of multivariate polynomials in $n$ variables of total degree of a polynomial at most $p-1$. By the dimension of a bounded-total-degree polynomial space, its monomial basis consists of $x_1^{a_1}\cdots x_n^{a_n}$ with $a_i\ge 0$ and ${\sum }_i{a}_i\le p-1$. Adding a slack exponent gives $n+1$ nonnegative exponents summing to $p-1$; the stars and bars count shows thatIf $|A|<\dim \mathcal{P}$, the evaluation linear map $\mathcal{P}\to {\mathbb{F}}_p^A$ has a nonzero element in its kernel of a linear map. Thus there is a nonzero polynomial $P$ of total degree of a polynomial $d\le p-1$ vanishing at every point of $A$. Its degree cannot be zero, since $A$ contains a line and is nonempty. Write $P_d$ for its nonzero top homogeneous polynomial part.

For every nonzero $v\in {\mathbb{F}}_p^n$, the directional hypothesis supplies an affine line in a vector spaceDirections are one-dimensional vector subspaces; rescaling a representative does not change this line. The univariate polynomial $P(a_v+tv)$ has degree at most $d<p$ and vanishes for all $p$ values of $t$. The root bound for a polynomial makes it the zero polynomial. Its coefficient of $t^d$ is exactly $P_d(v)$, so $P_d(v)=0$ for every nonzero $v$. Because $d>0$, $P_d(0)=0$ too.

To finish, we prove the relevant polynomial nonvanishing below the field size. A polynomial over ${\mathbb{F}}_p$ of degree at most $p-1$ in each variable cannot vanish on all of ${\mathbb{F}}_p^n$ unless it is zero. Induct on $n$. The one-variable case is the root bound for a polynomial. For more variables, writeFixing the first $n-1$ coordinates gives a univariate polynomial with $p$ roots of a polynomial, so all its coefficients are zero. Hence every $Q_j$ vanishes on ${\mathbb{F}}_p^{n-1}$, and the induction hypothesis makes every $Q_j$ zero. Applying this to $P_d$, whose total degree of a polynomial is less than $p$, contradicts its choice as nonzero.

Therefore $|A|\ge \dim \mathcal{P}$. Finally,which proves the requested lower bound. The crucial observation in the finite-field Kakeya polynomial bound is that complete lines force the highest homogeneous polynomial part to vanish in every direction.

Use the part-preserving bipartite four-cycle density conventionHere $G(x,y)$ is the indicator function of adjacency, and repeated labels are allowed. This is the homomorphism density convention appropriate to the four-cycle norm. We derive the needed counting and operator norm facts directly.

Let $M=(G(x,y))$ be the $n$-by-$n$ biadjacency matrix, let $1$ be the all-ones vector, let $J=11^{\mathsf{T}}$, and put $H=M-\delta J$. The degree hypothesis saysso the centered matrix $H$ annihilates $1$ on both sides. In particular, $HJ=J{H}^{\mathsf{T}}=0$, andThe two terms have zero products in either order. Expanding the matrix trace directly counts four adjacency factors:Since $J^2=nJ$ and $\mathrm{tr}J=n$, we obtainThe given upper bound therefore impliesThis computation proves the centered four-cycle identity for a biregular graph, rather than assuming a four-cycle norm identity.

The matrix $Q=H{H}^{\mathsf{T}}$ is a positive semidefinite matrix. By the spectral theorem for real symmetric matrices it has nonnegative eigenvalues ${\lambda }_j$, andMoreover, for the Euclidean norm,Indeed $\Vert H^{\mathsf{T}}v{\Vert }_2^2=v^{\mathsf{T}}Qv$, whose maximum on unit vectors is ${\lambda }_{\max }$; the Cauchy-Schwarz inequality characterization $\Vert H{\Vert }_{\mathrm{op}}={\sup }_{\Vert u{\Vert }_2=\Vert v{\Vert }_2=1}|u^{\mathsf{T}}Hv|$ also shows that $H$ and $H^{\mathsf{T}}$ have the same operator norm. Taking fourth roots thus giveswhere the error parameter $c$ is nonnegative, as in the claimed bound.

Finally use the indicator vectors $a=1_A$, $b=1_B$. Their Euclidean norms are $\sqrt{|A|}$ and $\sqrt{|B|}$, so the Cauchy-Schwarz inequality and the operator norm estimate yieldThis is the required discrepancy bound. It also holds when either subset is empty or $\delta =0$. In fact, because $H$ annihilates constants, replacing $a,b$ by $a-\alpha 1,b-\beta 1$ gives the stronger bound $c\delta n^2\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. This is the spectral discrepancy bound for a biregular graph.