Well-mixing vertices and almost expanders

DOI10.1090/PROC/16090zbMATH Open1498.05247arXiv2108.12864OpenAlexW4312734416MaRDI QIDQ5039232FDOQ5039232

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

Publication date: 12 October 2022

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

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).

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

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

zbMATH Keywords

random walks

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Expander graphs and their applications
• Title not available (Why is that?)
• On approximating the longest path in a graph
• A Separator Theorem for Planar Graphs
• On clusterings
• Compactness results in extremal graph theory
• A Sample of Samplers: A Computational Perspective on Sampling
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The number of walks in a graph
• An Inequality Arising in Genetical Theory
• On Testing Expansion in Bounded-Degree Graphs
• An Expansion Tester for Bounded Degree Graphs
• Title not available (Why is that?)
• Topological Cliques in Graphs
• Finding long paths and cycles in sparse Hamiltonian graphs
• Title not available (Why is that?)
• Extremal density for sparse minors and subdivisions
• Proof of Komlós's conjecture on Hamiltonian subsets
• A proof of Mader's conjecture on large clique subdivisions in C4-free graphs
• Finding and Using Expanders in Locally Sparse Graphs
• Expanders – how to find them, and what to find in them
• Clique immersion in graphs without a fixed bipartite graph
• Nested cycles with no geometric crossings
• Complete Minors in Graphs Without Sparse Cuts

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
• Title not available (Why is that?)

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)