## Abstract

We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counter-intuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of Erdős-Rényi random graphs G(n, p) with constant edge density p ∈ (0, 1), the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of G(n, p), which might be of independent interest.

Original language | English (US) |
---|---|

Pages (from-to) | 584-611 |

Number of pages | 28 |

Journal | Random Structures and Algorithms |

Volume | 50 |

Issue number | 4 |

DOIs | |

State | Published - Jul 2017 |

## Keywords

- Braess's paradox
- graph Laplacian
- random graphs
- spectral gap

## ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics