umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2008 (Engelska)Ingår i: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 32, nr 1, s. 88-100Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Wiley-Blackwell, 2008. Vol. 32, nr 1, s. 88-100
Nationell ämneskategori
Sannolikhetsteori och statistik Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-7590DOI: 10.1002/rsa.20177ISI: 000251767500006OAI: oai:DiVA.org:umu-7590DiVA, id: diva2:147261
Tillgänglig från: 2008-01-11 Skapad: 2008-01-11 Senast uppdaterad: 2019-07-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Markström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Markström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Random structures & algorithms (Print)
Sannolikhetsteori och statistikDiskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 101 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf