Change search
ReferencesLink to record
Permanent link

Direct link
Local Improvement Gives Better Expanders
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2012 (English)In: Computing Research Repository, Vol. abs/1211.0524Article in journal (Refereed) Published
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
URN: urn:nbn:se:kth:diva-112880OAI: diva2:587534

QC 20130502

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2013-05-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Search in DiVA

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

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

Total: 32 hits
ReferencesLink to record
Permanent link

Direct link