Zusammenfassung für den Vortrag am 30.10.2009 (16:00 Uhr)

Jing Qin (Nankai University, China, & IZBI, Universität Leipzig)

Random 3-noncrossing partitions generation

In this paper, we introduce polynomial time algorithms that generate random 3-noncrossing partitions and 2-regular, 3-noncrossing partitions with uniform probability. A 3-noncrossing partition does not contain any three 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 et al. [PNAS, 2009, to appear], we interpret 3-noncrossing partitions and 2-regular, 3-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.