Résumé : In recent years there has been increasing interest in the asymptotic analysis of (several classes of) planar maps and planar graphs. This was initiated by bijective methods (e.g. the Shaeffer bijection), generating function methods (e.g. Gimenez and Noy's result on the asymptotics of number of planar graphs) and the search for probabilistic limiting objects (e.g. the Brownian map by Le Gall). In particular in the discussion of several planar graph classes (like series-parallel graphs or labelled planar graphs) a dichotomy between a "critical" and "subcritical" behaviour between 2-connected and connected graphs was observed. Informally a graph class is subcritical when all 2-connected components are small (i.e., at most of log n - size) and one observes a "treelike structure". Conversely a graph class is critical when the largest 2-connected component is comparable to the size of the whole graph. The purpose of this talk is to discuss the asymptotic behaviour of several (extremal) parameters of subcritical and critical graph classes, in particular the diameter and the maximum degree. For subcritical graph classes the diameter is (usually) of oder n^(1/2) whereas we can expect the order n^(1/4) in the critial case. On the other hand the maximum degree is (usually) of order log n in both cases. However, critical graph classes are notoriously more difficult to handle than subcritical ones. This talk is mainly based on joint work with Omer Gimenez, Marc Noy, Konstantinos Panagiotou, and Angelika Steger.
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |