Change search
ReferencesLink to record
Permanent link

Direct link
Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
2008 (English)In: Random Structures and Algorithms, ISSN 1042-9832, Vol. 32, no 1, 88-100 p.Article in journal (Refereed) Published
Abstract [en]

The Alon-Roichman theorem states that for every $\ge > 0$ there is a constant $c(\ge)$, such that the Cayley graph of a finite group $G$ with respect to $c(\ge)\log{\abs{G}}$ elements of $G$, chosen independently and uniformly at random, has expected second largest eigenvalue less than $\ge$. In particular, such a graph is an expander with high probability.

Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a simpler proof of the result, improving the bounds even further. When considered for a general group $G$, our bounds are in a sense best possible.

We also give a generalisation of the Alon-Roichman theorem to random coset graphs.

Place, publisher, year, edition, pages
2008. Vol. 32, no 1, 88-100 p.
URN: urn:nbn:se:umu:diva-7590DOI: doi:10.1002/rsa.20177OAI: diva2:147261
Available from: 2008-01-11 Created: 2008-01-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Markström, Klas
By organisation
Mathematics and Mathematical Statistics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 29 hits
ReferencesLink to record
Permanent link

Direct link