Group:Student Seminar
Title: Random Walks on Triangulation Graphs of Arbitrary Planar Point Sets
Speaker: Hao Song Tsinghua university
Time: 2010-05-13 16:00-2010-05-13 17:00
Venue: FIT1-222

Abstract:

1. Commonly used techniques to prove upper bound on mixing times - the spectrum gap, conductance, maximum matching and their relationships

2. Michael Molloy et al.'s 1998 paper on the mixing rate of the triangulation walk on convex polygons. Because I'll also present the proof in Thursday's lunch meeting, I'll only cover those details that I can't go into during the earlier meeting.

3. My proof of the connectedness of the triangulation graph of arbitrary planar point set, and the degree lower bound. The connectedness proof is a simplified version of Kai Jin and Xiaohui Bei's.




Short Bio: