Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 11 (Probabilistic Combinatorics)

Use the random alteration method. Take arbitrarily large $n$ divisible by $2k$, and sample a binomial random graph with edge probability $p=n^{-1+1/(2g)}$. Let $Z$ count cycles of lengths $3,\dots ,g-1$. For each length $\ell$, its expected count is at most $(np{)}^{\ell }/(2\ell )$, soThe sum is empty if $g=3$. By the Markov inequality, $Z\le n/2$ with probability tending to one.

Set $s=n/(2k)$. The expected number of independent $s$-vertex sets isbecause the negative exponent has order $n^{1+1/(2g)}$, dominating the term of order $n$. Thus with probability tending to one there is no independent set of size $s$.

Choose a realization having both properties. Delete one vertex from each of its short cycles, using at most $Z$ deletions. The induced remaining graph $H$ has at least $n/2$ vertices and girth at least $g$. Deletion cannot create a new independent set, so $\alpha (H)\le s-1$. Every colour class is independent, givingIn particular a graph of the required girth and chromatic number exists. This proves graphs of arbitrarily high girth and chromatic number rather than invoking that existence theorem.

Put $q=1-p=1/b$ and $L={\log }_{b}n$. For $s=\lceil 2L\rceil$, the expected number of independent $s$-sets isTaking logarithms gives $\log \mathbb{E}{X}_s\le -c_p\log n\log \log n$ for all sufficiently large $n$: the two quadratic-order terms cancel to within $O_p(\log n)$, leaving the negative term $-s\log s$. By the first moment method, with probability tending to one $\alpha (G)\le s-1<2L$. Hence

For the upper bound, an explicit greedy exposure rule suffices; the sharper factor two is not needed here. SetWhile at least $m_0$ vertices remain, construct a colour class by choosing a candidate, retaining its non-neighbours as candidates, and repeating for $r$ choices. Expose only edges incident to chosen vertices. They will all be removed with this colour class. By deferred edge exposure in greedy independent-set colouring, the remaining internal edges are still independent Bernoulli edges conditional on the history. This assertion depends on this particular rule; it is not true for an arbitrary adaptively selected remainder.

If $M_j$ candidates remain after $j$ choices, then conditionallyThe Chernoff bound gives, for $M_j\ge 1/\eta$,On the event that these lower bounds hold, a class started from $m\ge m_0$ hasIndeed $q^r\ge n^{-1}(\log n{)}^8$, while $(1-2/\log n{)}^r$ is bounded below by a positive constant depending on $p$. Thus each conditional failure probability is at most $\exp [-c_p(\log n{)}^4]$. A union bound over at most $nr$ candidate steps shows that all these classes can be formed with probability tending to one. Colour the final fewer than $m_0$ vertices individually. The number of colours is at mostTogether this provesThe failure estimates are summable in $n$. Thus they give both the usual asymptotically-almost-sure assertion and, on any common probability space carrying the sequence, eventual almost-sure validity by the first Borel-Cantelli lemma.

On an independent Bernoulli product measure, the Harris-Kleitman inequality states that increasing events $E,F$ obeyThe same holds for two decreasing events; an increasing and a decreasing event have the reversed inequality.

Prove the stronger function version by induction on the number of coordinates. For increasing bounded functions $f,g$, condition on the last coordinate $Z$, with $\mathrm{Pr}(Z=1)=p$. The law of total covariance givesThe first term is nonnegative by induction, and the other factors are nonnegative by monotonicity. The one-coordinate case is the same formula without the first term. Event indicators prove the assertion. Two decreasing functions follow by replacing both by their negatives; replacing only one gives negative correlation of increasing and decreasing events.

Here is a precise Janson inequality and its lower-tail concentration form. Let $I_i$ indicate containment of a specified set of independent Bernoulli coordinates, set $X={\sum }_i{I}_i$, $\mu =\mathbb{E}X$, and letThis Janson dependency sum is ordered and excludes the diagonal. ThenA zero denominator means the trivial case $X=0$ almost surely.

