Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 8, 2017 | Published
Journal Article Open

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ödl, 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.

Additional Information

© 2017 David Conlon and Yufei Zhao. Licensed under a Creative Commons Attribution License (CC-BY). Received 21 April 2016; revised 28 February 2017; published 8 March 2017. The first author was supported by a Royal Society University Research Fellowship and ERC Starting Grant 676632. The second author was supported by an Esmée Fairbairn Junior Research Fellowship at New College, Oxford.

Attached Files

Published - 1603.03025.pdf


Files (318.7 kB)
Name Size Download all
318.7 kB Preview Download

Additional details

August 19, 2023
October 18, 2023