We prove that bounded-degree expanders with non-negative Ollivier-Ricci curvature do not exist, thereby solving a long-standing open problem suggested by Naor and Milman and publicized by Ollivier (2010). In fact, this remains true even if we allow for a vanishing proportion of large degrees, large eigenvalues, and negatively-curved edges. To establish this, we work directly at the level of Benjamini-Schramm limits, and exploit the entropic characterization of the Liouville property on stationary random graphs to show that non-negative curvature and spectral expansion are incompatible "at infinity". We then transfer this result to finite graphs via local weak convergence. The same approach also applies to the Bacry-Emery curvature condition CD$(0,\infty)$, thereby settling a recent conjecture of Cushing, Liu and Peyerimhoff (2019).


翻译:我们证明,没有带有非阴性奥利维埃-里基曲曲线的封闭度扩张器,从而解决了Naor和Milman提出并由Olivier(2010年)公布的长期开放问题。事实上,即使我们允许大度、大电子值和负曲线边缘的消失比例,情况依然如此。为了确立这一点,我们直接在Benjamini-Schramm极限水平上工作,利用固定随机图对Liouville财产进行昆虫特征描述,以显示非阴性曲线和光谱扩展是“无限”不相容的。我们随后通过本地微弱的趋同将这一结果转移到有限的图表中。同样的做法也适用于培利-Emery曲线状况 CD$(0,\inty),从而解决了Cushing、Li和Pyerimihoff(2019年)最近的一个插图。

0
下载
关闭预览

相关内容

【KDD2020教程】多模态网络表示学习
专知会员服务
129+阅读 · 2020年8月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
【论文】结构GANs,Structured GANs,
专知会员服务
14+阅读 · 2020年1月16日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
大神 一年100篇论文
CreateAMind
15+阅读 · 2018年12月31日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年3月23日
VIP会员
相关VIP内容
【KDD2020教程】多模态网络表示学习
专知会员服务
129+阅读 · 2020年8月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
【论文】结构GANs,Structured GANs,
专知会员服务
14+阅读 · 2020年1月16日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
大神 一年100篇论文
CreateAMind
15+阅读 · 2018年12月31日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员