Quasirandom Cayley graphs
We prove that the properties of having small discrepancy and having small second eigenvalue are equivalent in Cayley graphs, extending a result of Kohayakawa, R¨odl, and Schacht, who treated the abelian case. The proof relies on Grothendieck’s inequality. As a corollary, we also prove that a similar...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Discrete Analysis
2017
|
| _version_ | 1826269335890427904 |
|---|---|
| author | Conlon, D Zhao, Y |
| author_facet | Conlon, D Zhao, Y |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | We prove that the properties of having small discrepancy and having small second eigenvalue are equivalent in Cayley graphs, extending a result of Kohayakawa, R¨odl, and Schacht, who treated the abelian case. The proof relies on Grothendieck’s inequality. As a corollary, we also prove that a similar result holds in all vertex-transitive graphs. |
| first_indexed | 2024-03-06T21:23:28Z |
| format | Journal article |
| id | oxford-uuid:4246a556-6d3a-4b22-a78c-2bee5e9351a7 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:23:28Z |
| publishDate | 2017 |
| publisher | Discrete Analysis |
| record_format | dspace |
| spelling | oxford-uuid:4246a556-6d3a-4b22-a78c-2bee5e9351a72022-03-26T14:48:31ZQuasirandom Cayley graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:4246a556-6d3a-4b22-a78c-2bee5e9351a7Symplectic Elements at OxfordDiscrete Analysis2017Conlon, DZhao, YWe prove that the properties of having small discrepancy and having small second eigenvalue are equivalent in Cayley graphs, extending a result of Kohayakawa, R¨odl, and Schacht, who treated the abelian case. The proof relies on Grothendieck’s inequality. As a corollary, we also prove that a similar result holds in all vertex-transitive graphs. |
| spellingShingle | Conlon, D Zhao, Y Quasirandom Cayley graphs |
| title | Quasirandom Cayley graphs |
| title_full | Quasirandom Cayley graphs |
| title_fullStr | Quasirandom Cayley graphs |
| title_full_unstemmed | Quasirandom Cayley graphs |
| title_short | Quasirandom Cayley graphs |
| title_sort | quasirandom cayley graphs |
| work_keys_str_mv | AT conlond quasirandomcayleygraphs AT zhaoy quasirandomcayleygraphs |