Minimum weight disk triangulations and fillings

homotopical filling of the cycle \((123)\)minimum total weight of a disk triangulation minimum weights of a homological filling of the cycle \((123)\)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of simplicial complexes (05E45) 2-dimensional topology (including mapping class groups of surfaces, Teichmüller theory, curve complexes, etc.) (57K20) Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05)

Abstract: We study the minimum total weight of a disk triangulation using vertices out of

1, l d o t s, n

, where the boundary is the triangle

(123)

and the

triangles have independent weights, e.g.

m a t h r m E x p (1)

or

m a t h r m U (0, 1)

. We show that for explicit constants

c_{1}, c_{2} > 0

, this minimum is

c_{1} f r a c l o g n s q r t n + c_{2} f r a c l o g l o g n s q r t n + f r a c Y_{n} s q r t n

where the random variable

Y_{n}

is tight, and it is attained by a triangulation that consists of

f r a c 14 l o g n + O_{P} (s q r t l o g n)

vertices. Moreover, for disk triangulations that are canonical, in that no inner triangle contains all but

O (1)

of the vertices, the minimum weight has the above form with the law of

Y_{n}

converging weakly to a shifted~Gumbel. In addition, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle

(123)

are both attained by the minimum weight disk triangulation.

Recommendations

Cites work

Cited in

(1)

Typical values of extremal-weight combinatorial structures with independent symmetric weights

This page was built for publication: Minimum weight disk triangulations and fillings

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