Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 13 (Combinatorial Probability)

Write $p_i=\mathbb{P}(A_i)$. A strong independence graph of maximum degree one consists of isolated vertices and disjoint pairs. For a component $C$, let $B$ be the event that all events outside $C$ are avoided. Each $A_i$, $i\in C$, is independent of $B$, since the outside vertices are all nonneighbors. The union bound therefore givesRemove the components successively. If every $p_i<1/2$, all these factors are positive, including singleton components, so simultaneous avoidance has positive probability. Conversely, two complementary events of probability $1/2$, joined by one edge, cover the sample space. Consequently $\gamma (1)=1/2$. The argument does not assume joint independence between entire two-event components.

For higher degrees use a dependency-degree obstruction on a rooted tree. Put $d=\Delta -1$ and chooseOn a finite rooted $d$-ary tree take independent bits $B_v$ and define $A_v$ to mean that $B_v=1$ and every child bit is zero. The underlying tree is a strong independence graph: the variables used by $A_v$ are disjoint from all variables used by its nonneighbors. Its maximum degree is at most $d+1$.

Give the leaves success probability $r_0=p$, and, working upwards, useas long as this is less than one. This recursion must reach or exceed one after finitely many steps. Indeed,so the iterates strictly increase. An infinite sequence staying below one would either converge to a fixed point, contradicting the displayed maximum, or tend to one, in which case its next iterate would exceed one. At the first offending step set the root success probability to one instead of the proposed value. Every nonroot event then has probability exactly $p$; the root event has probability $(1-r_j{)}^d\le p$.

Every configuration contains an occurring event: start at the root, whose bit is one; if its event fails, descend to a child whose bit is one, and repeat. A finite tree forces this descent to end at an occurring event. Thus avoidance is impossible. Given any $c>p_{\ast }$, choose $p\in (p_{\ast },\min (c,1))$; all event probabilities are strictly below $c$. This proves

With a cyclically oriented independence digraph of events, each event is independent of one of the other two. Independence is symmetric, so all three pairs are independent events. This does not imply mutual independence. Put $x=\mathbb{P}(A_1\cap A_2\cap A_3)$. The inclusion-exclusion principle givesbecause $x\le \mathbb{P}(A_1\cap A_2)=a^2$. Thus the oriented case guarantees positive avoidance exactly when $0<a<1/2$.

For sharpness, for any $1/2\le a<1$ prescribe the law of the three event indicators by assigning mass $(1-a{)}^2$ to each of the three singleton success patterns, $(1-a)(2a-1)$ to each doubleton, $1-3a+3a^2$ to the tripleton, and zero to the zero-success pattern. All masses are nonnegative and their sum is one. Each marginal isand each pair intersection has mass $(1-a)(2a-1)+(1-3a+3a^2)=a^2$. These events satisfy the oriented independence conditions and have zero avoidance probability.

The unoriented triangle imposes no independence conditions at all: every vertex is adjacent to every other. The union bound gives positive avoidance if $3a<1$. To see that this is sharp for every $a\ge 1/3$, use uniform measure on the circle of circumference one and take three arcs of length $a$ starting at $0,1/3,2/3$. They cover the circle. Hence the unoriented case guarantees positive avoidance exactly when $0<a<1/3$.

The claimed sufficient condition is false for the printed all-colours requirement. This is a polychromatic hypergraph colouring problem, which is stronger than merely avoiding monochromatic edges.

For a counterexample even with $k=3$, take $V=\{1,2,3,4\}$ and all four triples as edges. Every edge meets the other three, so $m=3$, andAny assignment of three colours to four vertices repeats a colour on a pair. Any triple containing that pair has at most two colours. Thus this uniform hypergraph satisfies the numerical hypothesis but has no required colouring. A single two-vertex edge would already provide a smaller counterexample if $k=2$ is allowed.

