tailieunhanh - Báo cáo toán học: "A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components. | A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components Guillaume Chapuy1 Eric Fusy2 Mihyun Kang3 and Bilyana Shoilekova4 Submitted Sep 17 2008 Accepted Nov 30 2008 Published Dec 9 2008 Mathematics Subject Classihcation 05A15 Abstract Tutte has described in the book Connectivity in graphs a canonical decomposition of any graph into 3-connected components. In this article we translate using the language of symbolic combinatorics Tutte s decomposition into a general grammar expressing any family G of graphs with some stability conditions in terms of the subfamily G3 of graphs in G that are 3-connected until now such a general grammar was only known for the decomposition into 2-connected components . As a byproduct our grammar yields an explicit system of equations to express the series counting a labelled family of graphs in terms of the series counting the subfamily of 3-connected graphs. A key ingredient we use is an extension of the so-called dissymmetry theorem which yields negative signs in the grammar and associated equation system but has the considerable advantage of avoiding the difficult integration steps that appear with other approaches in particular in recent work by Gimenez and Noy on counting planar graphs. As a main application we recover in a purely combinatorial way the analytic expression found by Gimenez and Noy for the series counting labelled planar graphs such an expression is crucial to do asymptotic enumeration and to obtain limit laws of various parameters on random planar graphs . Besides the grammar an important ingredient of our method is a recent bijective construction of planar maps by Bouttier Di Francesco and Guitter. Finally our grammar applies also to the case of unlabelled structures since the dissymetry theorem takes symmetries into account. Even if there are still difficulties in counting unlabelled 3-connected planar graphs we think that our grammar is a promising tool toward the asymptotic enumeration