Quasirandom Cayley graphs
Copyright policy )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.
Reformatted for Discrete Analysis
- California Institute of Technology United States
- University of Oxford United Kingdom
Graphs and linear algebra (matrices, eigenvalues, etc.), Random graphs (graph-theoretic aspects), Group Theory (math.GR), 510, 004, Graphs and abstract algebra (groups, rings, fields, etc.), QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Group Theory, Mathematics
Graphs and linear algebra (matrices, eigenvalues, etc.), Random graphs (graph-theoretic aspects), Group Theory (math.GR), 510, 004, Graphs and abstract algebra (groups, rings, fields, etc.), QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Group Theory, Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!