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

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.