Tesis doctoral de Juan Jose Rue Perna
This thesis deals with the enumerative combinatorics of graphs defined by minor conditions, and of maps on surfaces. More concretely, we are interested in the enumeration (either exact or asymptotic) of different kind of families of graphs and maps, and also in getting precise limit laws for distinct parameters which arise in a natural way from these families. The fundamental tools used in all this work are the symbol ic method in order to deal with generating functions (using the language developed by philippe flajolet) and the singularity analysis over these objects. Analytical tools in singularity analysis let us obtain asymptotic estimates and limit laws for associated parameters . the dissertation is divided into 5 chapters. In chapter 1, basic concepts and definitions are stated, as well as additional concept s which wil l be necessary in the rest of the dissertation. in chapter 2 a general framework is presented, in which we get the enumeration of families of graphs defined by their 3-connected components. This theory explains the enumeration of planar graphs, of series-parallel graphs and of k_{3,3} graphs, among other families. The key point consists in exploiting the seminal ideas of william tutte in order to decompose maps into 3-connected components. We also study distinct limit laws, as the number of edges and the number of blocks. In all these cases, we get normal limit laws. We are able to study two important extremal parameters, the size of the 2-connected core and the size of the 3- connected core. The analysis gives rise to probability distributions which are related to the map airy law (introduced by banderier, phlajolet, schaeffer and soria), which is intimately related to stable laws with parameter 3/2. At the end, we find families of graphs with a critical phenomena not observed before, which depends on the choice in the family of the density of edges. in chapter 3 we study the enumeration of maps defined over the mí¶bius band, with the restriction that all vertices belong to the boundary . With this hypothesis, we get the exact enumeration of simplicial decompositions of the mí¶bius band, a result obtained before by edelman and reiner . The method we develop allows us to study families of maps where the degree of each face is constant, with the condition that the intersection of each pair of distinct faces is a simplex of dimension d<3. We get limit laws for associated parameters, which complement parcial results obtained by gao. In chapter 4, a similar study is done over the cylinder . We only consider vertices belonging to the boundary of the surface. We get the exact enumeration for simplicial decomposi tions of the cylinder, and the enumeration for dissections into k-agons. We remark that the arguments used here are qualitatively different from the ones used in the previous chapter . Using the method of moments (jointly with the laplace transform) we deduce non-standard limit laws for distinct parameteres associated to these families of maps. in chapter 5 we extend the previous results to compact and closed surfaces with boundary and arbitrary genus. Our method (which is based in exploiting the structure of the associated dual maps) allows us to get asymptotic estimates for maps where vertices belong to the boundary of the surface, and the degrees of the faces belong to a fixed subset of the non- negative integers. We also extend limit laws over arbitrary surfaces using the method of moments.
Datos académicos de la tesis doctoral «Enumeration and limit laws of topological graphs«
- Título de la tesis: Enumeration and limit laws of topological graphs
- Autor: Juan Jose Rue Perna
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 18/09/2009
Dirección y tribunal
- Director de la tesis
- Marcos Noy Serrano
- Tribunal
- Presidente del tribunal: Miguel ángel Fiol mora
- Francisco Javier Cilleruelo mateo (vocal)
- (vocal)
- (vocal)