Minisymposium: Topologie appliquée et numérique
Letting Loops Loose
Mileyko, Yuriy
University of Illinois at Urbana-Champaign

Problems in applied topology often require computation of an optimal (in some sense) representative among shapes satisfying particular topological constraints. In many cases this is a very challenging, if not infeasible task. The aim of this talk is to show that in some cases the needed optimality is a typical property, meaning that a representative chosen uniformly at random will be close to optimal with an overwhelming probability. In particular, we consider the space of closed polygonal chains which represent a fixed free homotopy class in a (multi-)punctured plane and have a large number of small edges. By employing tools from large deviation theory we show that the uniform measure on this space is sharply concentrated around representatives whose length is arbitrarily close to the length infimum. As a consequence, sampling from the stationary distribution of a Markov process (using, say, the Metropolis-Hastings algorithm) gives us a simple way to approximate the minimal length representative in a free homotopy class. This result has an important application in multi-agent systems, as it allows the agents to move towards the optimal configuration without any control.

Mercredi, 19 juin, 16h30
Salle Du Jardin