Counting partitions of $G_{n,1/2}$ with degree congruence conditions

Abstract

For $G=G_{n,1/2}$, the Erdős--Renyi random graph, let $X_n$ be the random variable representing the number of distinct partitions of $V(G)$ into sets $A_1,\dots ,A_q$ so that the degree of each vertex in $G[A_i]$ is divisible by $q$ for all $i\in [q]$. We prove that if $q\ge 3$ is odd then $X_n\stackrel{d}{\to }\mathrm{Po}(1/q!)$, and if $q\ge 4$ is even then $X_n\stackrel{d}{\to }\mathrm{Po}(2^q/q!)$. More generally, we show that the distribution is still asymptotically Poisson when we require all degrees in $G[A_i]$ to be congruent to $x_i$ modulo $q$ for each $i\in [q]$, where the residues $x_i$ may be chosen freely. For $q=2$, the distribution is not asymptotically Poisson, but it can be determined explicitly.

arXiv comment24 pages; v2: minor corrections including the proof of Theorem 19