Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 1

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.