Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Braess's paradox for the spectral gap in random graphs and
  delocalization of eigenvectors   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 counterintuitively, 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\H{o}s-R\'enyi random graphs $G(n,p)$ with constant edge density $p \in
(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.

8
The categories of this paper are: hep-ex
7
The categories of this paper are: hep-th
3
The categories of this paper are: physics
18
The categories of this paper are: econ
15
The categories of this paper are: nucl-ex
22
The categories of this paper are: chao-dyn
37
The categories of this paper are: supr-con
14
The categories of this paper are: math-ph
29
The categories of this paper are: funct-an
0
The categories of this paper are: hep-ph
32
The categories of this paper are: atom-ph
4
The categories of this paper are: cond-mat
26
The categories of this paper are: bayes-an
19
The categories of this paper are: eess
28
The categories of this paper are: alg-geom
6
The categories of this paper are: astro-ph