Probabilistic zero forcing is a coloring game played on a graph where the goal is to color every vertex blue starting with an initial blue vertex set. As long as the graph is connected, if at least one vertex is blue then eventually all of the vertices will be colored blue. The most studied parameter in probabilistic zero forcing is the expected propagation time starting from a given vertex of $G.$ In this paper we improve on upper bounds for the expected propagation time by Geneson and Hogben and Chan et al. in terms of a graph's order and radius. In particular, for a connected graph $G$ of order $n$ and radius $r,$ we prove the bound $\text{ept}(G) = O(r\log(n/r)).$ We also show using Doob's Optional Stopping Theorem and a combinatorial object known as a cornerstone that $\text{ept}(G) \le n/2 + O(\log n).$ Finally, we derive an explicit lower bound $\text{ept}(G)\ge \log_2 \log_2 n.$


翻译:概率零强迫是一个在图形上播放的彩色游戏, 目标是从最初的蓝色顶点设置开始, 给每个顶点上色, 从最初的蓝色顶点设置开始 。 只要图形连接, 如果至少一个顶点是蓝色的, 那么最终所有顶点都将是蓝色的。 概率零强迫中研究最多的参数是从给定的顶点G美元开始的预期传播时间。 本文中, 我们用图表的顺序和半径来改进Geneson和Hogben及Chan等人的预期传播时间的上界。 特别是, 对于一个连接的图表, $G$G$( 美元) 和半径为$r, 我们用 $\ text{ ept} (G) = O(r\log (n/r) 。 我们还用 Doob 的选项停止 Theorem 和一个被称作“ $text{ept} (G)\ n/2 + O(\log n) $, 我们用一个清晰的底框$\ text_\\\\\\\\ g} g) 显示一个基点的基点。 最后, 我们以明确的 $\\\\\\\\\\\\ g\\\\\\ g\ g\ g\ g\\\\\ g\\\\\\ g\ g\ g\ g\ g\\\\\\\\\ g\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

0
下载
关闭预览

相关内容

专知会员服务
28+阅读 · 2021年8月2日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
TensorFlow 2.0 学习资源汇总
专知会员服务
66+阅读 · 2019年10月9日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
弱监督语义分割最新方法资源列表
专知
9+阅读 · 2019年2月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
自然语言处理 (NLP)资源大全
机械鸡
35+阅读 · 2017年9月17日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
Arxiv
0+阅读 · 2021年9月30日
Arxiv
0+阅读 · 2021年9月29日
Arxiv
0+阅读 · 2021年9月29日
VIP会员
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
弱监督语义分割最新方法资源列表
专知
9+阅读 · 2019年2月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
自然语言处理 (NLP)资源大全
机械鸡
35+阅读 · 2017年9月17日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
Top
微信扫码咨询专知VIP会员