Size biased couplings and the spectral gap for random regular graphs. (English) Zbl 1386.05105
Summary: 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 N. Alon [Combinatorica 6, 83–96 (1986; Zbl 0661.05053)] and proved by J. Friedman [Mem. Am. Math. Soc. 910, 100 p. (2008; Zbl 1177.05070)] that if \(d\) is fixed independent of \(n\), then \(\lambda=2\sqrt{d-1}+o(1)\) with high probability. In the present work, we show that \(\lambda=O(\sqrt{d})\) continues to hold with high probability as long as \(d=O(n^{2/3})\), making progress toward a conjecture of V. Vu [Bolyai Soc. Math. Stud. 17, 257–280 (2008; Zbl 1154.15024)] that the bound holds for all \(1\leq d\leq n/2\). Prior to this work the best result was obtained by A. Z. Broder et al. [SIAM J. Comput. 28, No. 2, 541–573 (1998; Zbl 0912.05058)] 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.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60B20 | Random matrices (probabilistic aspects) |
| 60E15 | Inequalities; stochastic orderings |
| 15B52 | Random matrices (algebraic aspects) |
Keywords:
second eigenvalue; random regular graph; Alon’s conjecture; size biased coupling; Stein’s method; concentrationReferences:
| [1] | Alon, N. (1986). Eigenvalues and expanders. Combinatorica 6 83-96. Theory of computing (Singer Island, Fla., 1984). · Zbl 0661.05053 |
| [2] | Alon, N. and Milman, V. D. (1985). \(λ_1\), isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38 73-88. · Zbl 0549.05051 |
| [3] | Arratia, R. and Baxendale, P. (2015). Bounded size bias coupling: A Gamma function bound, and universal Dickman-function behavior. Probab. Theory Related Fields 162 411-429. · Zbl 1323.60034 |
| [4] | Arratia, R., Goldstein, L. and Kochman, F. (2015). Size bias for one and all. ArXiv preprint. Available at arXiv:1308.2729. · Zbl 1427.60002 |
| [5] | Baldi, P., Rinott, Y. and Stein, C. (1989). A normal approximation for the number of local maxima of a random function on a graph. In Probability, Statistics, and Mathematics 59-81. Academic Press, Boston, MA. · Zbl 0704.62018 |
| [6] | Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford Studies in Probability 2. Oxford Univ. Press, New York. · Zbl 0746.60002 |
| [7] | Bartroff, J., Goldstein, L. and Işlak, Ü. (2014). Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models. ArXiv preprint. Available at arXiv:1402.6769. · Zbl 1407.60032 |
| [8] | Bauerschmidt, R., Huang, J., Knowles, A. and Yau, H.-T. (2015). Bulk eigenvalue statistics for random regular graphs. ArXiv preprint. Available at arXiv:1505.06700. · Zbl 1379.05098 |
| [9] | Bauerschmidt, R., Knowles, A. and Yau, H.-T. (2015). Local semicircle law for random regular graphs. ArXiv preprint. Available at arXiv:1503.08702. · Zbl 1372.05194 |
| [10] | Bennett, G. (1962). Probability inequalities for the sum of independent random variables. J. Amer. Statist. Assoc.57 33-45. · Zbl 0123.36101 · doi:10.1093/biomet/50.3-4.528 |
| [11] | Bernstein, S. (1924). On a modification of Chebyshev’s inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math.1 38-49. |
| [12] | Bordenave, C. (2015). A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. ArXiv preprint. Available at arXiv:1502.04482. · Zbl 1462.05324 |
| [13] | Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities. A Nonasymptotic Theory of Independence. Oxford Univ. Press, Oxford. · Zbl 1279.60005 |
| [14] | Broder, A. and Shamir, E. (1987). On the second eigenvalue of random regular graphs. In 28 th Annual Symposium on Foundations of Computer Science (Los Angeles) 286-294. IEEE Comput. Soc. Press, Washington, DC. |
| [15] | Broder, A. Z., Frieze, A. M., Suen, S. and Upfal, E. (1999). Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput.28 541-573. · Zbl 0912.05058 |
| [16] | Chatterjee, S. (2007). Stein’s method for concentration inequalities. Probab. Theory Related Fields 138 305-321. · Zbl 1116.60056 |
| [17] | Chatterjee, S. and Dey, P. S. (2010). Applications of Stein’s method for concentration inequalities. Ann. Probab.38 2443-2485. · Zbl 1203.60023 |
| [18] | Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal Approximation by Stein’s Method. Probability and Its Applications (New York). Springer, Heidelberg. · Zbl 1213.62027 |
| [19] | Chung, F., Lu, L. and Vu, V. (2003). Spectra of random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 100 6313-6318. · Zbl 1064.05138 |
| [20] | Coja-Oghlan, A. and Lanka, A. (2009). The spectral gap of random graphs with given expected degrees. Electron. J. Combin.16 Research Paper 138. · Zbl 1187.05048 |
| [21] | Cook, N. A. (2017). Discrepancy properties for random regular digraphs. Random Structures Algorithms 50 23-58. · Zbl 1352.05164 |
| [22] | Cook, N. A. (2017). On the singularity of adjacency matrices for random regular digraphs. Probab. Theory Related Fields 167 143-200. · Zbl 1365.05260 |
| [23] | Dumitriu, I., Johnson, T., Pal, S. and Paquette, E. (2013). Functional limit theorems for random regular graphs. Probab. Theory Related Fields 156 921-975. · Zbl 1271.05088 |
| [24] | Dumitriu, I. and Pal, S. (2012). Sparse regular random graphs: Spectral density and eigenvectors. Ann. Probab.40 2197-2235. · Zbl 1255.05173 |
| [25] | Feige, U. and Ofek, E. (2005). Spectral techniques applied to sparse random graphs. Random Structures Algorithms 27 251-275. · Zbl 1076.05073 |
| [26] | Friedman, J. (1991). On the second eigenvalue and random walks in random \(d\)-regular graphs. Combinatorica 11 331-362. · Zbl 0760.05078 |
| [27] | Friedman, J. (2008). A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc.195 viii+100. · Zbl 1177.05070 |
| [28] | Friedman, J., Kahn, J. and Szemerédi, E. (1989). On the second eigenvalue of random regular graphs. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC’89 587-598. ACM, New York. |
| [29] | Friedman, J. and Wigderson, A. (1995). On the second eigenvalue of hypergraphs. Combinatorica 15 43-65. · Zbl 0843.05075 |
| [30] | Ghosh, S. and Goldstein, L. (2011). Concentration of measures via size-biased couplings. Probab. Theory Related Fields 149 271-278. · Zbl 1239.60011 |
| [31] | Ghosh, S., Goldstein, L. and Raič, M. (2011). Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings. Statist. Probab. Lett.81 1565-1570. · Zbl 1226.05227 |
| [32] | Goldstein, L. and Işlak, Ü. (2014). Concentration inequalities via zero bias couplings. Statist. Probab. Lett.86 17-23. · Zbl 1292.60030 |
| [33] | Goldstein, L. and Rinott, Y. (1996). Multivariate normal approximations by Stein’s method and size bias couplings. J. Appl. Probab.33 1-17. · Zbl 0845.60023 |
| [34] | Greenhill, C., Janson, S., Kim, J. H. and Wormald, N. C. (2002). Permutation pseudographs and contiguity. Combin. Probab. Comput.11 273-298. · Zbl 1006.05056 |
| [35] | Hoeffding, W. (1951). A combinatorial central limit theorem. Ann. Math. Stat.22 558-566. · Zbl 0044.13702 |
| [36] | Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc.58 13-30. · Zbl 0127.10602 |
| [37] | Hoory, S., Linial, N. and Wigderson, A. (2006). Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43 439-561. · Zbl 1147.68608 |
| [38] | Janson, S. (2009). The probability that a random multigraph is simple. Combin. Probab. Comput.18 205-225. · Zbl 1216.05145 |
| [39] | Johnson, T. (2015). Exchangeable pairs, switchings, and random regular graphs. Electron. J. Combin.22 Paper 1.33. · Zbl 1307.05205 |
| [40] | Keshavan, R. H., Montanari, A. and Oh, S. (2010). Matrix completion from a few entries. IEEE Trans. Inform. Theory 56 2980-2998. · Zbl 1366.62111 |
| [41] | Krivelevich, M., Sudakov, B., Vu, V. H. and Wormald, N. C. (2001). Random regular graphs of high degree. Random Structures Algorithms 18 346-363. · Zbl 0996.05106 |
| [42] | Lubetzky, E., Sudakov, B. and Vu, V. (2011). Spectra of lifted Ramanujan graphs. Adv. Math.227 1612-1645. · Zbl 1222.05168 |
| [43] | Lubotzky, A. (2012). Expander graphs in pure and applied mathematics. Bull. Amer. Math. Soc. (N.S.) 49 113-162. · Zbl 1232.05194 · doi:10.1090/S0273-0979-2011-01359-3 |
| [44] | McKay, B. D., Wormald, N. C. and Wysocka, B. (2004). Short cycles in random regular graphs. Electron. J. Combin.11 Research Paper 66. · Zbl 1063.05122 |
| [45] | Miller, S. J., Novikoff, T. and Sabelli, A. (2008). The distribution of the largest nontrivial eigenvalues in families of random regular graphs. Exp. Math.17 231-244. · Zbl 1151.05043 · doi:10.1080/10586458.2008.10129029 |
| [46] | Nilli, A. (1991). On the second eigenvalue of a graph. Discrete Math.91 207-210. · Zbl 0771.05064 |
| [47] | Raič, M. (2007). CLT-related large deviation bounds based on Stein’s method. Adv. in Appl. Probab.39 731-752. · Zbl 1127.60024 |
| [48] | Ross, N. (2011). Fundamentals of Stein’s method. Probab. Surv.8 210-293. · Zbl 1245.60033 |
| [49] | Stein, C. (1986). Approximate Computation of Expectations. Institute of Mathematical Statistics Lecture Notes—Monograph Series 7. IMS, Hayward, CA. · Zbl 0721.60016 |
| [50] | Tikhomirov, K. and Youssef, P. (2016). The spectral gap of dense random regular graphs. ArXiv preprint. Available at arXiv:1610.01765. · Zbl 1407.05212 |
| [51] | Tracy, C. A. and Widom, H. (1994). Level-spacing distributions and the Airy kernel. Comm. Math. Phys.159 151-174. · Zbl 0789.35152 |
| [52] | Tran, L. V., Vu, V. H. and Wang, K. (2013). Sparse random graphs: Eigenvalues and eigenvectors. Random Structures Algorithms 42 110-134. · Zbl 1257.05089 · doi:10.1002/rsa.20406 |
| [53] | Vu, V. (2008). Random discrete matrices. In Horizons of Combinatorics. Bolyai Soc. Math. Stud.17 257-280. Springer, Berlin. · Zbl 1154.15024 |
| [54] | Wormald, N. C. (1999). Models of random regular graphs. In Surveys in Combinatorics, 1999 (Canterbury). London Mathematical Society Lecture Note Series 267 239-298. · Zbl 0935.05080 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
