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...
मुख्य लेखकों: | , |
---|---|
स्वरूप: | Journal article |
प्रकाशित: |
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 |