To prove the avoidance bound, expose the avoidance events in order. For a fixed $i$, separate earlier indices into those whose supports are disjoint from $S_i$ and those overlapping it. Write $C$ for avoidance of the first group and $D$ for avoidance of the second. The event $C$ is independent of $I_i$, while $C$ is decreasing and $\{I_i=I_j=1\}$ is increasing. The correlation inequality therefore givesThe first inequality divides a nonnegative numerator by $\mathrm{Pr}(D\mid C)\le 1$; the second uses a union bound and negative correlation with $C$. Conditioning events of zero probability already make full avoidance impossible. Multiply the resulting conditional avoidance bounds to obtain the Janson sequential product lemma. Taking logarithms and using $\log (1-u)\le -u$ gives $-\mu +\Delta /2$, since each unordered dependency pair is counted once in the sequential sum.

For the Janson lower-tail bound by independent thinning, attach independent selectors of probability $t$ to the events. Their total expectation and dependency sum are $t\mu ,t^2\Delta$, so avoidance of the selected events givesSet $t=1-e^{-s}$ and apply the exponential Markov bound to $e^{-sX}$. Using $s-s^2/2\le 1-e^{-s}\le s$ yieldsChoosing $s=a/(\mu +\Delta )$ proves the concentration assertion. For avoidance alone, optimizing $-t\mu +t^2\Delta /2$ also gives $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$, and the original bound gives $e^{-\mu /2}$ when $\Delta \le \mu$.

To outline the sharp chromatic application, view an independent set of $G(n,p)$ as a clique of its complement, whose edge probability is $q=1-p$. Fix $0<\epsilon <1$, let $m=\lceil n/(\log n{)}^2\rceil$ and $r=\lfloor (2-\epsilon ){\log }_{b}n\rfloor$. For a particular $m$-vertex set, let $X$ count independent $r$-sets. Then $\mu =\left(\genfrac{}{}{0ex}{}{m}{r}\right)q^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$, and the overlap calculation givesOverlap of only one vertex shares no edge, hence is independent. For completeness, the summand is at most $(r^2/(m-r){)}^{\ell }{b}^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}/\ell !$. Since $r\le (2-\epsilon /2){\log }_{b}m$ eventually, large overlaps are bounded by $m^{-c_{\epsilon }\ell }$; finitely many smaller overlaps are dominated by $\ell =2$. Also $\log \mu ={\Omega }_{p,\epsilon }((\log m{)}^2)$, so the diagonal contribution $1/\mu$ is negligible. The concentration bound consequently givesA union bound over at most $2^n$ vertex sets still tends to zero. Thus independent sets in every large subset of a dense random graph are available uniformly, including adaptively obtained remainders. Repeatedly remove an independent $r$-set and give it a new colour, then colour the fewer than $m$ leftover vertices individually. This uses at most $n/r+m$ colours. Combining with the first-moment lower bound and letting fixed $\epsilon$ be arbitrarily small gives the accurate leading asymptoticThe uniform subset estimate, rather than merely the existence of one large independent set, is what makes the sharp upper bound possible.

The parameter relations give $\mu =\log (n/c)$ andFor each fixed integer $r\ge 1$, take an $r$-vertex set $S$ and let $X_S$ count triangles meeting $S$. The event that every vertex of $S$ is counted by $T$ is exactly $X_S=0$.

The number of such triangles isThus their total expected count is ${\mu }_S=N_S{p}^3=r\mu +O_r(n{p}^3)=r\mu +o(1)$.

Distinct triangles have dependent containment events only when they share an edge. If that common edge meets $S$, there are $O_r(n)$ choices for it and $O(n^2)$ choices for the two other vertices. If the common edge avoids $S$, both other vertices must lie in $S$, giving only $O_r(n^2)$ pairs. Each pair needs five edges. Consequently its ordered Janson dependency sum isJanson inequality gives the upper bound $\mathrm{Pr}(X_S=0)\le \exp (-{\mu }_S+{\Delta }_S/2)$. For the lower bound, the avoidance of each triangle is a decreasing event. Repeated application of Harris' inequality givesThe error $n^2{p}^6=O((\log n{)}^2/n^2)$ also tends to zero. The bounds match multiplicatively:Summing over ordered distinct vertices yields the factorial moments

