Counting partitions of Gn,1/2$$ {G}_{n,1/2} $$ with degree congruence conditions
Counting partitions of Gn,1/2$$ {G}_{n,1/2} $$ with degree congruence conditions
复制标题
计算具有度数同余条件的 Gn,1/2$$ {G}_{n,1/2} $$ 的划分
DOI：
10.1002/rsa.21115
复制
发表时间：
2022
影响因子：
1
通讯作者：
Balister P
中科院分区：
文献类型：
--
作者：
Balister P
对于Erdős-Renyi随机图G=Gn,1/2 $$ G={G}_{n,1/2} $$，设Xn $$ {X}_n $$为表示V(G) $$ V(G) $$分成集合A1，…，Aq $$ {A}_1,\dots, {A}_q $$的不同分区数的随机变量，使得对于所有i∈[q] $$ i\in \left[q\right] $$, G[Ai] $$ G\left[{A}_i\right] $$中每个顶点的度数都可以被q $$ q $$整除。证明了如果q≥3 $$ q\ge 3 $$是奇数则Xn→dPo(1/q!) $$ {X}_n\overset{d}{\to \limits}\mathrm{Po}\left(1/q!\right) $$，如果q≥4 $$ q\ge 4 $$是偶数则Xn→dPo(2q/q!) $$ {X}_n\overset{d}{\to \limits}\mathrm{Po}\left({2}^q/q!\right) $$。更一般地，我们证明了当我们要求G[Ai] $$ G\left[{A}_i\right] $$中的所有度对每个i∈[q] $$ i\in \left[q\right] $$都等于xi $$ {x}_i $$模q $$ q $$时，分布仍然是渐近泊松的，其中残数xi $$ {x}_i $$可以自由选择。对于q=2 $$ q=2 $$，分布不是渐近泊松分布，但可以显式确定。
For G=Gn,1/2$$ G={G}_{n,1/2} $$, the Erdős–Renyi random graph, let Xn$$ {X}_n $$ be the random variable representing the number of distinct partitions of V(G)$$ V(G) $$ into sets A1,…,Aq$$ {A}_1,\dots, {A}_q $$ so that the degree of each vertex in G[Ai]$$ 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 Xn→dPo(1/q!)$$ {X}_n\overset{d}{\to \limits}\mathrm{Po}\left(1/q!\right) $$, and if q≥4$$ q\ge 4 $$ is even then Xn→dPo(2q/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[Ai]$$ G\left[{A}_i\right] $$ to be congruent to xi$$ {x}_i $$ modulo q$$ q $$ for each i∈[q]$$ i\in \left[q\right] $$, where the residues xi$$ {x}_i $$ may be chosen freely. For q=2$$ q=2 $$, the distribution is not asymptotically Poisson, but it can be determined explicitly.
每个图都包含一个线性大小的诱导子图，所有度数均为奇数
影响因子：
1.7
作者：
Asaf Ferber;Michael Krivelevich
通讯作者：
Michael Krivelevich
DOI：
--
发表时间：
1994
期刊：
影响因子：
--
作者：
Y. Caro;I. Krasikov;Y. Roditty
通讯作者：
Y. Roditty
DOI：
--
发表时间：
2021
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Asaf Ferber;Liam Hardiman;Michael Krivelevich
通讯作者：
Michael Krivelevich