Conjecture and Related Problems

Title: Conjecture and Related Problems

Research Question: Can we resolve Alon's Second Eigenvalue Conjecture for various models of random d-regular graphs?

Methodology: The authors used the trace method, a technique that involves considering the sum of the eigenvalues of the adjacency matrix. They focused on a specific model of random d-regular graphs, called Gn,d, where d is an even positive integer and n is the number of vertices. In this model, d/2 permutations on the vertices are chosen uniformly and independently, and the graph is formed by connecting vertices according to these permutations.

Results: The authors proved Theorem 1.1, which states that for a random graph in the Gn,d model, with probability at least 1−c/nτ, the absolute value of all eigenvalues except the first (λ1=d) is bounded by 2√ d−1 +ǫ, where τ is a constant related to the model. They also showed that for some constant c′, the second eigenvalue (λ2) is greater than 2√ d−1 with probability at least c′/ns.

Implications: These results resolve Alon's Second Eigenvalue Conjecture for the Gn,d model of random d-regular graphs. They also suggest that there might be a gap between the bounds τfund and s in Theorem 1.1, which could be improved upon. The results have implications for the study of random graphs and their properties, such as being expanders or magnifiers.

Link to Article: https://arxiv.org/abs/0405020v1 Authors: arXiv ID: 0405020v1