Counting partitions of $ {G}_{n,1/2} $ with degree congruence conditions
For $G=G_{n, 1/2}$, the Erd\H{o}s--Renyi random graph, let $X_n$ be the random variable representing the number of distinct partitions of $V(G)$ into sets $A_1, \ldots, 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\geq 3$ is odd then $X...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Wiley
2022
|
| _version_ | 1797109823394807808 |
|---|---|
| author | Balister, P Powierski, E Scott, A Tan, J |
| author_facet | Balister, P Powierski, E Scott, A Tan, J |
| author_sort | Balister, P |
| collection | OXFORD |
| description | For $G=G_{n, 1/2}$, the Erd\H{o}s--Renyi random graph, let $X_n$ be the
random variable representing the number of distinct partitions of $V(G)$ into
sets $A_1, \ldots, 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\geq 3$ is odd then
$X_n\xrightarrow{d}{\mathrm{Po}(1/q!)}$, and if $q \geq 4$ is even then
$X_n\xrightarrow{d}{\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. |
| first_indexed | 2024-03-07T07:46:42Z |
| format | Journal article |
| id | oxford-uuid:41b10462-113d-4b48-8723-6d3ebfcc3b21 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:46:42Z |
| publishDate | 2022 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:41b10462-113d-4b48-8723-6d3ebfcc3b212023-06-15T09:34:45ZCounting partitions of $ {G}_{n,1/2} $ with degree congruence conditionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:41b10462-113d-4b48-8723-6d3ebfcc3b21EnglishSymplectic ElementsWiley2022Balister, PPowierski, EScott, ATan, JFor $G=G_{n, 1/2}$, the Erd\H{o}s--Renyi random graph, let $X_n$ be the random variable representing the number of distinct partitions of $V(G)$ into sets $A_1, \ldots, 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\geq 3$ is odd then $X_n\xrightarrow{d}{\mathrm{Po}(1/q!)}$, and if $q \geq 4$ is even then $X_n\xrightarrow{d}{\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. |
| spellingShingle | Balister, P Powierski, E Scott, A Tan, J Counting partitions of $ {G}_{n,1/2} $ with degree congruence conditions |
| title | Counting partitions of $ {G}_{n,1/2} $ with degree congruence conditions |
| title_full | Counting partitions of $ {G}_{n,1/2} $ with degree congruence conditions |
| title_fullStr | Counting partitions of $ {G}_{n,1/2} $ with degree congruence conditions |
| title_full_unstemmed | Counting partitions of $ {G}_{n,1/2} $ with degree congruence conditions |
| title_short | Counting partitions of $ {G}_{n,1/2} $ with degree congruence conditions |
| title_sort | counting partitions of g n 1 2 with degree congruence conditions |
| work_keys_str_mv | AT balisterp countingpartitionsofgn12withdegreecongruenceconditions AT powierskie countingpartitionsofgn12withdegreecongruenceconditions AT scotta countingpartitionsofgn12withdegreecongruenceconditions AT tanj countingpartitionsofgn12withdegreecongruenceconditions |