Random k-noncrossing partitions

MaRDI QIDQ6216342zbMATH OpenFDO

Authors Jing Qin, Christian M. Reidys

Publication date 16 November 2009

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: In this paper, we introduce polynomial time algorithms that generate random $k$-noncrossing partitions and 2-regular, $k$-noncrossing partitions with uniform probability. A $k$-noncrossing partition does not contain any $k$ mutually crossing arcs in its canonical representation and is 2-regular if the latter does not contain arcs of the form $(i,i+1)$. Using a bijection of Chen {it et al.} cite{Chen,Reidys:08tan}, we interpret $k$-noncrossing partitions and 2-regular, $k$-noncrossing partitions as restricted generalized vacillating tableaux. Furthermore, we interpret the tableaux as sampling paths of a Markov-processes over shapes and derive their transition probabilities.

This page was built for publication: Random $k$-noncrossing partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6216342)