Local Improvement Gives Better Expanders

arXiv1211.0524MaRDI QIDQ6236875FDOQ6236875

Authors: Michael Lampis 

Publication date: 2 November 2012

Abstract: It has long been known that random regular graphs are with high probability good expanders. This was first established in the 1980s by Bollob'as by directly calculating the probability that a 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 graph contains a set of vertices with small expansion then it must also contain such a set of vertices that is locally optimal, that is, a set whose expansion cannot be made smaller by exchanging a vertex from the set with one from the set's complement. We show that the probability that a set of vertices satisfies this additional property is significantly smaller. Thus, after again applying the union bound, we obtain improved lower bounds on the expansion of random $Delta$-regular graphs for $Deltage4$. In fact, the gains from this analysis increase as $Delta$ grows, a fact we explain by extending our technique to general $Delta$. Thus, in the end we obtain an improvement not only for some small special cases but on the general asymptotic bound on the expansion of $Delta$-regular graphs given by Bollob'as.

This page was built for publication: Local Improvement Gives Better Expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236875)