Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 (Extremal and Probabilistic Combinatorics)

In an independent Bernoulli product space, an event is increasing if changing any coordinate from $0$ to $1$ cannot destroy it. Harris' inequality says that two increasing events $A,B$ satisfyEquivalently, two decreasing events are positively correlated.

For Janson inequalities, let $R$ be a random subset of a finite ground set whose elements are selected independently, let $(S_i{)}_{i\in I}$ be fixed subsets, and putWrite $i\sim j$ when $i\ne j$ and $S_i\cap S_j\ne \varnothing$, and define the ordered dependency sumThe first Janson inequality isThe usual extended form isThere is also the complementary lower boundand if $\mathbb{E}{I}_i\le \epsilon <1$ for all $i$, the product is at least $\exp (-\mu /(1-\epsilon ))$.

For the proof, order $I$ arbitrarily and expose the avoidance events one at a time. The standard Janson sequential product lemma, obtained by conditioning and using Harris' inequality on the coordinates outside $S_i$, givesUsing $1-x\le e^{-x}$ and summing the pair terms yields $e^{-\mu +\Delta /2}$. If $\Delta \le \mu$, this is at most $e^{-\mu /2}$. If $\Delta >\mu$, adjoin an independent Bernoulli coordinate of mean $q=\mu /\Delta$ to each index and intersect $A_i$ with the event that its new coordinate is $1$. The event $X=0$ implies that none of these thinned events occurs, while the thinned family has mean $q\mu$ and dependency sum $q^2\Delta$. Applying the first inequality in the enlarged product space givesFinally, the events $I_i=0$ are decreasing, so repeated Harris' inequality proves the product lower bound; $log(1-x)\ge -x/(1-\epsilon )$ gives its exponential version.

Let $X$ count the triangles of the binomial random graph $G(n,p)$. ThenTwo distinct triangle indicators are dependent only when the triangles share an edge. Hence their ordered Janson dependency sum is

If $0<p\le n^{-1/2}$, then $\Delta =O(\mu )$. The first Janson inequality givesFor the reverse bound, the events that individual triangles are absent are decreasing, so Harris' inequality giveswhere $p<1/2$ keeps the logarithmic estimate uniform. Thus the probability is $e^{-\Theta (p^3{n}^3)}$.

If $n^{-1/2}\le p<1/2$, the extended Janson bound givesFor a lower bound, fix a balanced bipartition of the vertices and require every edge inside either part to be absent. The resulting graph is bipartite, hence triangle-free, and this event has probabilityCombining the bounds proves the second regime.

Put $p=C{n}^{-3/4}$. For any fixed $U\subseteq [n]$ with $|U|\ge 3n/5$, let $X_U$ count copies of the cycle graph $C_4$ in $G[U]$. ThenPairs of distinct $4$-cycles are dependent only when they share an edge. Classifying them by their common paths givesThe first Janson inequality therefore givesfor an absolute $c>0$ and all sufficiently large $n$. Choose $C$ so that $c{C}^4>\log 2+1$. A union bound over the at most $2^n$ choices of $U$ shows that, with high probability, every set of at least $3n/5$ vertices contains a $C_4$.

Now greedily choose vertex-disjoint $4$-cycles until none remains. If fewer than $n/10$ were chosen, they would cover fewer than $2n/5$ vertices, leaving more than $3n/5$ vertices and hence another $C_4$. This contradiction proves that the greedy packing contains at least $n/10$ vertex-disjoint copies.

A set $R\subseteq V(G)$ is $(s,k)$-rich when every $s$-element subset of $R$ has at least $k$ common neighbours.

Choose $t$ vertices $x_1,\dots ,x_t$ independently and uniformly from $V(G)$, allowing repetitions, and letBy Jensen inequality applied to the convex function $z\mapsto z^t$,

Let $Y$ count the $s$-subsets $S\subseteq X$ having fewer than $k$ common neighbours in $G$. For each such $S$, the probability that $S\subseteq X$ issoThe assumed inequality gives $\mathbb{E}(|X|-Y)\ge r$, so some choice has $|X|-Y\ge r$. Delete one vertex from each bad $s$-subset of $X$. The remaining set $R$ has size at least $|X|-Y\ge r$ and contains no bad $s$-subset, so it is $(s,k)$-rich. This is the basic dependent random choice argument.

Embed the part $A$ injectively into the rich set in a graph $R$. List the vertices of $B$ as $b_1,\dots ,b_q$. When embedding $b_i$, the images of its at most $s$ neighbours in $A$ have at least $|H|$ common neighbours in $G$: extend that image set to an $s$-subset of $R$ if necessary, noting that enlarging a set can only shrink its common neighbourhood. At most $|H|-1$ vertices have already been used, so one common neighbour remains available for $b_i$. Choosing it embeds every edge incident with $b_i$ and keeps the map injective. Continuing greedily embeds $H$ in $G$. This is the rich-set embedding lemma.

Let $N=2^{4d}$ and colour the edges of $K_N$ red and blue. One colour, say red, forms a graph $G$ withApply part (a) withIts positive term satisfieswhileThe difference is at least $2^{d-1}$, so $G$ contains a $(d,2^d)$-rich set of size at least $2^{d-1}$.

The hypercube graph $Q_d$ is bipartite according to the parity of the sum of its coordinates. Each part has $2^{d-1}$ vertices, every vertex has degree $d$, and $|Q_d|=2^d$. Part (b) therefore embeds a red copy of $Q_d$. Every red-blue colouring of $K_{2^{4d}}$ has a monochromatic copy, proving

