Well-mixing vertices and almost expanders

DOI10.1090/PROC/16090MaRDI QIDQ5039232zbMATH OpenOpenAlexFDO

Authors Debsoumya Chakraborti, Jinha Kim, Hong Liu, Jaehoon Kim, Min-Ki Kim

Publication date 12 October 2022

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.12864

zbMATH Keywords

random walks

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81) Expander graphs (05C48)

Abstract: We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and has no small separator. This answers a question of Pak [SODA, 2002]. As a corollary, it shows that sparse (constant degree) regular graphs with many well-mixing vertices have a long cycle, improving a result of Pak. Furthermore, such cycle can be found in polynomial time. Secondly, we show that if the random walks from a positive fraction of vertices are well-mixing, then the random walks from almost all vertices are well-mixing (with a slightly worse mixing time).

Recommendations

• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• scientific article; zbMATH DE number 2119679
• Mixing rates of random walks with little backtracking
• Comparing mixing times on sparse random graphs
• Comparing mixing times on sparse random graphs

Cites work

• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2119679 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• A sample of samplers: a computational perspective on sampling
• An Inequality Arising in Genetical Theory
• An expansion tester for bounded degree graphs
• Clique immersion in graphs without a fixed bipartite graph
• Compactness results in extremal graph theory
• Complete Minors in Graphs Without Sparse Cuts
• Expander graphs and their applications
• Expanders -- how to find them, and what to find in them
• Extremal density for sparse minors and subdivisions
• Finding and using expanders in locally sparse graphs
• Finding long paths and cycles in sparse Hamiltonian graphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Nested cycles with no geometric crossings
• On approximating the longest path in a graph
• On clusterings: good, bad and spectral
• On testing expansion in bounded-degree graphs
• The number of walks in a graph
• Topological Cliques in Graphs

Cited in

(6)

• Cutoff for random lifts of weighted graphs
• Towards the Erdős-Gallai cycle decomposition conjecture
• Crux, space constraints and subdivisions
• Towards the Erdős-Gallai cycle decomposition conjecture
• Finding large expanders in graphs: from topological minors to induced subgraphs
• scientific article; zbMATH DE number 2119679 (Why is no real title available?)

This page was built for publication: Well-mixing vertices and almost expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5039232)