Trees play a fundamental role in various areas of mathematics such as combinatorics, graph theory, population genetics, and theoretical computer science. In the first part of this thesis, we consider fires on large random trees. We dfine dynamics where, as time goes by, fires start randomly on a tree and propagate through the neighboring fiammable edges, whereas in the meantime, some edges become fireproof and stop the propagation of subsequent fires. We study the efiect of such dynamics, which is intimately related to the geometry of the underlying tree, and consider two difierent models of trees: Cayley trees and random recursive trees. The techniques used are related to the procedure of cutting-down a tree (in which edges are successively removed from the tree) and fragmentation theory.

In the second part, we use trees (in particular Galton–Watson trees) as tools to study large random non-crossing configurations of the unit disk. Such configurations consist of a graph formed by nonintersecting diagonals of a regular polygon. We consider two variants: first when the connected components of the graph are pairwise disjoint polygons (the configuration is then called a noncrossing partition), and then when this graph is a tree (it is called a non-crossing tree). These objects have been studied from the perspective of combinatorics and probability but in the past, research has focused on the uniform distribution. We generalize the latter using Boltzmann sampling. In both models, we observe a universality phenomenon: all large non-crossing partitions for which the distribution of the size of a typical polygon belongs to the domain of attraction of a stable law resemble the same random object, namely a stable lamination. A similar result holds for non-crossing trees, for which we construct a novel universal limit that we call a stable triangulation.

Marzouk, Cyril. *Random trees, fires and non-crossing partitions.* 2015, University of Zurich, Faculty of Science.

## Abstract

Trees play a fundamental role in various areas of mathematics such as combinatorics, graph theory, population genetics, and theoretical computer science. In the first part of this thesis, we consider fires on large random trees. We dfine dynamics where, as time goes by, fires start randomly on a tree and propagate through the neighboring fiammable edges, whereas in the meantime, some edges become fireproof and stop the propagation of subsequent fires. We study the efiect of such dynamics, which is intimately related to the geometry of the underlying tree, and consider two difierent models of trees: Cayley trees and random recursive trees. The techniques used are related to the procedure of cutting-down a tree (in which edges are successively removed from the tree) and fragmentation theory.

In the second part, we use trees (in particular Galton–Watson trees) as tools to study large random non-crossing configurations of the unit disk. Such configurations consist of a graph formed by nonintersecting diagonals of a regular polygon. We consider two variants: first when the connected components of the graph are pairwise disjoint polygons (the configuration is then called a noncrossing partition), and then when this graph is a tree (it is called a non-crossing tree). These objects have been studied from the perspective of combinatorics and probability but in the past, research has focused on the uniform distribution. We generalize the latter using Boltzmann sampling. In both models, we observe a universality phenomenon: all large non-crossing partitions for which the distribution of the size of a typical polygon belongs to the domain of attraction of a stable law resemble the same random object, namely a stable lamination. A similar result holds for non-crossing trees, for which we construct a novel universal limit that we call a stable triangulation.

## Downloads

0 downloads since 12 months

## Additional indexing

Item Type: | Dissertation |
---|---|

Referees: | Bertoin Jean, Curien Nicola, Duquesne Thoma, Féray Valentin, Kortchemsk. Igor, Nikeghbali Ashkan |

Communities & Collections: | 07 Faculty of Science > Institute of Mathematics |

Dewey Decimal Classification: | 510 Mathematics |

Language: | English |

Date: | 2015 |

Deposited On: | 28 Jan 2016 11:07 |

Last Modified: | 22 Sep 2016 11:36 |

Number of Pages: | 160 |

Official URL: | http://www.recherche-portal.ch/ZAD:default_scope:ebi01_prod010580324 |

## Download

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.

You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.