Here is the correlation graph of events argument that correctly applies to the printed colouring definition. Colour each vertex independently and uniformly with three colours, and let $B_E$ be the event that edge $E$ misses some colour. For $k\ge 1$, the inclusion-exclusion principle givesJoin two bad events when their edges intersect. This is a dependency graph of events, hence also a correlation graph of events, of maximum degree at most $m$: each $B_E$ depends only on colours on $E$, which are jointly independent of the colours on all disjoint edges. Precisely, the symmetric Lovász local lemma says that events of probability at most $q$ with such a graph have positive simultaneous avoidance probability whenever $eq(m+1)\le 1$. It follows from the asymmetric form $q\le x(1-x{)}^m$, taking $x=1/(m+1)$ for $m\ge 1$ and using $(m/(m+1){)}^m\ge e^{-1}$; the case $m=0$ is direct independence.

Thus a valid replacement sufficient condition isor the simpler, stronger condition $3e(m+1)\le (3/2{)}^k$. Under either replacement, avoiding all $B_E$ gives exactly the requested polychromatic hypergraph colouring. For infinitely many vertices, finite subfamilies can be coloured and compactness of the product of three-point spaces extends this to all constraints; positive simultaneous avoidance probability is only asserted for finite families. The printed $3^k$ bound cannot be justified by substituting monochromatic-event probabilities for missing-colour probabilities.

Work on the unbiased Boolean hypercube with values $\{-1,1\}$ for the coordinates and $\{0,1\}$ for $f$. Write its Fourier-Walsh transform asThe flip-probability influences satisfyThese factors of four are essential for zero-one $f$. If $v=0$, the conclusion is immediate. Otherwise suppose, for a contradiction, that $I<2bv$, where $b=\log (1/\beta )/3$. Take $\beta$ small enough that $b\ge 1$. The high-level Fourier weight obeysThis proves the first intermediate claim, including when $b$ is not an integer.

Set $\delta =e^{-1}$ and $r=2/(1+\delta )$. For the discrete derivative of a Boolean function, $D_{i}f$ has magnitude $1/2$ exactly on a set of measure ${\beta }_i$. Beckner's inequality, in the precise form $\Vert T_{\sqrt{\delta }}g{\Vert }_2\le \Vert g{\Vert }_{1+\delta }$ for the noise operator on the Boolean hypercube, yieldsFor $1\le s\le b$, concavity of $\log s-s+1$ shows that $s{\delta }^{s-1}$ is at least the smaller endpoint value $\min (1,b{\delta }^{b-1})$, and this is at least $b{\delta }^b$ since $b{e}^{-b}\le 1$. Therefore the low-level Fourier weight gives the second required intermediate bound:On the other hand, ${\beta }_i\le \beta$ and the assumed bound on $I$ giveCombining these inequalities would imply ${\beta }^{r-1}>{\delta }^b={\beta }^{1/3}$. But $r-1=(1-\delta )/(1+\delta )>1/3$ and $0<\beta <1$, so the inequality is impossible. ConsequentlyIn fact, this proof needs sufficiently small $\beta$ but no separate lower bound on $n$.

Put $v=t(1-t)$ and $M={\max }_i{\beta }_i$. If $v=0$ the assertion is immediate. Otherwise, supposeSince $v\le 1/4$, this makes $M\le \log n/(8n)$, so $M$ is sufficiently small to apply the maximum-influence logarithmic lower bound once $n$ is large. That bound givesFor all sufficiently large $n$, the last quantity exceeds $v\log n/2$, contradicting $nM<v\log n/2$. The choice of sufficiently large $n$ is independent of $t$. Therefore

We prove the following precise form of the Friedgut-Kalai sharp threshold theorem. There is an absolute $C$ such that, for a nontrivial transitive increasing event $A\subseteq \{0,1{\}}^n$, $n\ge 2$, and $0<\epsilon <1/2$, its success probability increases from $\epsilon$ to $1-\epsilon$ over an interval of length at mostIn particular, ${\mu }_p(A)>\epsilon$ and $q-p\ge C\log ((1-\epsilon )/\epsilon )/\log n$, with $p<q<1$, imply ${\mu }_q(A)>1-\epsilon$. Here ${\mu }_p$ denotes independent bits equal to one with probability $p$. Symmetry means invariance under a permutation group acting transitively on the $n$ coordinates, not necessarily invariance under all coordinate permutations.

