{"ID":2836592,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.21868","arxiv_id":"2511.21868","title":"A Combinatorial Characterization of Constant Mixing Time","abstract":"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.","short_abstract":"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 ra...","url_abs":"https://arxiv.org/abs/2511.21868","url_pdf":"https://arxiv.org/pdf/2511.21868v2","authors":"[\"Lap Chi Lau\",\"Raymond Liu\"]","published":"2025-11-26T19:49:28Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}