A Combinatorial Characterization of Constant Mixing Time
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912739737206784 |
|---|---|
| author | Lau, Lap Chi Liu, Raymond |
| author_facet | Lau, Lap Chi Liu, Raymond |
| contents | Classical spectral graph theory characterizes graphs with logarithmic mixing time. In this work, we present a combinatorial characterization of graphs with constant mixing time. The combinatorial characterization is based on the small-set bipartite density condition, which is weaker than having near-optimal spectral radius and is stronger than having near-optimal small-set vertex expansion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21868 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Combinatorial Characterization of Constant Mixing Time Lau, Lap Chi Liu, Raymond Data Structures and Algorithms Combinatorics Classical spectral graph theory characterizes graphs with logarithmic mixing time. In this work, we present a combinatorial characterization of graphs with constant mixing time. The combinatorial characterization is based on the small-set bipartite density condition, which is weaker than having near-optimal spectral radius and is stronger than having near-optimal small-set vertex expansion. |
| title | A Combinatorial Characterization of Constant Mixing Time |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2511.21868 |