Use the allowed weighted-cube influence theorem in this exact form: an absolute $c>0$ exists such that, for every $n\ge 2$, $0<p<1$, and zero-one Boolean function of mean $u$ under ${\mu }_p$, some coordinate has pivotal probability at least $cu(1-u)\log n/n$. A coordinate's pivotal event is determined by the other coordinates and means that the two possible values of that coordinate give different outputs. This uniform form is a consequence of the weighted Kahn-Kalai-Linial theorem; it applies to nonsymmetric functions as well.

Write $u(p)={\mu }_p(A)$. Differentiating the finite product expression for $u(p)$, one coordinate at a time, givesThe last equality uses monotonicity, so each summand is the pivotal probability. This derives the Margulis–Russo formula in the normalization being used. Transitivity makes all the influences equal; applying the weighted influence theorem therefore yieldsNontriviality ensures $0<u(p)<1$ throughout $(0,1)$. Dividing and integrating the derivative of the log odds givesAt the two specified quantiles the left side is $2\log ((1-\epsilon )/\epsilon )$. Taking $C=2/c$ proves the window bound and, with a strict starting inequality, the asserted strict final inequality. This is the sharp threshold conclusion, rather than an assumption about a discontinuous finite-$n$ probability curve.

Partition $N=mw$ bits into $m$ tribes of size $w$, and let the tribes function be one when some tribe consists entirely of ones. Permuting tribes and permuting bits within a tribe acts transitively on the $N$ coordinates, so this is a transitive increasing event. Under independent bits of density $p$, its exact success probability isChoose $m=\lfloor (\log 2)2^w\rfloor$. Then $u(1/2)\to 1/2$, while $\log N=w\log 2+O(\log w)$. For fixed $0<x<1$, its unique $x$-quantile isPut $a_x=-\log (1-x)$. Expanding $1-e^{-a_x/m}=a_x/m+O_x(m^{-2})$ givesThus, for fixed $0<\epsilon <1/2$,This positive window prevents an improvement to $o(1/\log N)$ in the Friedgut-Kalai sharp threshold theorem. Moreover, as the fixed error parameter tends to zero, the displayed logarithmic coefficient is $\log (1/\epsilon )+\log \log (1/\epsilon )+o(1)$, so the theorem's logarithmic error dependence is also optimal up to constants. This last comparison takes $w\to \infty$ for each fixed $\epsilon$; the expansion is not being claimed uniformly for arbitrarily tiny $w$-dependent errors.

Use the induced square lattice rectangle with lattice spacings as its side lengths. An open left-to-right crossing and a top-to-bottom crossing of closed dual bonds are mutually exclusive: their embedded paths must intersect, and a primal open bond cannot have its crossing dual bond closed. They are exhaustive. Indeed, explore all vertices connected to the left side by open paths. If that exploration does not reach the right side, the interface separating the explored set from the right side supplies a top-to-bottom path of closed dual bonds. This is the planar crossing alternative for dual bond percolation.

For a primal rectangle of width $m$ and height $n$, the dual crossing can be represented using the dual columns at $1/2,3/2,\dots ,m-1/2$ and the exterior rows at $-1/2,n+1/2$. The terminal portions can be moved horizontally along the wired top and bottom boundary, so the random edges involved have exactly the law of a vertical crossing of a rectangle of width $m-1$ and height $n+1$. ConsequentlyThis is why the boundary offset is needed; one cannot simply assert that a finite square has crossing probability exactly one half. For $m=n+1$ and $p=1/2$, the second term is the same as the first after rotation and translation. ThereforeShortening a rectangle can only help a horizontal crossing, so $h_{1/2}(n,n)\ge 1/2$ as well.