Here is an explicit justification that these moments determine the limit. For every integer $t\ge 0$, the finite alternating sumsare upper bounds for $\mathrm{Pr}(T=t)$ when $L$ is even and lower bounds when $L$ is odd. This follows by applying the Bonferroni inequalities to $\left(\genfrac{}{}{0ex}{}{T}{t}\right){\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{T-t}{j})$; the full sum is precisely the indicator of $T=t$. First let $n\to \infty$ for a fixed truncation and use the factorial-moment limits. Then let the even and odd truncations grow. Both bounds tend toHence every point probability has the Poisson distribution limit, proving the Poisson threshold for vertices lying in no triangle:This is also the factorial-moment criterion for Poisson convergence, here justified rather than left as an unproved implication.

Use the independent product measure on the finite coordinate spaces. For $A\ne \varnothing$, let $V_A(x)$ be the convex hull of its mismatch vectors $(1_{x_i\ne y_i}{)}_{i=1}^n$, $y\in A$. The distance in the question equalsTo verify this, let $v_{\ast }$ be the nearest point. Any unit vector $\alpha$ satisfies ${\min }_{v\in V_A}\alpha \cdot v\le \alpha \cdot v_{\ast }\le \Vert v_{\ast }{\Vert }_2$. Conversely the projection property $v_{\ast }\cdot (v-v_{\ast })\ge 0$ gives equality for $\alpha =v_{\ast }/\Vert v_{\ast }{\Vert }_2$ when $v_{\ast }\ne 0$. If $v_{\ast }=0$, nonnegative weights give supremum zero. Linear functionals have the same minimum on the hull as on its original vectors, so this is exactly the quantified definition of the Talagrand convex distance.

We prove the stronger section induction for the Talagrand exponential moment,Zero-probability atoms may be discarded, replacing $A$ by its supported part: this preserves its probability and can only increase its distance. Thus assume all coordinate atoms have positive mass. The induction starts with zero coordinates, when a positive-probability event is the singleton space and its distance is zero.

Split the last coordinate into values $j$, with probabilities $q_j$, and write $A_j$ for the corresponding section in the first $n-1$ coordinates. Put $a_j=\mathrm{Pr}(A_j)$, choose a largest section $A_s$ of probability $a>0$, and set $r_j=a_j/a\in [0,1]$. For a point $(x^{\prime },j)$, mix nearest mismatch vectors from $A_j$ and $A_s$ with weights $\lambda ,1-\lambda$. Their final coordinates are zero and, if $j\ne s$, one. Convexity of the squared norm givesFor an empty $A_j$, use $\lambda =0$ directly. If $j=s$, the final-coordinate term is an unnecessary nonnegative allowance, so the bound still holds.

Exponentiate, integrate in $x^{\prime }$, and use Hölder's inequality and the induction hypothesis. For $r_j>0$ this givesWe supply the scalar estimate for Talagrand product induction used in the last step. Set $L=-\log r$. For $0\le L\le 1/2$, choose $1-\lambda =2L$, making the expression $e^{L-L^2}$. The functionhas $h(0)=h^{\prime }(0)=0$ andThus $e^{L-L^2}\le 2-e^{-L}$. For $L\ge 1/2$, choose $\lambda =0$, giving $e^{1/4}$; the already proved boundary case and monotonicity of $2-e^{-L}$ give the same bound. For $r=0$, the direct empty-section bound is $e^{1/4}/a\le 2/a$.

Now average over $j$. With $m={\sum }_j{q}_j{r}_j=\mathrm{Pr}(A)/a\in (0,1]$, the exponential integral is at most $(2-m)/a$. Since $m(2-m)\le 1$, this is at most $1/(am)=1/\mathrm{Pr}(A)$, closing the induction.

