Expanders Reading Group Fall 2016

Organizer: Sivaramakrishnan Natarajan Ramamoorthy
Email: sivanr [at] cs [dot] washington [dot] edu

Meetings: Wednesdays 4:30-6pm, CSE 306

This reading group is a students-only group (any interested student may attend, including those outside CSE). Send the organizer an email for questions.

Topic	Speaker	Date	Reference
Basic Definitions	Siva	October 5	Chapter 2 from [1], Exercises from [2]
Mixing time in Expanders	Alireza	October 12	Chapter 3 from [1]
Cheeger's Inequality	Jeffrey	October 19	Chapter 4, 5.1, 5.2 from [1]
Spectrum of infinite d-regular tree	Siva	November 2	[3], Chapter 5.3 from [1]
Alon Boppana Theorem	Siva	November 9	[4], Chapter 6 from [1]
Margulis Expander	Jeffrey	November 16	[5]
The Zig-Zag Product	Alireza	November 30	[6],[7]
Higher-Order Cheeger's Inequality	Yuqing	December 8	[8]

References

[1]: http://www.math.ias.edu/~boaz/ExpanderCourse/allnotes.pdf
[2]: https://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/
[3]: https://lucatrevisan.wordpress.com/2014/08/20/the-spectrum-of-the-infinite-tree/
[4]: https://lucatrevisan.wordpress.com/2014/09/01/the-alon-boppana-theorem-2/
[5]: https://tcsmath.org/2012/04/18/gabber-galil-analysis-of-margulis-expanders/
[6]: https://lucatrevisan.wordpress.com/2016/04/19/cs294-lecture-16-zig-zag-graph-product/
[7]: https://lucatrevisan.wordpress.com/2016/04/19/cs294-lecture-17-zig-zag-graph-product/
[8]: https://arxiv.org/abs/1111.1055/