We first derive the reflected attachment estimate for percolation. Put $R=[0,m]\times [0,2n]$, $m\ge n$, and $S=[0,n{]}^2$. Let $X(R)$ require an open vertical crossing of $S$ together with an open path in $R$ attaching it to the right side of $R$. ThenTo prove this, explore the leftmost vertical open crossing $P$ of $S$, revealing bonds on $P$ and to its left, but none strictly to its right. One can implement this exploration by following the boundary of the set accessible from the left using closed dual bonds; its right boundary is the extremal open crossing when that crossing exists. Thus fixing its outcome leaves right-side bonds in their original independent distribution.

For each possible explored $P$, reflect its geometry in $y=n$ and join it to its reflection to obtain a bottom-to-top separator $L$ of $R$. This reflected portion is only a geometrical separator and is not presumed open. Let $Y_{-}$ and $Y_{+}$ mean that an open path from the right boundary reaches, respectively, the lower or upper half of $L$, staying to its right until its endpoint. Any horizontal open crossing of $R$, followed from right to left until its first meeting with $L$, witnesses at least one of these events. Reflection in $y=n$ swaps $Y_{-}$ and $Y_{+}$ and preserves the independent measure. HenceThe bonds tested by $Y_{-}$ remain unexposed after specifying $P$; conditional on that exploration its probability is still the unconditional one for this deterministic separator. Its occurrence attaches the genuinely open lower crossing $P$ to the right side. Average over $P$ to obtain the attachment estimate.

Now take $R=[0,2n]\times [0,2n]$ and $R^{\prime }=[-n,n]\times [0,2n]$, with common corner square $S=[0,n{]}^2$. Use $X(R)$, its horizontal reflection in $R^{\prime }$, and a horizontal open crossing of $S$. The last crossing meets the vertical crossings of $S$ in both attachment events, so these three events give a horizontal crossing of $R\cup R^{\prime }$. All three events are increasing events, so the Harris lemma gives

For all aspect ratios, glue a width-$m_1$, height-$2s$ rectangle to a width-$m_2$, height-$2s$ rectangle with an overlap square of side $2s$. Their horizontal crossings and an overlap vertical crossing imply a crossing of their union. Again the Harris lemma givesAdding a $3s$-wide rectangle therefore yieldsFor height $n\ge 2$, let $s=\lfloor n/2\rfloor$, so $2s\le n$ and $s\ge n/3$. Choose an integer $k\ge \max (3,3\lambda )$. For $m\le \lambda n$, we have $m\le ks$; restricting to height $2s$ and extracting a shorter horizontal crossing givesFor $n=1$, the horizontal bottom-row path gives $h_{1/2}(m,1)\ge 2^{-\lceil \lambda \rceil }$ whenever the allowed integer $m\ge 1$ exists. Thus one may take $c_{\lambda }=\min (2^{17-8k},2^{-\lceil \lambda \rceil })>0$. This proves the requested uniform rectangle crossing in bond percolation bound, rather than assuming the Russo-Seymour-Welsh theorem.

The Harris theorem for square-lattice bond percolation asserts $\theta (1/2)=0$, and hence $p_c\ge 1/2$. Work in the dual square lattice, declaring a dual bond open precisely when its primal bond is closed. At $p=1/2$ this is again independent bond percolation of density one half.

Around a square centered at the origin place four dual rectangles of dimensions $6r$ by $2r$, one on each side, with overlap squares at the corners. Long crossings of all four must meet in the corner squares and their union contains a dual circuit surrounding the central square. The fixed-aspect crossing bound and the Harris lemma give this dual barrier a probability at least $\eta :=c_3^4>0$, independent of $r$.

