Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Local Improvement Gives Better Expanders
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2012 (English)Manuscript (preprint) (Other academic)
Abstract [en]

It has long been known that random regular graphs are with high probability good ex-panders. This was first established in the 1980s by Bollobás by directly calculating the probability thata set of vertices has small expansion and then applying the union bound. In this paper we improve on this analysis by relying on a simple high-level observation: if a graphcontains a set of vertices with small expansion then it must also contain such a set of vertices that islocally optimal, that is, a set whose expansion cannot be made smaller by exchanging a vertex fromthe set with one from the set’s complement. We show that the probability that a set of vertices satisfiesthis additional property is significantly smaller. Thus, after again applying the union bound, we obtainimproved lower bounds on the expansion of random ∆-regular graphs for∆≥4. In fact, the gains fromthis analysis increase as ∆ grows, a fact we explain by extending our technique to general ∆. Thus, inthe end we obtain an improvement not only for some small special cases but on the general asymptoticbound on the expansion of ∆-regular graphs given by Bollobás

Place, publisher, year, edition, pages
2012. Vol. abs/1211.0524
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-112880OAI: oai:DiVA.org:kth-112880DiVA: diva2:587534
Note

QC 20130502

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2017-04-12Bibliographically approved

Open Access in DiVA

No full text

Other links

arXiv

Search in DiVA

By author/editor
Lampis, Michael
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 38 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf