论文标题
Cayley图形没有有限的本egenbasis
Cayley graphs without a bounded eigenbasis
论文作者
论文摘要
每个$ n $ vertex cayley图都有一个正顺式的eigenbasis，其所有其坐标为$ o（1/\ sqrt {n}）$？虽然答案是Abelian群体是肯定的，但我们表明这不是。 另一方面，我们表明，每$ n $ vertex cayley图（并且更一般而言，顶点传递图）具有正顺式基础，其坐标都是$ o（\ sqrt {\ sqrt {\ log n / n}）$，并且几乎可以限制这个界限。 我们的调查是由阿萨夫·纳尔（Assaf Naor）的问题引起的。他的证据依赖于Abelian Cayley图的存在，我们现在知道这对一般群体无法保持。另一方面，我们围绕着这种障碍物导航，并将NAOR的结果扩展到非亚伯群体。
Does every $n$-vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are $O(1/\sqrt{n})$? While the answer is yes for abelian groups, we show that it is no in general. On the other hand, we show that every $n$-vertex Cayley graph (and more generally, vertex-transitive graph) has an orthonormal basis whose coordinates are all $O(\sqrt{\log n / n})$, 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.
