| dc.contributor |
Massachusetts Institute of Technology. Department of Mathematics |
|
| dc.creator |
Sah, Ashwin |
|
| dc.creator |
Sawhney, Mehtaab |
|
| dc.creator |
Zhao, Yufei |
|
| dc.date |
2022-10-18T16:47:13Z |
|
| dc.date |
2022-10-18T16:47:13Z |
|
| dc.date |
2020 |
|
| dc.date |
2022-10-18T16:39:01Z |
|
| dc.date.accessioned |
2023-03-01T18:08:57Z |
|
| dc.date.available |
2023-03-01T18:08:57Z |
|
| dc.identifier |
https://hdl.handle.net/1721.1/145890 |
|
| dc.identifier |
Sah, Ashwin, Sawhney, Mehtaab and Zhao, Yufei. 2020. "Cayley Graphs Without a Bounded Eigenbasis." International Mathematics Research Notices, 2022 (8). |
|
| dc.identifier.uri |
http://localhost:8080/xmlui/handle/CUHPOERS/278933 |
|
| dc.description |
<jats:title>Abstract</jats:title>
<jats:p>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.</jats:p> |
|
| dc.format |
application/pdf |
|
| dc.language |
en |
|
| dc.publisher |
Oxford University Press (OUP) |
|
| dc.relation |
10.1093/IMRN/RNAA298 |
|
| dc.relation |
International Mathematics Research Notices |
|
| dc.rights |
Creative Commons Attribution-Noncommercial-Share Alike |
|
| dc.rights |
http://creativecommons.org/licenses/by-nc-sa/4.0/ |
|
| dc.source |
arXiv |
|
| dc.title |
Cayley Graphs Without a Bounded Eigenbasis |
|
| dc.type |
Article |
|
| dc.type |
http://purl.org/eprint/type/JournalArticle |
|