Matchings on infinite graphs

Free entry.

  • Date : 6/12/2010
  • Place : Inria Paris-Rocquencourt, conference room, building 9
  • Guests : Marc Lelarge and Cecilia Holmgren
  • Organisers : ALGORITHMS

• At 10.30 am: Marc Lelarge, TREC project, Inria Paris-Rocquencourt & Ecole Normale Supérieure Paris.

Matchings on infinite graphs

We consider the Boltzmann distribution with positive fugacity over the matchings of a finite graph, and we establish its weak convergence as the underlying graph converges locally to an infinite graph with finite branching number. As a by-product, we obtain convergence of the scaled logarithm of the matching polynomial. By then letting the fugacity tend to infinity, we obtain a limit theorem for the asymptotic size of a maximum matching in the graph sequence. Joint work with Charles Bordenave and Justin Salez.

• At 2.00 pm: Cecilia Holmgren, Algorithms, Inria Paris-Rocquencourt.

The Total Path Length of Split Trees

By using renewal theory we prove convergence in distribution of the total path length, i.e., the sum of all depths, for the entire class of random split trees introduced by Devroye. Many split trees are models of sorting algorithms and data structures and the total path length is a natural cost measure of the sorting algorithm. Split trees include e.g., search trees, m2k+1)-trees, simplex trees, tries and digital search trees.

Keywords: Séminaire ALGORITHMS Paris - Rocquencourt