On subgraphs with degrees of prescribed residues in the random graph

Abstract

We show that with high probability the random graph $G_{n,1/2}$ has an induced subgraph of linear size, all of whose degrees are congruent to $r(\mathrm{mod}q)$ for any fixed $r$ and $q\ge 2$. More generally, the same is true for any fixed distribution of degrees modulo $q$. Finally, we show that with high probability we can partition the vertices of $G_{n,1/2}$ into $q+1$ parts of nearly equal size, each of which induces a subgraph all of whose degrees are congruent to $r(\mathrm{mod}q)$. Our results resolve affirmatively a conjecture of Scott, who addressed the case $q=2$.