Project for CS860 Winter 2022
Flow methods in spectral graph theory
Here is the report. Without going into the background, in this report I proved three little results on top of surveying past work:
- Cut-matching game for vertex expansion. The cut player strategy is the same as in [OSVV], and we show that using vertex-capacitated flows suffices to recover $O(\log n)$ approximation ratio for vertex expansion using this (slightly) modified cut-matching game.
- An alternative proof of planar separation theorem by upper-bounding the three-dimensional dual program of the reweighted eigenvalue SDP by $O(1/n)$.
- Extending the upper bounds on $\lambda_2$ for bounded-genus and minor-free graphs to analogous upper bounds on the reweighted eigenvalue $\lambda_2^*$.
Shout out to my advisor Lap Chi who taught the course! It had a cool format – each week we write up journal entries which could consist of relevant readings/research or attempted solutions to suggested problems. It has a degree of personalization only attainable with a small class and when the instructor really puts his heart into teaching his students. I had a lot of fun delving deeper into these topics, and fun was had even on the last day which was an intense deadline-fighting session. I wrote 10+ pages on that single day and only worked out one of the proofs that afternoon…!
License
Copyright 2016-present George Cushen.
Released under the MIT license.
