Department of Mathematical Sciences
|Thursday, February 20, 2018
|1:15pm – 5:15pm
|Yinsong Chen, Binghamton University
|The Conductance and Mixing Time
The conductance of a graph can be used to provide both upper and lower bound of the mixing time. I will talk about the basic theorem for the bound and serval examples. An artificial glued graph and the rectangle tiling will be included in the application for lower bound. The example random walk on hyper cube will be concerned for upper bound to provide the idea that we can lower bound the conductance by “counting the max number of path passing through an edge”.