On subgraphs with degrees of prescribed residues in the random graph
On subgraphs with degrees of prescribed residues in the random graph
复制标题
在随机图中具有指定残基度的子图
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Michael Krivelevich
中科院分区：
文献类型：
--
作者：
Asaf Ferber;Liam Hardiman;Michael Krivelevich
证明了随机图Gn，1/2$${G}{n，1/2}$$有一个线性大小的导出子图，其所有度都与r(Modq)$$rkern0.3em Left(算子名{mod}kern0.3em q)同余
Ight)$$对于任何固定的r$$r$$和q≥2$$qge 2$$。更广泛地说，对于模Q$$Q$$的任何固定分布的学位也是如此。最后，我们证明了高概率地将Gn的1/2$${G}_{n，1/2}$$划分成大小几乎相等的q+1$$q+1$$部分，每个部分的所有度都与r(Modq)$$rkern0.3em Left(算子名{mod}kern0.3em q
夜)$$。我们的结果肯定地解决了Scott的一个猜想，他解决了情形Q=2$$Q=2$$。
We show that with high probability the random graph Gn,1/2$$ {G}_{n,1/2} $$ has an induced subgraph of linear size, all of whose degrees are congruent to r(modq)$$ rkern0.3em left(operatorname{mod}kern0.3em q
ight) $$ for any fixed r$$ r $$ and q≥2$$ qge 2 $$ . More generally, the same is true for any fixed distribution of degrees modulo q$$ q $$ . Finally, we show that with high probability we can partition the vertices of Gn,1/2$$ {G}_{n,1/2} $$ into q+1$$ q+1 $$ parts of nearly equal size, each of which induces a subgraph all of whose degrees are congruent to r(modq)$$ rkern0.3em left(operatorname{mod}kern0.3em q
ight) $$ . Our results resolve affirmatively a conjecture of Scott, who addressed the case q=2$$ q=2 $$ .
计算具有度数同余条件的 Gn,1/2$$ {G}_{n,1/2} $$ 的划分
影响因子：
1
作者：
Balister P
通讯作者：
Balister P