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

For $k\ge 1$, monotonicity of the logarithm givesThus $k!\ge (k/e{)}^k$. Bounding the numerator of the binomial coefficient by $n^k$ yields

The function $x-\log (1+x)$ has derivative $x/(1+x)$, is zero at zero, and is nonnegative for every $x>-1$. Therefore $\log (1+x)\le x$. Multiplying by $m>0$ and exponentiating givesEquality occurs at $x=0$.

Each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered vertex pairs has two independent choices of orientation. Hence the number of tournaments on the specified labelled vertex set is

Orient each edge independently and uniformly. Fix a $k$-set $A$. An outside vertex beats every member of $A$ with probability $2^{-k}$. For different outside vertices these events depend on disjoint sets of edges, so they are independent. ThusA union bound over all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ possible sets givesThe complementary event has positive probability, proving a tournament with the required domination property exists. This applies in the intended nonvacuous range $n\ge k$; the asymptotic construction below has $n>k$.

For large $k$, chooseUsing the two inequalities proved in part (a), the logarithm of the union bound is at mostNow ${\log }_e(en/k)=k{\log }_{e}2+{\log }_{e}k+O(1)$, whereas $(n-k)2^{-k}=k^2{\log }_{e}2+2k{\log }_{e}k+o(1)$. Their difference isfor all sufficiently large $k$. The existence criterion therefore applies. Since the chosen $n$ satisfieswe obtain $\boxed{f(k)\le k^2{2}^k({\log }_{e}2)(1+o(1))}$, with the usual convention that the tournament has at least $k$ vertices. If orders below $k$ were permitted, the property would be vacuous there; the same upper bound remains valid but the extremal definition would be uninteresting.

Explore the individuals one at a time, maintaining the number of discovered but unprocessed individuals. It starts at $S_0=1$. Processing one individual removes it and adds its offspring, soThe offspring choices make these increments independent. Exploration stops when the queue first becomes empty; every processed individual has then been counted exactly once. Hencewith $K=\infty$ if the walk never hits zero. The increment sequence can be extended independently beyond the stopping time for probability estimates.

The event $K=k$ implies $S_k=0$. If $B_k$ counts the positive increments, then $B_k\sim \mathrm{Bin}(k,p)$ and $S_k=1+2B_k-k$. Let $\delta =|p-1/2|>0$.

For $p>1/2$, $S_k=0$ forces $B_k=(k-1)/2\le k/2$, so the lower-tail Hoeffding form of the Chernoff bound givesFor $p<1/2$ and $k\ge 1/\delta$, the required value is at least $kp+\delta k/2$. The upper-tail bound gives $\mathbb{P}(K=k)\le e^{-{\delta }^{2}k/2}$.

To include all smaller positive integers, note that each finite-time atom has probability strictly less than one: at $k=1$ its probability is $1-p<1$, while for $k>1$ immediate extinction already has positive probability and excludes $K=k$. Over the finitely many small $k$ with nonzero atom, take the minimum of $-k^{-1}\log \mathbb{P}(K=k)$ and the applicable tail constant. This minimum is positive, and zero atoms impose no restriction. Thus for both cases there is $c>0$ such thatIn the supercritical case this bounds the finite atoms, not the positive probability of $K=\infty$.

Let $Z_r$ be the size of generation $r$, with $Z_0=1$. Its offspring mean is $2p$, so conditioning on the previous generation gives $\mathbb{E}{Z}_r=(2p{)}^r$. At $p=1/2$,The interchange uses Tonelli's theorem for nonnegative variables. Critical extinction is nevertheless almost sure: its probability is the smallest root in $[0,1]$ of $s=(1+s^2)/2$, whose only root is one. Hence $K$ is finite almost surely. If all its finite atoms had the exponential bound, then $\mathbb{E}K\le {\sum }_{k\ge 1}k{e}^{-ck}<\infty$, a contradiction.

For $p>1/2$ the extinction probability is $(1-p)/p<1$. There is positive mass at $K=\infty$, so the mean is infinite even if every finite atom decays exponentially. This is precisely why the critical contradiction does not extend to the supercritical case.

The general Lovász local lemma concerns events $A_1,\dots ,A_m$ with a dependency graph: each $A_i$ is independent of the sigma-algebra generated by all nonneighbouring events other than itself. If numbers $x_i\in [0,1)$ satisfythen $\mathbb{P}({\bigcap }_i{A}_i^c)\ge {\prod }_i(1-x_i)>0$.

Its symmetric form states that if $\mathbb{P}(A_i)\le q$, every dependency degree is at most $d$, and $eq(d+1)\le 1$, then there is positive probability that no event occurs. For $d\ge 1$, set all $x_i=1/(d+1)$. Sincewe have $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge q$, so the general form applies. The displayed inequality follows from $d\log (1+1/d)\le 1$. When $d=0$, the events are mutually independent and each has probability below one, so their complements have positive joint probability directly.

Each row sum is a sum of $k$ independent random signs. For $s>0$, its moment generating function isFor example, $\log \cosh s\le s^2/2$ follows by integrating $\tanh s\le s$ for $s\ge 0$. Markov's inequality yields $\mathbb{P}(Y_j\ge t)\le \exp (-st+k{s}^2/2)$. Choosing $s=t/k$ gives $e^{-t^2/(2k)}$ for $t>0$. The distribution is symmetric, so the same bound applies to its negative tail. A union bound provesfor $t\ge 0$, including the trivial endpoint $t=0$.

Let $t=\sqrt{2k{\log }_e(6kr)}$ and define $A_j=\{|Y_j|\ge t\}$. The preceding estimate gives $\mathbb{P}(A_j)\le 1/(3kr)$. An event depends only on the $k$ signs in that row. Each such column occurs in at most $r-1$ other rows, so its dependency degree is at most $d=k(r-1)$. Events on disjoint sets of signs are independent even jointly, giving the required dependency graph.

For positive $k,r$,The symmetric Lovász local lemma therefore gives positive probability that no $A_j$ occurs. Such a sign vector satisfiesThe positive-parameter assumption is implicit in the printed square-root expression. If all rows are zero, all row sums vanish and no probabilistic construction is needed.

Chebyshev's inequality says that for a random variable $Z$ with finite mean and variance, and every $t>0$,

For each cyclic starting position $i$, let $I_i$ indicate that the next $k$ entries are all one. Then $X={\sum }_i{I}_i$ and $\mathbb{E}{I}_i=p^k$, hence $\mathbb{E}X=n{p}^k$.

For two starts separated by $j\in \{1,\dots ,k-1\}$ along either direction, their runs overlap in $k-j$ positions, so $\mathbb{E}(I_i{I}_{i+j})=p^{k+j}$. All other distinct starts use disjoint entries and are independent. Since $k\le n/2$, the two directions' overlap ranges do not intersect. Summing the variances and covariances givesIn particular, dropping negative terms and summing a geometric series yieldswhen $p\le 1/2$. The formula also covers $k=1$ with an empty covariance sum.

For $p=1/2$ and $k={\log }_{2}n+\omega (n)$,If $\omega (n)\to \infty$, the mean tends to zero. Markov's inequality gives $\mathbb{P}(X\ge 1)\le \mathbb{E}X\to 0$, so $\boxed{\mathbb{P}(X=0)\to 1}$.

Now $\omega (n)\to -\infty$ makes $\mathbb{E}X=2^{-\omega (n)}\to \infty$. Chebyshev's inequality and the variance bound giveFor every fixed $ϵ>0$, they likewise giveThus the count is concentrated about its growing mean, despite the overlapping runs.

For $p=1/4$, use $k={\log }_{4}n+\omega (n)$. Then $\mathbb{E}X=4^{-\omega (n)}$, so its limits are exactly those needed for the same two arguments.

For $p=1/{\log }_{e}n$, a convenient definition that also accounts for the varying probability isIt makes $\mathbb{E}X=e^{-\omega (n)}$. Thus $\omega \to +\infty$ gives no runs with high probability, and $\omega \to -\infty$ gives runs and relative concentration. For sufficiently large $n$, $p\le 1/2$, so the same uniform variance bound applies. Definitions are made from the actual integer $k$; no continuous rounding assumption is required. These conclusions retain the stipulated range $1\le k\le n/2$.