== Problem 4 (Concentration of measure) == Consider the [[wikipedia:Erds-Rnyi_model#Definition|Erds-Rnyi random graph]] $G(n,\; p)$ where every two vertices in the graph are connected randomly and independently with probability $p$. We denote $G\; \backslash sim\; G(n,\; p)$ if $G$ is generated in this way. Recall that $\backslash chi(G)$ is the chromatic number of the graph $G$. '''(a.)''' For , let $G\_1\; \backslash sim\; G(n,\; p\_1)$ and let $G\_2\; \backslash sim\; G(n,\; p\_2)$. Compare $\backslash mathbf\{E\}[\backslash chi(G\_1)]$ and $\backslash mathbf\{E\}[\backslash chi(G\_2)]$ and prove it. '''(b.)''' For $G\; \backslash sim\; G(n,\; n^\{-\backslash alpha\})$ with $\backslash alpha\; >\; 5/6$ and constant $C\; >\; 0$, prove that every subgraph of $G$ on $C\backslash sqrt\{n\; \backslash log\; n\}$ vertices is $3$-colorable with probability $1\; -\; o(1)$ when $n$ is large enough. ('''''Hint''''': $\backslash binom\{n\}\{k\}\; \backslash leq\; (en/k)^k$.) '''(c.)''' For $G\; \backslash sim\; G(n,\; n^\{-\backslash alpha\})$ with $\backslash alpha\; >\; 5/6$, show that $\backslash chi(G)$ is concentrated on four values with probability $1\; -\; o(1)$ when $n$ is large enough. To be more exact, show that there exists an integer $u$ such that $u\; \backslash leq\; \backslash chi(G)\; \backslash leq\; u+3$ with probability $1\; -\; o(1)$ when $n$ is large enough.