Tata Institute of Fundamental Research
Expansion of Random Graphs: New Proofs, New Results
Special Mathematics Colloquium
Speaker:
Doron Puder (The Hebrew University of Jerusalem
Israel)
Organiser:
Jaikumar Radhakrishnan
Date:
Tuesday, 23 Jul 2013, 11:00 to 12:00
Venue:
AG-77
(Scan to add to calendar)
Abstract:
We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on deep results from combinatorial group theory. It applies both to regular and irregular random graphs.
Let $G$ be a random d-regular graph on n vertices. It was conjectured by Alon (86') and proved by Friedman (08') in a $100\pm$page-long-booklet that the highest non-trivial eigenvalue of $G$ is a.a.s. arbitrarily close to $2\sqrt{(d-1)}$. We give a new, substantially simpler proof, that nearly recovers Friedman's result. This approach also has the advantage of applying to a more general model of random graphs, concerning also
non-regular graphs. Friedman (03') extended Alon's conjecture to this general case, and we obtain new, nearly optimal results here too.
| Speaker: | Doron Puder (The Hebrew University of Jerusalem Israel) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Tuesday, 23 Jul 2013, 11:00 to 12:00 |
| Venue: | AG-77 |
(Scan to add to calendar)
Abstract:
We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on deep results from combinatorial group theory. It applies both to regular and irregular random graphs.
Let $G$ be a random d-regular graph on n vertices. It was conjectured by Alon (86') and proved by Friedman (08') in a $100\pm$page-long-booklet that the highest non-trivial eigenvalue of $G$ is a.a.s. arbitrarily close to $2\sqrt{(d-1)}$. We give a new, substantially simpler proof, that nearly recovers Friedman's result. This approach also has the advantage of applying to a more general model of random graphs, concerning also
non-regular graphs. Friedman (03') extended Alon's conjecture to this general case, and we obtain new, nearly optimal results here too.
Let $G$ be a random d-regular graph on n vertices. It was conjectured by Alon (86') and proved by Friedman (08') in a $100\pm$page-long-booklet that the highest non-trivial eigenvalue of $G$ is a.a.s. arbitrarily close to $2\sqrt{(d-1)}$. We give a new, substantially simpler proof, that nearly recovers Friedman's result. This approach also has the advantage of applying to a more general model of random graphs, concerning also
non-regular graphs. Friedman (03') extended Alon's conjecture to this general case, and we obtain new, nearly optimal results here too.