Take geometrically increasing integer radii, for example with a factor of eight, and shift by half a lattice spacing to lie on the dual lattice. The four-rectangle annuli then have disjoint bond sets. Their barrier events are independent. An infinite primal open path from the origin would have to avoid every closed dual circuit, so the independent annular barriers for percolation giveLetting $j\to \infty$ provesThe extension to smaller $p$ follows by the monotone coupling of Bernoulli percolation. Translation and a countable union also show that no infinite open cluster exists anywhere at $p=1/2$.

The Harris lemma says that, in any finite product of independent Bernoulli coordinates, two increasing events satisfyThe coordinates need not have the same parameter. For completeness, the same statement for increasing functions follows by induction on the number of coordinates. Conditional on the last bit, induction makes the conditional covariance nonnegative; the covariance of the two conditional means is $p(1-p)(a_1-a_0)(b_1-b_0)\ge 0$. The covariance decomposition proves the induction step. Complementing both events gives the inequality for decreasing events too. Finite-cylinder approximation extends it to the countable product setting when needed.

For increasing events $A_1,\dots ,A_r$ of a common probability $a$, their decreasing complements giveTherefore the nth root trick isThis is a lower bound for an individual success probability when a symmetric union is very likely. Without equality of the individual probabilities, the conclusion applies to their maximum. Independence among the $A_j$ is not required.

Let $T$ be the torus graph $(\mathbb{Z}/(5n)\mathbb{Z}{)}^2$, with independent bond density $p$. For $n$ large, all rectangles below are too small to identify any of their own vertices or edges. Let $E_n$ be the event that somewhere in $T$ there is a horizontal open crossing of a $4n$ by $n$ rectangle or a vertical open crossing of an $n$ by $4n$ rectangle. It is increasing and invariant under translations and a quarter turn. These symmetries act transitively on all $50n^2$ bonds, including both orientations. Thus it is a transitive increasing event.

A fixed $4n$ by $n$ rectangle has its ordinary planar distribution, so the supplied lower bound gives ${\mathbb{P}}_{1/2}^T(E_n)>c_4$. Choose any $0<\eta <\min (c_4,1/2)$. Since $p-1/2>0$ is fixed and $\log (50n^2)\to \infty$, the Friedgut-Kalai sharp threshold theorem implies ${\mathbb{P}}_p^T(E_n)>1-\eta$ for all sufficiently large $n$. As $\eta$ is arbitrary,It remains to transfer this symmetric statement to a fixed rectangle, without a growing union-bound loss. On each circular coordinate take the ten positions $a_j=\lfloor jn/2\rfloor$, $0\le j<10$. Consecutive circular gaps are at most $\lceil n/2\rceil$. Use the one hundred $3n$ by $2n$ rectangles starting at pairs $(a_i,a_j)$ and their one hundred quarter-turn images. Every crossed $4n$ by $n$ rectangle contains the full horizontal width of one of the first family, with its vertical span contained in that rectangle's height-$2n$ span: the permissible starting intervals in each coordinate have length $n$, so the chosen positions always supply a suitable start. The crossing, restricted between those two vertical sides, gives a crossing of the chosen $3n$ by $2n$ rectangle. The analogous assertion holds in the rotated family.

Consequently $E_n$ implies at least one of these two hundred increasing crossing events. Their common success probability is $a_n=h_p(3n,2n)$. The nth root trick givesOnly two hundred translates are used, independently of scale. This bounded exponent is the essential finite-torus crossing amplification step.

For a requested height $N$, set $s=\lfloor N/2\rfloor$. Glue $k$ width-$3s$, height-$2s$ rectangles, each successive pair overlapping in a square of side $2s$. Their horizontal crossings and the $k-1$ vertical overlap crossings imply a crossing of the union, which has width $(k+2)s$. An overlap square has crossing probability at least $a_s=h_p(3s,2s)$. Thus the Harris lemma givesChoose $k$ fixed and large enough that $(k+2)s\ge \lambda N$ for all sufficiently large $N$. Increasing height and shortening width can only help, so uniformly for $m\le \lambda N$,In particular it exceeds $1-\epsilon$ for every sufficiently large $N$, with the bound depending only on $p,\lambda ,\epsilon$.

