Cayley Graphs Without a Bounded Eigenbasis
Cayley Graphs Without a Bounded Eigenbasis
复制标题
没有有界本征基的凯莱图
DOI：
10.1093/imrn/rnaa298
复制
发表时间：
2020
影响因子：
1
通讯作者：
Zhao, Yufei
中科院分区：
文献类型：
--
作者：
Sah, Ashwin;Sawhney, Mehtaab;Zhao, Yufei
是否每个顶点的凯莱图都有一个其坐标都是的正交本征基？虽然对阿贝尔群的回答是肯定的，但我们证明了它一般是否定的。另一方面，我们证明了每个顶点Cayley图（更一般地说，顶点传递图）有一个正交基，其坐标是所有的，并且这个界几乎是最好的可能。我们的调查是出于一个问题的Assaf Naor，谁证明了随机阿贝尔凯莱图是小集扩张，扩展了经典的结果Alon-Roichman。他的证明依赖于阿贝尔凯莱图的有界本征基的存在，我们现在知道这对一般群不成立。另一方面，我们绕过这个障碍，并扩展Naor的结果nonabelian组。
Does every-vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are? While the answer is yes for abelian groups, we show that it is no in general. On the other hand, we show that every-vertex Cayley graph (and more generally, vertex-transitive graph) has an orthonormal basis whose coordinates are all, and that this bound is nearly best possible. Our investigation is motivated by a question of Assaf Naor, who proved that random abelian Cayley graphs are small-set expanders, extending a classic result of Alon–Roichman. His proof relies on the existence of a bounded eigenbasis for abelian Cayley graphs, which we now know cannot hold for general groups. On the other hand, we navigate around this obstruction and extend Naor’s result to nonabelian groups.
登录
查看更多内容
拟随机凯莱图
DOI：
10.19086/da.1294
发表时间：
2016
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
D. Conlon;Yufei Zhao
通讯作者：
Yufei Zhao
影响因子：
2.5
作者：
B. Green
通讯作者：
B. Green
关于Banach空间值的Azuma不等式和Alon-Roichman图的小集等周图
DOI：
10.1017/s0963548311000757
发表时间：
2010
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
A. Naor
通讯作者：
A. Naor
DOI：
10.1090/s0002-9947-1958-0100235-1
发表时间：
1958-02
影响因子：
1.3
作者：
R. Kunze
通讯作者：
R. Kunze