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...

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखकों: Conlon, D, Zhao, Y
स्वरूप: 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