Course Project for CS860 Winter 2022

Here is the report. Without going into the background, in this report I proved three little results on top of surveying past work:

1. 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.
2. An alternative proof of planar separation theorem by upper-bounding the three-dimensional dual program of the reweighted eigenvalue SDP by $O(1/n)$.
3. Extending the upper bounds on $\lambda_2$ for bounded-genus and minor-free graphs to analogous upper bounds on the reweighted eigenvalue $\lambda_2^*$.

Update on 8 February 2025: Some of these results have turned into Chapter 7 of my PhD thesis.