# Expanders via Local Edge Flips

### Venue

Society for Industrial and Applied Mathematics (2015), pp. 259-269

### Publication Year

2015

### Authors

Zeyuan Allen-Zhu,, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, Lorenzo Orecchia

### BibTeX

## Abstract

Designing distributed and scalable algorithms to improve network connectivity is a
central topic in peer-to-peer networks. In this paper we focus on the following
well-known problem: given an n-node d-regular network for d=Ω(logn), we want to
design a decentralized, local algorithm that transforms the graph into one that has
good connectivity properties (low diameter, expansion, etc.) without affecting the
sparsity of the graph. To this end, Mahlmann and Schindelhauer introduced the
random "flip" transformation, where in each time step, a random pair of vertices
that have an edge decide to `swap a neighbor'. They conjectured that performing
O(nd) such flips at random would convert any connected d-regular graph into a
d-regular expander graph, with high probability. However, the best known upper
bound for the number of steps is roughly O(n^17d^23), obtained via a delicate
Markov chain comparison argument. Our main result is to prove that a natural
instantiation of the random flip produces an expander in at most O(n^2d^2√logn)
steps, with high probability. Our argument uses a potential-function analysis based
on the matrix exponential, together with the recent beautiful results on the
higher-order Cheeger inequality of graphs. We also show that our technique can be
used to analyze another well-studied random process known as the `random switch',
and show that it produces an expander in O(nd) steps with high probability.