Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2011 / B (Probabilistic Combinatorics)

Markov's inequality states that for $Y\ge 0$ and $t>0$, $\mathbb{P}(Y\ge t)\le \mathbb{E}Y/t$. It follows by taking expectations in $Y\ge t{1}_{\{Y\ge t\}}$.

If $X$ has finite mean $\mu$ and variance ${\sigma }^2$, apply Markov to $(X-\mu {)}^2$ to obtain Chebyshev's inequality:For the first moment method, assume ${\mu }_n=\mathbb{E}{X}_n\to 0$. Nonnegative integer values give $\{X_n>0\}=\{X_n\ge 1\}$, soFor a standard second moment method, suppose ${\mu }_n>0$ eventually, the second moments are finite, and $\mathbb{E}{X}_n^2/{\mu }_n^2\to 1$. Equivalently, $\mathrm{Var}(X_n)/{\mu }_n^2\to 0$. The zero event is contained in $\{|X_n-{\mu }_n|\ge {\mu }_n\}$, soHence $\boxed{\mathbb{P}(X_n>0)\to 1}$. The second-moment condition controls the fluctuations relative to the mean; a large mean alone is insufficient.

Let $X$ count the four-vertex sets spanning all four of their possible triples. For each such set $S$, write $I_S$ for its indicator. Independence of the four hyperedges givesIf $np\to 0$, then $\mu \le (np{)}^4/24\to 0$, and the first moment method shows that the probability of a four-clique tends to zero.

For the other direction, consider two distinct four-sets. If they meet in at most two vertices, they have no possible triple in common, so their indicators are independent. If they meet in three vertices, they share exactly one triple, so $\mathbb{E}(I_S{I}_T)=p^7$ and their covariance is at most $p^7$. There are $O(n^5)$ ordered pairs of this latter type. The diagonal variances sum to at most $\mu$, henceFor large $n$, $\mu$ is a constant multiple of $n^4{p}^4$, and consequentlyIf $np\to \infty$, the first term tends to zero, and so does the second since $n^{3}p=n^2(np)\to \infty$. The second moment method proves that a four-clique exists with probability tending to one. Therefore a threshold function isThe shared-triple overlap, rather than overlaps in one or two vertices, is the only off-diagonal dependence that affects this computation.

This is the four-clique threshold in a binomial 3-uniform hypergraph.

The requested scale is $\boxed{k=\Theta (\sqrt{\log n})}$. To see its first-moment origin, the number $X_k$ of $k$-cliques has expectationFor $k$ on the proposed scale, taking base-two logarithms givesThe leading terms balance at $k\approx \sqrt{6{\log }_{2}n}$. In particular, for any fixed $c>\sqrt{6}$, taking $k$ near $c\sqrt{{\log }_{2}n}$ makes the expectation tend to zero, so such cliques are absent with probability tending to one.

Thus the first-moment estimate places the largest-clique scale at a constant multiple of $\sqrt{\log n}$, as requested. A diverging expectation below that balance does not itself prove existence; a corresponding probabilistic lower-bound proof would require an additional argument and is not part of the requested first-moment estimate.

A dependency digraph has vertices $1,\dots ,n$ and no loops. For each $i$, the event $A_i$ must be independent of the sigma-algebra generated jointly by all $A_j$ with $j\ne i$ for which there is no edge $i\to j$. Joint independence from that collection is required; pairwise independence alone does not suffice.

Write ${\Gamma }^{+}(i)$ for the outneighbours of $i$, and $B_S={\bigcap }_{j\in S}{A}_j^c$. We prove by induction on $|S|$ that $B_S$ has positive probability and, when $i\notin S$,For $S=\varnothing$, the asserted conditional bound follows from the hypothesis, since its product factors are at most one. For the induction step, positivity for a set of size $r$ follows by writing its avoidance probability as a chain product: all preceding conditioning sets have size below $r$, so each factor is at least $1-x_j>0$.

Now take $|S|=r$, split $S_1=S\cap {\Gamma }^{+}(i)$ and $S_2=S\setminus {\Gamma }^{+}(i)$, and condition first on $B_{S_2}$. Independence gives $\mathbb{P}(A_i\mid B_{S_2})=\mathbb{P}(A_i)$. Moreover, order the elements of $S_1$ and use the inductive conditional bounds on the successive avoidance factors. Their conditioning sets have size at most $r-1$, soThis remains true when $S_1$ is empty, with both sides one. ThereforeThe induction is complete. Finally expand the probability of avoiding all events in the order $1,\dots ,n$:This proves the asymmetric Lovász local lemma, including the positivity needed to make every conditioning step legitimate.

The symmetric Lovász local lemma states: if each bad event has probability at most $p$, each event is independent of the collection of all but at most $d$ other events, andthen the probability that none of the bad events occurs is positive. Independence is from the sigma-algebra generated by the indicated nonneighbours, as in part (a). A sufficient sharper parameter condition is $p\le x(1-x{)}^d$ for some $x\in (0,1)$; taking $x=1/(d+1)$ gives the displayed standard bound when $d\ge 1$. When $d=0$, mutual independence directly gives the conclusion under the displayed bound.

