# The spectral gap of dense random regular graphs

@article{Tikhomirov2019TheSG, title={The spectral gap of dense random regular graphs}, author={Konstantin E. Tikhomirov and Pierre Youssef}, journal={The Annals of Probability}, year={2019} }

For any $\alpha\in (0,1)$ and any $n^{\alpha}\leq d\leq n/2$, we show that $\lambda(G)\leq C_\alpha \sqrt{d}$ with probability at least $1-\frac{1}{n}$, where $G$ is the uniform random $d$-regular graph on $n$ vertices, $\lambda(G)$ denotes its second largest eigenvalue (in absolute value) and $C_\alpha$ is a constant depending only on $\alpha$. Combined with earlier results in this direction covering the case of sparse random graphs, this completely settles the problem of estimating the… Expand

#### 22 Citations

Structure of eigenvectors of random regular digraphs

- Mathematics
- Transactions of the American Mathematical Society
- 2019

Let $n$ be a large integer, let $d$ satisfy $C\leq d\leq \exp(c\sqrt{\ln n})$ for some universal constants $c, C>0$, and let $z\in {\mathcal C}$. Further, denote by $M$ the adjacency matrix of a… Expand

Large subgraphs in pseudo-random graphs

- Mathematics
- 2016

We consider classes of pseudo-random graphs on $n$ vertices for which the degree of every vertex and the co-degree between every pair of vertices are in the intervals $(np - Cn^\delta,np+Cn^\delta)$… Expand

Circular law for sparse random regular digraphs

- Mathematics
- 2018

Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices.… Expand

Complete Minors in Graphs Without Sparse Cuts

- Mathematics
- International Mathematics Research Notices
- 2019

We show that if $G$ is a graph on $n$ vertices, with all degrees comparable to some $d = d(n)$, and without a sparse cut, for a suitably chosen notion of sparseness, then it contains a complete… Expand

On the norm of a random jointly exchangeable matrix

- Mathematics
- Journal of Theoretical Probability
- 2018

In this note, we show that the norm of an $$n\times n$$n×n random jointly exchangeable matrix with zero diagonal can be estimated in terms of the norm of its $$\lfloor n/2\rfloor \times \lfloor… Expand

Dirac’s theorem for random regular graphs

- Mathematics, Computer Science
- Combinatorics, Probability and Computing
- 2020

A ‘resilience’ version of Dirac’s theorem in the setting of random regular graphs is proved, showing that whenever d is sufficiently large compared to $\epsilon > 0$ , a.s.a. the following holds. Expand

Size biased couplings and the spectral gap for random regular graphs

- Mathematics
- 2018

Let λλ be the second largest eigenvalue in absolute value of a uniform random dd-regular graph on nn vertices. It was famously conjectured by Alon and proved by Friedman that if dd is fixed… Expand

1-Factorizations of Pseudorandom Graphs

- Mathematics, Computer Science
- 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
- 2018

It is proved that for any ε > 0, an (n, d,λ)-graph G (that is, a d-regular graph on n vertices whose second largest eigenvalue in absolute value is at most λ) admits a 1-factorization provided that n is even, and C_0 ≤ d ≤ n-1 (where C-0=C_0(ε) is a constant depending only on ε). Expand

Reliable communication over highly connected noisy networks

- Computer Science, Mathematics
- Distributed Computing
- 2017

It is shown that if a (d-regular) network has mixing time m, then there exists an efficient coding scheme with rate O(1/m^3\log m)$$O( 1/m3logm), which implies a constant rate coding scheme for any n-party protocol over a d-regular network with a constant mixing time. Expand

Sherali-adams strikes back

- Computer Science, Mathematics
- Computational Complexity Conference
- 2019

The results imply that constant-round Sherali-Adams can strongly refute random Boolean k-CSP instances with n[EQUATION] constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy. Expand

#### References

SHOWING 1-10 OF 29 REFERENCES

Adjacency matrices of random digraphs: singularity and anti-concentration

- Mathematics
- 2015

Let ${\mathcal D}_{n,d}$ be the set of all $d$-regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We… Expand

On the singularity of adjacency matrices for random regular digraphs

- Mathematics
- 2014

We prove that the (non-symmetric) adjacency matrix of a uniform random d-regular directed graph on n vertices is asymptotically almost surely invertible, assuming $$\min (d,n-d)\ge C\log… Expand

Expansion of random graphs: new proofs, new results

- Mathematics
- 2015

We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on recent deep results in combinatorial group theory. It applies to both regular and… Expand

Functional limit theorems for random regular graphs

- Mathematics
- 2013

Consider $$d$$ uniformly random permutation matrices on $$n$$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random… Expand

On the second eigenvalue and random walks in randomd-regular graphs

- Mathematics, Computer Science
- Comb.
- 1991

It follows, for example, that for fixedd the second eigenvalue's magnitude is no more than 2d - 1 + 2\log d + C' with probability 1−n−C for constantsC andC′ for sufficiently largen. Expand

Optimal construction of edge-disjoint paths in random graphs

- Mathematics, Computer Science
- SODA '94
- 1994

The results give the first tight bounds for the edge-disjoint paths problem for any nontrivial class of graphs. Expand

On the norm of a random jointly exchangeable matrix

- Mathematics
- Journal of Theoretical Probability
- 2018

In this note, we show that the norm of an $$n\times n$$n×n random jointly exchangeable matrix with zero diagonal can be estimated in terms of the norm of its $$\lfloor n/2\rfloor \times \lfloor… Expand

Local semicircle law for random regular graphs

- Mathematics, Physics
- 2015

We consider random $d$-regular graphs on $N$ vertices, with degree $d$ at least $(\log N)^4$. We prove that the Green's function of the adjacency matrix and the Stieltjes transform of its empirical… Expand

A proof of Alon's second eigenvalue conjecture and related problems

- Mathematics, Computer Science
- ArXiv
- 2004

These theorems resolve the conjecture of Alon, that says that for any > 0a ndd, the second largest eigenvalue of \ most" random dregular graphs are at most 2 p d 1+ (Alon did not specify precisely what \most" should mean or what model of random graph one should take). Expand

Size biased couplings and the spectral gap for random regular graphs

- Mathematics
- 2018

Let λλ be the second largest eigenvalue in absolute value of a uniform random dd-regular graph on nn vertices. It was famously conjectured by Alon and proved by Friedman that if dd is fixed… Expand