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

Chebyshev's inequality states that if $X$ has finite mean $\mu$ and variance ${\sigma }^2$, then for $t>0$,Indeed $(X-\mu {)}^2\ge t^2{1}_{\{|X-\mu |\ge t\}}$ pointwise. Taking expectations proves the result, including the zero-variance case.

The assumptions implyEventually ${\mu }_n>0$, and $X_n=0$ implies $|X_n-{\mu }_n|\ge {\mu }_n$. Thus Chebyshev's inequality givesNo independence between the different $X_n$ is needed; this is a second moment method.

For each cyclic starting position let $I_i$ indicate that its length-$k$ block is increasing. All $k!$ relative orders of its distinct entries are equally likely, so $\mathbb{E}{I}_i=1/k!$. By linearity of expectation,The indicators need not be independent for this calculation.

Write $X_k={\sum }_i{I}_i$. For two disjoint blocks, their relative orders are independent and each is increasing with probability $1/k!$, giving joint probability $1/(k!{)}^2$. If their cyclic starting positions differ by $s$, with $1\le s<k$, and $k\le n/2$, they overlap in just one interval. Both blocks increasing is then equivalent to their entire length-$k+s$ union increasing, so the joint probability is $1/(k+s)!$.

For each $s$ there are $2n$ ordered overlapping pairs, while there are $n(n-2k+1)$ ordered disjoint pairs and $n$ diagonal pairs. Thus for $k\ge 2$,The tail is bounded using $(k+s)!\ge k!(k+1{)}^s$:Dropping the negative correction in the disjoint term provesFor $k=1$, $X_1=n$ deterministically and the same bound is immediate.

Take $k=k_0=\min \{j:j!\ge n\}$. Then $k\to \infty$ and $(k-1)!<n\le k!$. Also $k=O(\log n)$, because $j!\ge 2^{j-1}$, so the needed block lengths are below $n/2$ for large $n$.

If $L\ge k+1$, then $X_{k+1}\ge 1$. Markov's inequality givesFor $j=k-2$, the expected count satisfies $\mu =n/j!>k-1\to \infty$. Part (ii) bounds its variance by $2\mu$, so Chebyshev's inequality givesCombining the tails provesThe blocks are consecutive in the cyclic order throughout; this is not the longest increasing subsequence with arbitrary omitted positions.

This establishes the longest increasing cyclic run of a random permutation concentration bound.

Let $I_i=1_{A_i}$ and $X={\sum }_i{I}_i$. DefineThe dependency sum is over ordered pairs, so each unordered overlapping pair is counted twice. Disjoint prescribed edge sets give independence.

Order the events. For each $i$, let $B_i$ be the event that all earlier events fail. Split it as $B_i=C_i\cap D_i$, where $C_i$ excludes earlier events with edge sets disjoint from $E_i$, and $D_i$ excludes the overlapping earlier events. These are down-sets. The event $A_i$ is a principal up-set, and it is independent of $C_i$ since their determining edge sets are disjoint.

If some $B_i$ has probability zero the desired zero-event bound is immediate. Otherwise the allowed conditional correlation inequality givesSince $\mathbb{P}(B_i)\le \mathbb{P}(C_i)$, it follows thatThe last step is the union bound under conditioning on $A_i$. Zero-probability events may simply be omitted, and a certain event makes the target probability zero. Finally the sequential product and $1-u\le e^{-u}$ giveThis proves the first Janson inequality with the dependency-sum convention explicit.

Independently retain each event with probability $t$, using a fresh Bernoulli mark for every index. Its retained occurrence is the original principal up-set together with its mark being one, so the first proof applies in the enlarged independent product space. The new parameters are ${\mu }_t=t\mu$ and ${\Delta }_t=t^2\Delta$: distinct retained events have independent marks, and pairs of disjoint original supports remain independent.

If no original event occurs, no retained event occurs. ThusWhen $\Delta \ge \mu >0$, choose $t=\mu /\Delta$ to minimize this quadratic exponent. It givesIf $\mu =0$, the appropriate trivial bound is one, rather than an undefined zero-over-zero exponent. The argument is the Janson lower-tail bound by independent thinning.

Count one copy for each four-element vertex set. It requires six independent edges, soDistinct copies share an edge exactly when their vertex intersection has size two or three. For each first copy, their numbers are $6\left(\genfrac{}{}{0ex}{}{n-4}{2}\right)$ and $4(n-4)$, respectively. The required union then has eleven or nine edges. Hence the ordered Janson dependency sum isFor large $n$, $\mu =\Theta (n^4)$ and $\Delta =\Theta (n^6)$, so $\Delta \ge \mu$ and ${\mu }^2/(2\Delta )\ge a{n}^2$ for some constant $a>0$. The second Janson inequality therefore givesThis is the asserted asymptotic bound. It can also be made valid for every $n\ge 4$ by decreasing $a$ to cover the finitely many smaller values, since each then has probability strictly below one of containing no copy. For $n<4$ the event has probability one and no positive exponential bound of this form can hold.

A dependency graph of events, written here as a loopless directed graph $D$ on the event indices, must satisfy a joint independence condition: for each $i$, $A_i$ is independent of the sigma-algebra generated by all $A_j$ with $j\ne i$ and no arc $i\to j$. In particular this means independence from every Boolean combination of those non-neighbour events, not merely pairwise independence. The outgoing neighbours list the events for which that independence is not required.

The asymmetric Lovász local lemma states that if there are numbers $0\le x_i<1$ withfor every index, thenFor maximum out-degree $d\ge 1$, take every $x_i=1/(d+1)$. Sinceone has $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge p$. Fewer than $d$ outgoing neighbours only increases the product, so the hypothesis is satisfied whenever $ep(d+1)\le 1$.

If $d=0$, take $x_i=p<1$; the neighbour products are empty and equal one. This separately covers the case in which $1/(d+1)$ would equal the forbidden value one. Thus the symmetric local lemma follows in every case.

For distinct indices put arcs in both directions whenever $S_i\cap S_j\ne \varnothing$. If $j$ is not an outgoing neighbour of $i$, every variable determining $A_j$ lies outside $S_i$. The entire family of such events is measurable with respect to variables outside $S_i$, whose sigma-algebra is independent of the variables inside $S_i$. Thus $A_i$ is independent of their whole generated sigma-algebra, establishing the required dependency graph of events. This justifies joint independence rather than just checking each pair.

Color every edge independently and uniformly with one of $k$ colors. For each unoriented simple four-edge path $P$, let $A_P$ be its repetition event. Its four distinct edges must satisfy two prescribed color equalities, so $\mathbb{P}(A_P)=k^{-2}$.

Events with edge-disjoint paths depend on disjoint random variables. A fixed edge lies on at most $4{\Delta }^3$ unoriented four-edge paths: count its four possible positions and two orientations, bound the remaining choices by ${\Delta }^3$, then divide the oriented path count by two. Thus the union of all paths sharing any of $P$'s four edges has size at most $16{\Delta }^3$. This union includes $P$ itself, so a dependency graph has $d+1\le 16{\Delta }^3$.

For $k\ge 8{\Delta }^{3/2}$,The symmetric Lovász local lemma yields positive probability of avoiding every event. Therefore such an edge coloring exists. If there are no four-edge paths the conclusion is immediate.

Use the same independent coloring, now with events indexed by unoriented six-edge paths. A repetition fixes the second three-edge color block to equal the first, so each event has probability $k^{-3}$. A fixed edge belongs to at most $6{\Delta }^5$ such paths, and a six-edge path has at most $36{\Delta }^5$ events in its closed dependency neighbourhood. Thus $d+1\le 36{\Delta }^5$.

For $k\ge 5{\Delta }^{5/3}$,The symmetric Lovász local lemma again guarantees a coloring avoiding all six-edge repetition events. Thus the required coloring exists, with the empty event family handled trivially.

Use both families of bad events in one asymmetric Lovász local lemma application. Give every four-edge event parameter $x_4$ and every six-edge event parameter $x_6$. A path of length $\ell$ shares edges with at most $4\ell {\Delta }^3$ four-edge paths and $6\ell {\Delta }^5$ six-edge paths. It therefore suffices to verifyThese slightly excessive exponents are safe even though they may count the event itself. Choose $x_4=2/k^2$ and $x_6=2/k^3$. For $k\ge C{\Delta }^{5/3}$, the sums of exponents times their parameters are bounded by constants times $C^{-2}{\Delta }^{-1/3}+C^{-3}$, uniformly in $\Delta \ge 1$. Taking $C$ sufficiently large makes each product of factors at least $1/2$, for example using $(1-x{)}^r\ge 1-rx$ and multiplying the two factors. Both displayed inequalities then hold. Positive probability of no bad event gives simultaneous avoidance of both lengths. Keeping two event parameters avoids replacing the rarer six-edge events by the larger four-edge probability.

These are the avoiding short repetitions in an edge coloring bounds, for repetitively colored paths.