Put $q=1-p_0$. In one-independent bond percolation, bond states in two sets with disjoint endpoint sets are independent as collections. In particular, the states of any finite matching in a graph are mutually independent, by induction on its size. Neither translation invariance nor the Harris lemma is assumed for this law.

If the origin's open cluster is finite, the outer boundary of the union of its vertex-centered unit squares contains a closed dual circuit surrounding the origin. A specified circuit of length $\ell$ corresponds to $\ell$ distinct closed primal bonds. Partition those bonds into four matchings in a graph: horizontal bonds according to the parity of the left endpoint's horizontal coordinate, and vertical bonds according to the parity of the lower endpoint's vertical coordinate. Some class has at least $\ell /4$ bonds. Their mutual independence and their individual closed probabilities at most $q$ implyThis is the Peierls circuit bound for one-independent percolation.

There are at most $4\ell 3^{\ell }$ dual circuits of length $\ell$ enclosing the origin. To obtain this crude bound, choose a crossing of the positive horizontal ray; its distance from the origin is at most $\ell$, since the circuit also extends to the other side of the origin. There are at most $\ell$ choices for its dual edge, at most two orientations, and at most three choices at each subsequent step of a nonbacktracking walk. The stated bound allows extra slack and overcounting. The union bound now givesFor instance choose $p_0=1-10^{-8}<1$, so $x=3q^{1/4}=0.03$. The exact sum isIt follows that $\tilde{\mathbb{P}}(|C_0|=\infty )>0$. This deliberately nonoptimal constant suffices for existence of a universal $p_0$.

Fix $p>1/2$, and use separated-block percolation renormalization to apply the preceding one-independent bond percolation result. Place a squareat each coarse vertex $v\in {\mathbb{Z}}^2$. For a horizontal coarse edge $e=\{v,v+(1,0)\}$, let $R_e$ be the width-$5n$, height-$2n$ rectangle joining the two endpoint squares. Declare $e$ good if $R_e$ has a horizontal open crossing and both endpoint squares have vertical open crossings. For vertical coarse edges use the rotated definition.

The rectangle crossing in bond percolation limit proved above shows that each of these three events has probability tending to one. The Harris lemma givesChoose $n$ so large that every coarse bond has good probability at least the $p_0<1$ from the preceding part.

The good-bond process really is one-independent. Its determining bonds lie entirely in the corresponding $R_e$. Nonincident horizontal coarse edges either lie in rows separated by at least $3n$, while their strips have width $2n$, or in the same row separated by at least one coarse edge; their rectangles are then separated by at least $n$. The vertical case is identical. A horizontal rectangle and a vertical rectangle can intersect only if the horizontal edge's endpoint column is the vertical edge's column and the vertical edge has an endpoint in the horizontal edge's row, which would make the coarse edges incident. Thus sets of nonincident coarse edges use disjoint fine-bond sets, and those sets are independent. The positive gap avoids the shared-boundary-bond problem that occurs with touching block constructions.

An infinite good coarse cluster produces an infinite connected fine open set. To verify connectivity, a long horizontal crossing of $R_e$ contains a horizontal crossing of each endpoint square. It therefore meets every vertical crossing of that square. For collinear good edges the transverse crossing of their shared square joins their long crossings; for perpendicular good edges their long crossings meet inside the shared square. Concatenating along the coarse cluster gives a connected open fine set visiting boxes at arbitrarily large distances.

The one-independent result gives positive probability that the coarse origin belongs to an infinite good cluster. On this event some vertex of the finite square $S_0$ belongs to an infinite fine open cluster. The union bound and translation invariance of the original independent law implyso $\theta (p)>0$. Since this holds for every $p>1/2$, and the Harris theorem for square-lattice bond percolation gives $\theta (p)=0$ for $p\le 1/2$, we obtain the Harris-Kesten theorem: