11:00 am Monday, April 28, 2014
Mathematical Physics/Complex Networks Seminar : The Relative Alon Conjecture for Regular Graphs by Joel Friedman (Univ. British Columbia) in RLM 12.166
The Alon Second Eigenvalue Conjecture says that for fixed integer, d, and fixed epsilon 0, a random d-regular graphs on n vertices has its second eigenvalue less than 2 sqrt(d-1) + epsilon with "high probability," i.e., with probability tending to one as n tends to infinity. This was proven by the speaker some ten years ago. We simplify the proof of the Alon Second Eigenvalue Conjecture and prove a generalization of it. Our results not only simplify the proof of the original conjecture, but also give the first bounds for the above probability that are tight to within a multiplicative constant for any fixed d. The main new tool is called "certified traces." The generalization says that for any fixed d-regular graph, B, and an epsilon 0, a random degree n covering map to B has its new eigenvalues at most 2 sqrt(d-1) + epsilon with high probability. This result is of interest for various reasons; for example, it indicates one can obtain new expanders from old expanders--or even a tower of expanders--by taking random covering maps (of sufficiently large degree) to the old expanders. This is joint work with David Kohler. This talk only assumes a basic knowledge of graph theory and linear algebra.
Submitted by