Counting partitions of Gn, 1/2$$ {G}_{n, 1/2} $$ with degree congruence conditions. Issue 3 (2nd October 2022)

• Record Type: Journal Article
• Authors: Balister, Paul; Powierski, Emil; Scott, Alex; Tan, Jane
• Is Part Of: Random structures & algorithms. Volume 62:Issue 3(2023)
• Page Start: 564
• Page End: 584
• Publication Date: 2022-10-02
• Subjects: induced subgraph -- random graphs -- vertex partition; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21115
• Languages: English
• ISSNs: 1042-9832

Abstract

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, \dots, {A}_q $$ so that the degree of each vertex in G [ A i ] $$ G\left[{A}_i\right] $$ is divisible by q $$ q $$ for all i ∈ [ q ] $$ i\in \left[q\right] $$ . We prove that if q ≥ 3 $$ q\ge 3 $$ is odd then X n → d Po ( 1 / q ! ) $$ {X}_n\overset{d}{\to \limits}\mathrm{Po}\left(1/q!\right) $$, and if q ≥ 4 $$ q\ge 4 $$ is even then X n → d Po ( 2 q / q ! ) $$ {X}_n\overset{d}{\to \limits}\mathrm{Po}\left({2}^q/q!\right) $$ . More generally, we show that the distribution is still asymptotically Poisson when we require all degrees in G [ A i ] $$ G\left[{A}_i\right] $$ to be congruent to x i $$ {x}_i $$ modulo q $$ q $$ for each i ∈ [ q ] $$ i\in \left[q\right] $$, 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.