SIZE BIASED COUPLINGS AND THE SPECTRAL GAP FOR RANDOM REGULAR GRAPHS

• 成果类型: Article
• 署名作者: Cook, Nicholas; Goldstein, Larry; Johnson, Tobias
• 署名单位: Stanford University; University of Southern California
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/17-AOP1180
• 发表日期: 2018
• 页码: 72-125
• 关键词: 2nd eigenvalue; steins method; probability-inequalities; expander graphs

摘要

Let lambda be the second largest eigenvalue in absolute value of a uniform random d-regular graph on n vertices. It was famously conjectured by Alon and proved by Friedman that if d is fixed independent of n, then lambda = 2 root d - 1+ o(1) with high probability. In the present work, we show that lambda = O(root d) continues to hold with high probability as long as d = O(n(2/3)), making progress toward a conjecture of Vu that the bound holds for all 1 <= 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(n(1/2)). We are able to go beyond this barrier by proving concentration of measure results directly for the uniform distribution on d-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.