Finally apply the Markov inequality to the nonnegative exponential. For the distance-tail event ${\overline{A}}_t$,This proves Talagrand's convex distance inequality for the finite product. If $\mathrm{Pr}(A)=0$, the required probability-product inequality is immediate, including the empty-event case with distance defined as infinity; no finite exponential-moment assertion is needed there.

Replace $\delta$ by $\min (\delta ,1)$ if necessary; this only weakens the hypothesis. We prove the result for finite graphs using a random proper partial graph coloring, then a deterministic completion. All constants below may depend on this fixed positive $\delta$.

First record the extension of a partial colouring by neighbour-colour savings. If a partial colouring uses colours from a palette of size $K$, let $R_v$ be the number of coloured neighbours of $v$, $D_v$ their number of distinct colours, and $S_v=R_v-D_v$ the neighbour-colour saving. There are $K-D_v$ available colours and $d(v)-R_v$ uncoloured neighbours. Thusat every vertex suffices for greedy completion: each subsequently coloured neighbour removes at most one available colour while reducing the uncoloured-neighbour count by one.

Call $v$ high-degree if $d(v)\ge (1-\delta /8)\Delta$. Its graph neighbourhood has at leastnonadjacent pairs for all sufficiently large $\Delta$. Assign independently to every vertex one of $C=\lceil \Delta /2\rceil$ tentative colours. Erase the colour of every vertex having a neighbour with the same tentative colour. The remaining colouring is proper; erasure is based on the original assignments and is not an iterative cascade.

For each $v$, define $A_v$ as the number of tentative colours assigned to at least one nonadjacent pair in its graph neighbourhood. Let $B_v$ count those same colours for which at least one neighbour of $v$ loses its colour. Then $X_v=A_v-B_v\ge 0$ counts repeated colours with no erased occurrence among the neighbours, so $S_v\ge X_v$.

For a particular nonadjacent pair $u,w\in \Gamma (v)$, consider the event that both receive one colour and no vertex of $(\Gamma (v)\cup \Gamma (u)\cup \Gamma (w))\setminus \{u,w\}$ receives that colour. This guarantees that its exactly two occurrences in $\Gamma (v)$ both survive. Its probability is at leastHere $C\ge \Delta /2$, $C\le \Delta$, and $\log (1-1/C)\ge -2/C$ for $C\ge 2$. Different pairs cannot be counted by the same colour in this event, since each event specifies exactly two occurrences in the graph neighbourhood. Thereforefor every high-degree vertex. This is the expected colour savings from sparse neighbourhoods.

We need simultaneous concentration, not just a positive expectation. A single tentative-colour change can affect $A_v$ or $B_v$ only in the old and new colour categories, so each function changes by at most two. A witness for $A_v\ge s$ fixes two vertices for each of $s$ colours. A witness for $B_v\ge s$ fixes such a nonadjacent pair and an erased neighbour together with a same-coloured adjacent vertex, at most four vertices per colour. Thus both are certifiable functions with Lipschitz constant $2$ and certificate parameter at most $4$. Both are bounded by $C\le \Delta$.

To see exactly what concentration follows, let an integer-valued $Z$ change by at most $L$ per coordinate and have certificates of size at most $rb$. For an input with $Z\ge b$, fix such a certificate $J$. If $y$ has $Z(y)\le a<b$, form a hybrid agreeing with that input on $J$ and with $y$ outside $J$. The hybrid has value at least $b$, so at least $(b-a)/L$ certificate positions differ from $y$. Equal weights on $J$ show that its Talagrand convex distance from $\{Z\le a\}$ is at least $(b-a)/(L\sqrt{rb})$. Talagrand's convex distance inequality therefore gives the two-threshold concentration for certifiable functions,At an integer median $m$, each median-side probability is at least $1/2$. Taking thresholds $m-t,m$ or $m,m+t$ and using $0\le Z\le \Delta$ givesfor $L=2,r=4$. Summing these tails gives $|\mathbb{E}Z-m|=O(\sqrt{\Delta })$. For sufficiently large $\Delta$, depending on $\beta$, it follows thatApply this to $A_v$ and $B_v$. Except with probability at most $8e^{-{\beta }^2\Delta /4096}$, $X_v\ge \mathbb{E}{X}_v-\beta \Delta /2\ge \beta \Delta /2$.

