Counting partitions of Gn, 1/2 G_n, 1/2 with degree congruence conditions. Issue 3 (2nd October 2022) - Balister, Paul; Powierski, Emil; Scott, Alex; Tan, Jane
Abstract: For G = G n, 1 / 2 G=G_n, 1/2 , the Erdős–Renyi random graph, let X n X_n be the random variable representing the number of distinct partitions of V ( G ) V(G) into sets A 1, …, A q A_1, …, A_q so that the degree of each vertex in G [ A i ] G[A_i] is divisible by q q for all i ∈ [ q ] i[q] . We prove that if q ≥ 3 q3 is odd then X n → d Po ( 1 / q ! ) X_nd→ Po(1/q!) , and if q ≥ 4 q4 is even then X n → d Po ( 2 q / q ! ) X_nd→ Po(2^q/q!) . More generally, we show that the distribution is still asymptotically Poisson when we require all degrees in G [ A i ] G[A_i] to be congruent to x i x_i modulo q q for each i ∈ [ q ] i[q] , where the residues x i x_i may be chosen freely. For q = 2 q=2 , the distribution is not asymptotically Poisson, but it can be determined explicitly.