DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.63

Rapid Mixing of the Down-Up Walk on Matchings of a Fixed Size

Authors: Vishesh Jain and Clayton Mizgerd

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

Let G = (V,E) be a graph on n vertices and let m^*(G) denote the size of a maximum matching in G. We show that for any δ > 0 and for any 1 ≤ k ≤ (1-δ)m^*(G), the down-up walk on matchings of size k in G mixes in time polynomial in n. Previously, polynomial mixing was not known even for graphs with maximum degree Δ, and our result makes progress on a conjecture of Jain, Perkins, Sah, and Sawhney [STOC, 2022] that the down-up walk mixes in optimal time O_{Δ,δ}(nlog{n}). In contrast with recent works analyzing mixing of down-up walks in various settings using the spectral independence framework, we bound the spectral gap by constructing and analyzing a suitable multi-commodity flow. In fact, we present constructions demonstrating the limitations of the spectral independence approach in our setting.

Cite as

Vishesh Jain and Clayton Mizgerd. Rapid Mixing of the Down-Up Walk on Matchings of a Fixed Size. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.APPROX/RANDOM.2024.63,
  author =	{Jain, Vishesh and Mizgerd, Clayton},
  title =	{{Rapid Mixing of the Down-Up Walk on Matchings of a Fixed Size}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{63:1--63:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.63},
  URN =		{urn:nbn:de:0030-drops-210563},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.63},
  annote =	{Keywords: Down-up walk, Matchings, MCMC}
}

Search Results

Documents authored by Mizgerd, Clayton

Rapid Mixing of the Down-Up Walk on Matchings of a Fixed Size

Abstract

Cite as

Thanks for your feedback!

Could not send message