Graph Decomposition and Parity

Motivated by a recent extension of the zero‐one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph . We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo q. We determine the asymptotic distribution of all fixed two‐component graphs in for all q, and we give infinite families of many‐component graphs with a uniform asymptotic distribution for all q. We also prove a negative result that no recursive proof of the simplest form exists for a uniform asymptotic distribution for arbitrary graphs.