The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs

Details The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs

2006-11-21

arxiv.org/abs/math/0611649v2

Experimental Mathematics 17 (2008), no. 2, 231--244

Mathematics

Combinatorics

23 pages, version 2 (MAJOR correction: see footnote 7 on page 7: the eigenvalue program unkowingly assumed the eigenvalues of

Scientific paper

Recently Friedman proved Alon's conjecture for many families of d-regular graphs, namely that given any epsilon > 0 `most' graphs have their largest non-trivial eigenvalue at most 2 sqrt{d-1}+epsilon in absolute value; if the absolute value of the largest non-trivial eigenvalue is at most 2 sqrt{d-1} then the graph is said to be Ramanujan. These graphs have important applications in communication network theory, allowing the construction of superconcentrators and nonblocking networks, coding theory and cryptography. As many of these applications depend on the size of the largest non-trivial positive and negative eigenvalues, it is natural to investigate their distributions. We show these are well-modeled by the beta=1 Tracy-Widom distribution for several families. If the observed growth rates of the mean and standard deviation as a function of the number of vertices holds in the limit, then in the limit approximately 52% of d-regular graphs from bipartite families should be Ramanujan, and about 27% from non-bipartite families (assuming the largest positive and negative eigenvalues are independent).

Affiliated with

Also associated with

No associations

Rating

The Distribution of the Largest Non-trivial Eigenvalues in Families of 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 The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-338889