On the uniform generation of modular diagrams

Abstract: In this paper we present an algorithm that generates

k

-noncrossing,

s i g m a

-modular diagrams with uniform probability. A diagram is a labeled graph of degree

l e 1

over

n

vertices drawn in a horizontal line with arcs

(i, j)

in the upper half-plane. A

k

-crossing in a diagram is a set of

k

distinct arcs

(i_{1}, j_{1}), (i_{2}, j_{2}), l d o t s, (i_{k}, j_{k})

with the property

i_{1} < i_{2} < l d o t s < i_{k} < j_{1} < j_{2} < l d o t s < j_{k}

. A diagram without any

k

-crossings is called a

k

-noncrossing diagram and a stack of length

s i g m a

is a maximal sequence

((i, j), (i + 1, j - 1), d o t s, (i + (s i g m a - 1), j - (s i g m a - 1)))

. A diagram is

s i g m a

-modular if any arc is contained in a stack of length at least

s i g m a

. Our algorithm generates after

O (n^{k})

preprocessing time,

k

-noncrossing,

s i g m a

-modular diagrams in

O (n)

time and space complexity.

Full work available at URL: https://arxiv.org/abs/1006.2881

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cited In (4)

This page was built for publication: On the uniform generation of modular diagrams