In this tutorial we will review an influential phenomenon concerning random structures that can be stated in balls-into-bins terminology.
Assume there are n balls and m bins and we wish to place each ball into a bin chosen at random. By the birthday paradox we have to expect a collision of two balls in the same bin as soon as n = Ω(√m). If, however, we generate 3 candidate bins for each ball, then as long as n < 0.81m it is with high probability possible to place each ball into a candidate bin without any collisions. Such a placement can even be computed by the so-called peeling algorithm that keeps greedily looking for a bin that is a candidate for only one unplaced ball.
This result and its generalisations can be stated in several languages and have wide applications. In graph terminology it is related to the emergence of cores in Erdős-Reyni graphs (and related graphs), in coding theory to fast decoding of LDPC codes, and in data structure theory to cuckoo hash tables as well as data structures for retrieval and approximate membership. We will see a (more or less) complete proof, which will take us to a few interesting places along the way. For instance, we will study the properties of certain random infinite trees, which are, perhaps surprisingly, much easier to understand than random finite graphs.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne