Many random combinatorial structures have some natural recursive decompositions. Some first examples are provided by models for efficient data structures based on a divide-and-conquer paradigm. I will show how one may obtain precise characterizations of the asymptotics for the cost of search queries using fixed-points arguments.
The same fixed-points arguments also allow to obtain geometric information on the scaling limits of trees arising from geometric partitioning schemes. I will also try to hint at more general results about the behaviour of some fixed-point equations arising from recursive decompositions for metric measure spaces.
This is based on joint work with Henning Sulzbach and Ralph Neininger.
Biography
Nicolas Broutin is a Visiting Associate Professor of Mathematics at NYU Shanghai. He is also a research scientist at Inria Paris-Rocquencourt. He holds a MEng from Ecole Polytechnique (Paris), a PhD from McGill University and an Habilitation from UPMC Paris 6. Professor Broutin’s research interests are probability, random structures and algorithms. His work has appeared for instance in Probability Theory and Related Fields, The Annals of Probability and the Annals of Applied Probability.