Quasirandom Cayley graphs

Creators: Conlon, David; Zhao, Yufei

Abstract

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

1603.03025.pdf

Files (318.7 kB)

Name	Size	Download all
1603.03025.pdf md5:a2f3d48492586e15dd467e47b58d4434	318.7 kB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes