Functional limit theorems for random regular graphs

Details Functional limit theorems for random regular graphs Functional limit theorems for random regular graphs

2011-09-19

arxiv.org/abs/1109.4094v2

Mathematics

Probability

Added some references and corrected typos. Added Remark 38. 39 pages

Scientific paper

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 regular graph of degree 2d on n vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as n grows to infinity, either when d is kept fixed or grows slowly with n. In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein's method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn-Szemer\'edi argument for estimating the second largest eigenvalue for all values of d and n.

Affiliated with

Also associated with

No associations

Rating

Functional limit theorems for random regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Functional limit theorems for random regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Functional limit theorems for random regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-97337