Markov inequality says that a nonnegative random variable $Y$ satisfiesChebyshev inequality says that a random variable with finite variance satisfies

Let $X$ count triangles in $G(n,p)$. The triangle count in a binomial random graph calculation givesSince $p\gg n^{-1}$,For sufficiently large $n$, $\mu >200$, and Chebyshev inequality gives

For a monotone graph property $P=(P_n)$, a function $p^{\ast }(n)$ is a threshold function for a monotone graph property whenand

Write $f_n(q)=\mathbb{P}(G(n,q)\in P_n)$. This is increasing in $q$ by monotone coupling of binomial random graphs, and $f_n(p)=1/10$ by hypothesis.

First let $q/p\to 0$. Choose $k=\lfloor p/(2q)\rfloor$, so $k\to \infty$. The union of $k$ independent copies of $G(n,q)$ has distribution $G(n,q^{\prime })$, whereIf any layer has $P_n$, their union has $P_n$, and henceIt follows that $f_n(q)\le 1-(9/10{)}^{1/k}\to 0$.

Now let $q/p\to \infty$. Choose $k=\lfloor q/(2p)\rfloor$, again tending to infinity. The union of $k$ independent $G(n,p)$ graphs has parameterMonotonicity and independence giveThus $p(n)$ is a threshold function.

Use sprinkling of a binomial random graph to write $G(n,p)=G_1\cup G_2$, where the rounds are independent,and $C$ is chosen large enough that $1-p=(1-p_1)(1-p_2)$. By the given theorem, $G_1$ has a Hamilton cycle $v_1{v}_2\cdots v_n{v}_1$ with high probability.

Condition on such a cycle. For each $3\le \ell \le n-1$, every chord $v_i{v}_{i+\ell -1}$ closes one of the two paths around the Hamilton cycle into a cycle of length $\ell$. There are at least $n/2$ distinct candidate chords, so the probability that $G_2$ supplies none is at mostA union bound over the fewer than $n$ lengths shows that all these cycles occur simultaneously with high probability when $c>4$. The Hamilton cycle itself supplies length $n$, so $G$ is pancyclic.

For disjoint nonempty vertex sets $A,B$, writeThe pair $(A,B)$ is $\epsilon$-uniform ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$, and $|Y|\ge \epsilon |B|$.

The Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0$ there are $M,n_0$ such that every graph on $n\ge n_0$ vertices has a partitionwith $m_0\le m\le M$, $|V_0|\le \epsilon n$, equal sizes $|V_1|=\cdots =|V_m|$, and at most $\epsilon m^2$ pairs $(V_i,V_j)$ that are not $\epsilon$-uniform.

The triangle embedding lemma for regular pairs states that if $0<\epsilon <1/2$, the three pairs among disjoint nonempty sets $A,B,C$ are $\epsilon$-uniform, and all three densities are at least $2\epsilon$, then the graph contains a triangle with one vertex in each set.

In an $\epsilon$-uniform pair $(A,B)$ of density $d$, fewer than $\epsilon |A|$ vertices of $A$ have fewer than $(d-\epsilon )|B|$ neighbours in $B$; otherwise those vertices and $B$ would violate uniformity. Apply this observation to $(A,B)$ and $(A,C)$. Since $2\epsilon <1$, choose $a\in A$ that is typical for both pairs. Thensatisfy $|B^{\prime }|\ge \epsilon |B|$ and $|C^{\prime }|\ge \epsilon |C|$. Uniformity of $(B,C)$ givesThus some $bc$ joins $B^{\prime }$ to $C^{\prime }$, and $abc$ is the required triangle.

For fixed disjoint $A,B$, the random variable $e(A,B)$ has the binomial distribution $\mathrm{Bin}(|A||B|,p)$. A two-sided Chernoff bound givesWhen $|A|,|B|\ge n/\log n$, this is at mostThere are at most $3^n$ ordered disjoint pairs $(A,B)$, since each vertex can lie in $A$, in $B$, or in neither. The union bound therefore makes the probability of any failure at mostwhich proves the simultaneous estimate.

Fix the requested $\epsilon >0$ and choose much smaller constants $\eta ,\delta ,\rho >0$ in that order. Apply the Szemerédi regularity lemma with regularity parameter $\rho$ and a sufficiently large lower bound $m_0$ to a largest triangle-free subgraph $F\subseteq G$. Letbe the resulting equitable partition, and form the reduced graph of a regularity partition $R$ on $[m]$ by joining $i$ and $j$ when $(V_i,V_j)$ is $\rho$-uniform in $F$ and has $F$-density at least $\delta$.

Choose $\rho <\delta /2$. If $R$ contained a triangle, the triangle embedding lemma for regular pairs would give a triangle in $F$. Thus $R$ is triangle-free, and Turan theorem gives

Part (c), with error $\eta$, holds simultaneously for every pair of sets of size at least $n/\log n$. Since $m$ is bounded independently of $n$, all regularity classes and their halves satisfy this size condition for large $n$. It follows that every cross-pair contains at most $(p+\eta )|V_i||V_j|$ edges of $G$. It also givestake a bipartition of $V_i$ carrying at least half its internal edges and apply the cross-pair estimate.

Now count the edges of $F$. Pairs represented in $R$ contribute at mostThe exceptional set, the at most $\rho m^2$ irregular pairs, pairs of $F$-density below $\delta$, and edges inside classes together contribute at mostChoose $\eta$, then $\delta ,ho$, and finally $m_0^{-1}$ small enough in terms of $p\epsilon$. The total is at mostwith high probability, as required.