Rapid mixing of the flip chain over non-crossing spanning trees

Konrad Anand; Weiming Feng; Graham Freifeld; Heng Guo; Mark Jerrum; Jiaheng Wang

doi:10.48550/arXiv.2409.07892

Rapid mixing of the flip chain over non-crossing spanning trees

Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, Mark Jerrum, Jiaheng Wang

Research output: Working paper › Preprint

Abstract

We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n8logn).

Original language	English
Publisher	ArXiv
Pages	1-19
Number of pages	19
DOIs	https://doi.org/10.48550/arXiv.2409.07892
Publication status	Published - 12 Sept 2024

Keywords / Materials (for Non-textual outputs)

probability
computational geometry
discrete mathematics
combinatorics

Access to Document

10.48550/arXiv.2409.07892

AnandEtalArXiv2024RapidMixingOfTheFlipChainSubmitted manuscript, 704 KB

NACS - New Approaches to Counting and Sampling
Guo, H. (Principal Investigator)
European Commission
1/01/21 → 30/06/26
Project: Research

Cite this

@techreport{b8fde76bb93340ca8c14a574bd102d4e,

title = "Rapid mixing of the flip chain over non-crossing spanning trees",

abstract = "We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n8logn).",

keywords = "probability, computational geometry, discrete mathematics, combinatorics",

author = "Konrad Anand and Weiming Feng and Graham Freifeld and Heng Guo and Mark Jerrum and Jiaheng Wang",

year = "2024",

month = sep,

day = "12",

doi = "10.48550/arXiv.2409.07892",

language = "English",

pages = "1--19",

publisher = "ArXiv",

type = "WorkingPaper",

institution = "ArXiv",

}

TY - UNPB

T1 - Rapid mixing of the flip chain over non-crossing spanning trees

AU - Anand, Konrad

AU - Feng, Weiming

AU - Freifeld, Graham

AU - Guo, Heng

AU - Jerrum, Mark

AU - Wang, Jiaheng

PY - 2024/9/12

Y1 - 2024/9/12

N2 - We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n8logn).

AB - We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n8logn).

KW - probability

KW - computational geometry

KW - discrete mathematics

KW - combinatorics

U2 - 10.48550/arXiv.2409.07892

DO - 10.48550/arXiv.2409.07892

M3 - Preprint

SP - 1

EP - 19

BT - Rapid mixing of the flip chain over non-crossing spanning trees

PB - ArXiv

ER -

Rapid mixing of the flip chain over non-crossing spanning trees

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

NACS - New Approaches to Counting and Sampling

Cite this