Tata Institute of Fundamental Research
Mixing time and expanders
STCS Colloquium
Speaker:
Debsoumya Chakrabarti (IBS Discrete Mathematics Group)
Organiser:
Jaikumar Radhakrishnan
Date:
Tuesday, 17 May 2022, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
Youtube link: https://youtu.be/N3XRrb3Bgzo
| Speaker: | Debsoumya Chakrabarti (IBS Discrete Mathematics Group) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Tuesday, 17 May 2022, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
Youtube link: https://youtu.be/N3XRrb3Bgzo
Youtube link: https://youtu.be/N3XRrb3Bgzo