# Expanders via Local Edge Flips

arXiv: https://arxiv.org/abs/1510.07768 · HTML: https://mlsanity.com/paper/1510.07768/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2015.

## Built on by (most cited first, 3 of 3)

- [Oversquashing in GNNs through the lens of information contraction and graph expansion](https://mlsanity.com/paper/2208.03471/) (2022)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [Effects of Dropout on Performance in Long-range Graph Learning Tasks](https://mlsanity.com/paper/2502.07364/) (2025)

## Abstract (arXiv)

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=Omega(log n), 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(n d) 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(n17 d23), 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(n2 d2 √log n) 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(n d) steps with high probability.