6
$\begingroup$

Let $G=(V, E)$ be a graph with chromatic number $\chi(G)=1000 .$ Let $U \subset V$ be a random subset of $V$ chosen uniformly from among all $2^{|V|}$ subsets of $V$. Let $H=G[U]$ be the induced subgraph of $G$ on $U$. Prove that $$ \operatorname{Pr}[\chi(H) \leq 400]<1 / 100 $$

This is an exercise on The Probabilistic Method, authors are Noga Alon, Joel H. Spencer.

$\endgroup$

1 Answer 1

4
$\begingroup$

My copy of the book being in my locked-down office makes it easy to avoid checking which section this question is from for a hint of the expected method, so here's a sledge hammer.

Fix a partition $V = V_1 \cup V_2 \cup \cdots \cup V_{1000}$ into independent sets and let $U_i = U \cap V_i$. A uniformly random subset of $V$ includes each element of $V$ independently with probability $1/2$, so the $U_i$ are independent.

Apply the Hoeffding-Azuma inequality with the martingale that reveals each $U_i$ one at a time. We always have the option to give the vertices of $U_i$ in $H$ their own colour, so each $U_i$ can affect $\chi(H)$ by at most $1$. It follows that $\chi(H)$ is exponentially concentrated in some interval of length on the order of $\sqrt{1000}$, but we don't know where.

Now note that (i) $\chi(G[V\setminus U])$ has the same distribution as $\chi(H)$ and (ii) $\chi(H) + \chi(G[V\setminus U]) \geq 1000$ (else we can combine their colourings to obtain a cheaper colouring of $G$). So if $\Pr(\chi(H) \leq 400) > 1/100$, then we also have $\Pr(\chi(H) \geq 600) > 1/100$, but this isn't consistent with exponential concentration in a short interval.

I haven't checked that the numbers work out in this case, but this method should at least solve some problems of this basic shape.

$\endgroup$
1
  • $\begingroup$ Right. Your argument shows the expected chromatic number is at least 500, and Azuma then gives us Prob(\chi \leq 400) \leq Prob(\chi - \mu \leq -100) \leq exp(-(100)^2/(2*1000)) = exp(-5) = 0.00673... < 1/100. $\endgroup$
    – Pat Devlin
    Commented Jun 26, 2020 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.