Size biased couplings and the spectral gap for random regular graphs
By Nicholas A. Cook, Larry Goldstein, Tobias Johnson. 2015
59 citations recorded by the source corpus.
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 independent of nn, then λ=2d−1−−−−√+o(1)λ=2d−1+o(1) with high probability. In the present work, we show that λ=O(d−−√)λ=O(d) continues to hold with high probability as long as d=O(n2/3)d=O(n2/3), making progress toward a conjecture of Vu that the bound holds for all 1≤d≤n/21≤d≤n/2. Prior to this work the best result was obtained by Broder, Frieze, Suen and Upfal (1999) using the configuration model, which hits a barrier at d=o(n1/2)d=o(n1/2). We are able to go beyond this barrier by proving concentration of measure results directly for the uniform distribution on dd-regular graphs. These come as consequences of advances we make in the theory of concentration by size biased couplings. Specifically, we obtain Bennett-type tail estimates for random variables admitting certain unbounded size biased couplings.
Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/0a8275447f14d8ef1e4388c7189d334e1959f769
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
In Geometry and Topology
In Statistics and Probability
Citations in the corpus
- Size bias for one and all (2013, unknown): “An extension to exploit the weaker condition P(X∗ ≤ X + c|X∗) ≥ p ∈ (0, 1) is discussed in [32].”
- The spectral gap of dense random regular graphs (2016, background): “≤ 2exp − dkQk2 HS nkQk2 ∞ H ctnkQk∞ dkQk2 HS . In view of (7), the “shift” d2 n2 Pn i,j=1 Qij is majorized by ed2 n Pn i=1 krowi(Q)klog,n= ed3/2 n ∆(Q). Thus, the concentration inequality from [11] gives sharper estimates than ours provided that 43 d = O(n2/3). On the other hand, for d ≫ n2/3 the”