Presenter: Hao Song
In this presentation, I will continue the investigation into the triangulation graph random walk problem.
1. Brief review of the conductance technique - a commonly used technique to prove mixing time upper bound
2. Method used in Michael Molloy et al.'s 1998 paper to prove a polynomial upper bound of the random walk mixing time on the triangulation graph of a convex polygon. The method involves proving the existence a big matching between an arbitrary subset of the whole triangulation set and its complement, which, in turn, gives a lower bound on conductance.
3. Some of my efforts to generalize the method, and the difficulty I'm trying to overcome.