A bad event at $v$ depends only on tentative colours at distance at most two. It is independent of the entire collection of bad events at distance greater than four. Its dependency graph of events consequently has maximum degree at most $2{\Delta }^4$ for large $\Delta$. The Lovász local lemma now makes all high-degree vertices good simultaneously: exponential decay beats this polynomial dependency bound.

The needed local-lemma step can be checked directly. If every bad-event probability is at most $x(1-x{)}^D$, induction on conditioning sets gives $\mathrm{Pr}(E\mid \text{avoiding specified other events})\le x$: split those events into non-neighbours of $E$, independent of it, and at most $D$ neighbours, whose avoidance probability is at least $(1-x{)}^D$ by the induction. Multiplying the resulting conditional avoidance probabilities makes total avoidance positive. Taking $x=1/(D+1)$ works whenever $ep(D+1)\le 1$, since $(1-1/(D+1){)}^D\ge e^{-1}$. Our bound satisfies this criterion once $\Delta \ge {\Delta }_0(\delta )$.

Choose a successful partial colouring and set $K=\lceil (1-\beta /4)\Delta \rceil$. This contains the original palette. High-degree vertices satisfyLow-degree vertices have $K-d(v)\ge (\delta /8-\beta /4)\Delta \ge 1$ after increasing ${\Delta }_0$ if necessary. Greedy completion therefore gives $\chi (H)\le K$. Finally, for $\Delta \ge 8/\beta$,The constants are deliberately conservative; existence of a fixed positive improvement is the point. The same proof uses an external maximum degree bound, so if infinite locally finite graphs are allowed, every finite subgraph has this uniform colouring bound and compactness extends the colouring to the whole graph.

For the stronger triangle-free result, the appropriate brief route is semi-random palette refinement for triangle-free colouring. Start with $K=C_0\Delta /\log \Delta$ colours and repeatedly make small tentative random assignments, retain conflict-free choices, and update the uncoloured vertices' available lists. Triangle-freeness makes each graph neighbourhood independent. Track list size and average residual neighbour congestion per colour, prune unusually congested colours, and use concentration inequalities and the Lovász local lemma to preserve these invariants through the rounds. The ratio of residual congestion to list size decreases until a final completion using the Lovász local lemma or greedy coloring succeeds. Average control and pruning are important: four-cycles are allowed, so assuming tight uniform concentration for every individual colour load would be unjustified. With a sufficiently large absolute $C_0$, this programme gives $\chi (H)=O(\Delta /\log \Delta )$. The one-round fixed-fraction saving proved above alone does not establish that logarithmic improvement.

To show the order is best possible, let $d\to \infty$ through integers and sample $G(n,d/n)$ with $n=d^7$. A Chernoff bound and union bound give maximum degree at most $2d$ with probability tending to one. The expected triangle count is at most $d^3/6=o(n)$, so fewer than $n/2$ vertices need be deleted to remove all triangles with high probability. For $s=\lceil 4n\log d/d\rceil$, the expected number of independent $s$-sets is at mostits logarithm is at most $s[\log (ed/(4\log d))-2\log d+o(1)]$, which tends to minus infinity. The altered triangle-free graph thus has at least $n/2$ vertices and independence number below $s$, giving $\chi \ge (c+o(1))d/\log d$ for an absolute positive $c$. Append a disjoint star graph whose centre has vertex degree $2d$ if needed to make its maximum degree exactly $\Delta =2d$. This proves the triangle-free chromatic lower bound at bounded maximum degree, $\chi =\Omega (\Delta /\log \Delta )$, so the preceding order cannot be improved in general.