Avoidance couplings on non‐complete graphs
Avoidance couplings on non‐complete graphs
复制标题
非完全图上的回避耦合
DOI：
10.1002/rsa.20999
复制
发表时间：
2021
影响因子：
1
通讯作者：
Podder, Moumanti
中科院分区：
文献类型：
--
作者：
Bates, Erik;Podder, Moumanti
同一有限图上的随机游走者的耦合，按顺序轮流进行，如果游走者从不发生碰撞，则称为回避耦合。以前对这些过程的研究几乎完全集中在完整的图上，特别是回避耦合可以包含多少个步行者。对于其他图，除了特殊情况外，两个不碰撞的简单随机游走器是否可以耦合还没有定论。在本文中，我们在 (i) 任何 d 正则图上构造这样的耦合，避免依赖于 d 的固定子图； (ii) 任何最小次数至少为三的无平方图。第一个结果的推论是，顶点上的均匀随机正则图承认高概率的避免耦合。
A coupling of random walkers on the same finite graph, who take turns sequentially, is said to be anavoidance couplingif the walkers never collide. Previous studies of these processes have focused almost exclusively on complete graphs, in particular how many walkers an avoidance coupling can include. For other graphs, apart from special cases, it has been unsettled whether even two noncolliding simple random walkers can be coupled. In this article, we construct such a coupling on (i) anyd‐regular graph avoiding a fixed subgraph depending ond; and (ii) any square‐free graph with minimum degree at least three. A corollary of the first result is that a uniformly random regular graph onnvertices admits an avoidance coupling with high probability.
登录
查看更多内容
KN 上回避耦合的单调性
DOI：
10.1017/s0963548316000195
发表时间：
2014
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
O. Feldheim
通讯作者：
O. Feldheim
非冲突随机游走的调度
DOI：
10.1007/978-981-15-0302-3_4
发表时间：
2014
期刊：
Springer Proceedings in Mathematics & Statistics
影响因子：
--
作者：
Riddhipratim Basu;V. Sidoravicius;A. Sly
通讯作者：
A. Sly
影响因子：
2
作者：
P. Balister;B. Bollobás;A. Stacey
通讯作者：
A. Stacey
ℤ2 和 17 的平方根的角渗滤
影响因子：
2.3
作者：
G. Pete
通讯作者：
G. Pete
均匀回避耦合、匿名系统设计与匹配理论
DOI：
10.1349/ddlp.2158
发表时间：
2016
期刊：
Springer Proceedings in Mathematics & Statistics
影响因子：
--
作者：
Ewa J. Infeld
通讯作者：
Ewa J. Infeld