In a graph, we call a vertex well-mixing if the standard random walk starting from that vertex reaches close to its stationary distribution fast (say within 'polylogarithmic in the size of the vertex set' steps). Call a graph well-mixing if all of its vertices are well-mixing. Call a graph expander if every subset of vertices has a large boundary (in other words, the cut induced by every bipartition of the vertex set is 'large'). For graphs, it is well-known that the properties of being well-mixing and being an expander are equivalent (in a precise quantitative way). Extending (in a weak sense) this classical result, we establish that a regular graph is virtually an expander even if it has only a positive fraction of vertices that are well-mixing. Indeed, we prove that such a graph becomes an expander after deleting a small number of vertices. As a corollary, it shows that such graphs contain long cycles, which improves a result of Pak. Furthermore, we can obtain such a cycle in polynomial time. This talk will be based on joint work with Jaehoon Kim, Jinha Kim, Minki Kim, and Hong Liu.
