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 G ( n , p ) . 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 G ( n , p ) 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.