1
$\begingroup$

Suppose that we have a random graph G(n,p) with $n$ vertices and each edge exists with probability $p = n^{-\alpha}, \alpha>\frac{5}{6}$. Prove that with high probability, say $1-\delta$, every subgraph with $o(\sqrt{n})$ vertices has a chromatic number equal to 3.

This is the first part of a problem that I'm stuck at it.

$\endgroup$
  • $\begingroup$ Is this a step in the proof of two-point concentration of the chromatic number $\chi(G(n,p))$? $\endgroup$ – Misha Lavrov Apr 16 at 20:32
  • $\begingroup$ @MishaLavrov It is the first step in the proof of a concentration for the chromatic number. What do you mean by two-point? $\endgroup$ – SMA.D Apr 16 at 20:39
  • $\begingroup$ By two-point I mean the result that for some range of $p$ (I do not remember which) the chromatic number has one of two values with high probability. $\endgroup$ – Misha Lavrov Apr 16 at 21:38
  • $\begingroup$ @MishaLavrov In my problem it was asked to prove $u\le\chi(G)\le u+3$ with high probability. $\endgroup$ – SMA.D Apr 17 at 4:40
  • $\begingroup$ That's also pretty good! The $u \le \chi(G) \le u+1$ result can be found in this paper by Luczak. $\endgroup$ – Misha Lavrov Apr 17 at 5:07
1
$\begingroup$

For any $k$, the expected number of sets of $k$ vertices with at least $\frac32k$ edges between them is no more than $$ \binom nk \binom{\binom k2}{\frac32 k} p^{\frac32k} \le \binom nk \binom{\frac12 k^2}{\frac32 k} p^{\frac32k}. $$ Using the inequality $\binom nk \le \left(\frac{ne}{k}\right)^k$, we can show that when $k \le \sqrt n$, this is bounded by $f(n)^k$ for some function $f(n)$ such that $f(n) \to 0$ as $n \to \infty$. (Try this!) In particular, if we sum over all $k \le \sqrt n$, the sum is bounded by $\frac{f(n)}{1-f(n)}$, which is still tending to $0$ as $n \to \infty$.

So with high probability, there are no sets of $k\le \sqrt n$ vertices with $\frac32k$ edges between them: in other words, the average degree of any subgraph on at most $\sqrt n$ vertices is less than $3$.

Then we can $3$-color any such subgraph by choosing a vertex $v$ of degree $2$, removing it, coloring the rest inductively, and putting $v$ back in with a color different from either of its neighbors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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