If there are no triangles, any edge colouring works. Otherwise $\Delta \ge 2$. Put $q=\lceil 3\sqrt{\Delta }\rceil$ and colour each edge independently and uniformly from $q$ colours. For each triangle $T$, let $A_T$ be the event that its three edges have one colour. ThenEvents for triangles sharing no edge depend on disjoint edge-colour variables, so each event is jointly independent of the collection of all such nonneighbours. Each edge of a triangle lies in at most $\Delta -2$ other triangles: a common neighbour of its endpoints must be one of at most $\Delta -1$ neighbours besides the other endpoint, and one of these is the third vertex of $T$ itself. Thus the dependency degree is at most $d=3(\Delta -2)$.

Because $q^2\ge 9\Delta$,The symmetric local lemma gives positive probability of avoiding every monochromatic triangle. HenceFor an edgeless graph the empty colouring handles even the zero-colour case $\Delta =0$.

A Galton-Watson process starts with one ancestor, $X_0=1$. Given generation size $X_r$, definewhere all offspring variables are independent with common distribution $Z$. The empty sum is zero, so zero is absorbing. Its extinction probability isFor the probability generating function $f(s)=\mathbb{E}[s^Z]$, the allowed fixed-point characterization isFor binomial offspring, $f(s)=(1-p+ps{)}^k$, with $f(1)=1$, $f^{\prime }(1)=kp$, and $f$ convex on $[0,1]$.

First assume $0<p<1$. If $k=0$, extinction occurs immediately. For $k=1$, $f(s)-s=(1-p)(1-s)>0$ for $s<1$, so the only fixed point is one. For $k\ge 2$, strict convexity givesIf $kp\le 1$, the right-hand side is at least $s$, so no fixed point below one exists and $\eta =1$. If $kp>1$, $f(s)-s<0$ for $s$ just below one, whereas $f(0)>0$. Continuity supplies a fixed point in $(0,1)$; hence $\eta <1$. Thus in the nondegenerate parameter range,For completeness, if binomial endpoint parameters are allowed, $p=0$ or $k=0$ gives $\eta =1$, while $p=1$ and $k\ge 1$ gives deterministic positive offspring and $\eta =0$. In particular $(k,p)=(1,1)$ survives forever despite mean one. Over $k\in \{0,1,\dots \}$ and $p\in [0,1]$, the full condition is

Explore the family tree one individual at a time, maintaining a queue of individuals not yet explored. Initially its size is $Y_0=1$. Exploring individual $t$ removes it and adds its independent offspring $Z_t$, so before the queue empties,One may define the independent increments indefinitely, but the tree exploration stops at $T=\inf \{t:Y_t=0\}$. This hitting time is the total progeny, including the ancestor. Since each increment is at least $-1$, a queue cannot jump below zero before hitting zero. If it never hits zero, the family has infinitely many individuals.

Suppose $kp<1$. A Chernoff bound in moment-generating-function form says that for independent $W_j$ and $\theta >0$,Here take $W_j=Z_j-1$, withWe have $M(0)=1$ and $M^{\prime }(0)=kp-1<0$, so some $\theta >0$ has $M(\theta )<1$. Let $c=-\log M(\theta )>0$. If $T>n$, the queue is still positive after $n$ explorations; its integer value is at least one, giving ${\sum }_{j=1}^n(Z_j-1)\ge 0$. ThereforeThis proves the claimed bound without appealing to a general branching-process tail theorem.

The argument proves the more general exponential total progeny tail for bounded subcritical offspring.

First take $0<p<1$ and $kp>1$. Part (a) gives an extinction probability $\eta \in (0,1)$. Write $p_j=\mathbb{P}(Z=j)$. Conditional on the ancestor having $j$ children, extinction requires extinction of all $j$ independent descendant trees and has probability ${\eta }^j$. Bayes' rule therefore gives the conditional offspring lawIts sum is $f(\eta )/\eta =1$. Conditional on extinction of all descendant trees, those trees remain independent, each with its own extinction-conditioned law. Thus the entire conditioned process is a Galton–Watson process with offspring generating functionFor binomial offspring, using $\eta =(1-p+p\eta {)}^k$ givesIts mean is $k\tilde{p}=f^{\prime }(\eta )<1$. Indeed, $f(s)-s$ is strictly convex and has its two zeros at $\eta$ and one, so its derivative at the first zero is strictly negative. This proves subcriticality directly from the generating function.

Let $T$ be total progeny, taking value infinity on survival. Apply part (b) to the conditioned process. For some $c>0$,Thus the unconditional tail tends to the positive survival probability $1-\eta$, with an exponentially small finite-extinction contribution. It does not decay to zero.

If $p=1$ and $kp>1$, extinction has probability zero and conditioning on it does not specify a probability law. In that deterministic case total progeny is infinite and $\mathbb{P}(T>n)=1$ for every finite $n$.

The nondegenerate law above is the binomial branching process conditioned on extinction.