An interesting bound (problem from Rudi’s  Modern coding theory book) regarding the chromatic number of a random graph.  I first attempted it during the course.  Here is the problem statement:

C.5 (Concentration of the Chromatic Number – Spencer and Shamir). Consider a graph $G$ on $n$ vertices.  The chromatic number of a graph $G$, denoted by $\chi(G)$, is the smallest number of colors needed to color all vertices so that no two vertices which are joined by an edge have the same color. Consider the standard ensemble of random graphs on $n$ vertices with parameter $p$: to sample from this ensemble, pick $n$ vertices and connect each of the $\binom{n}{2}$ ordered pairs of vertices independently from all other connections with probability $p$. Show that for this ensemble

$\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}\left[\chi(G)\right] \rvert >\lambda \sqrt{n-1}\right) \le 2e^{\frac{-\lambda^2}{2}}$.

My solution is as folllows: (PDF typeset as single file is available here. Look for problem 3)

Let $G$ is a random graph with $n$ vertices.  If $p$ is the probability that a given edge is in $G$. The probability space be $G(n,p)$.  Let $\chi$ be a filter on the set of all such random graphs. We can define a Martingale as follows:

$X_{0}=\mathbb{E}[X(G)]$

$X_{i}=\mathbb{E}[X(G)\lvert 1_{1},1_{2},\ldots,1_{i}],\forall 1\le i\le \binom{n}{2}$

where

$1_{i}=\begin{cases}1,&\text{if edge} \quad e_{i}\in G\\ 0, &\text{if edge} \quad e_{i}\notin G\end{cases}$

and $\chi(G)$ is the Chromatic number of $G$. Chromatic number changes at most by one , when the information about the new edge comes in. Clearly, $\chi$ satisfies the conditions for Azuma’s inequality. $\{X_i\}_{i\ge 0}$

is a Martingale, with $\lvert X_i-X_0\rvert \le 1$).  Let $Z_i=X_i-E[X_i]$. Clearly

$E[Z_i]=E[X_i]-E[x_i]=0$

$Z_m=X_m-E[X_m]=\mathbb{E}[\chi(G)|1_1,1_2,\ldots,1_m]-\mathbb{E}[\chi(G)]$

$=\chi(G)-\mathbb{E}[\chi(G)]$

Now we can use the Azuma’s inequality on $\{Z_i\}$ to get,

$\mathbb{P}\left(\lvert Z_n-Z_0\rvert \ge \lambda \sqrt{n}\right)=\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}[\chi(G)] \rvert \ge \lambda \sqrt{n}\right)\le 2e^{\frac{-\lambda^2}{2}}$.

Since $\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}[\chi(G)] \rvert \ge \lambda \sqrt{n}\right)=\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}[\chi(G)] \rvert > \lambda \sqrt{n-1}\right)$, the result

$\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}\left[\chi(G)\right] \rvert >\lambda \sqrt{n-1}\right) \le 2e^{\frac{-\lambda^2}{2}}$

follows.