TAILIEUCHUNG - Báo cáo toán học: "Airy Phenomena and Analytic Combinatorics of Connected Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Airy Phenomena and Analytic Combinatorics of Connected Graphs. | Airy Phenomena and Analytic Combinatorics of Connected Graphs Philippe Flajolet Algorithms Project INRIA Rocquencourt 78153 Le Chesnay France . . Bruno Salvy Algorithms Project INRIA Rocquencourt 78153 Le Chesnay France . . Gilles Schaeffer LIX - CNRS École polytechnique 91128 Palaiseau France . Submitted Oct 11 2002 Mar 12 2004 Accepted Apr 7 2004 Published May 27 2004. MR Subject Classifications 05A15 05A16 05C30 05C40 05C80 Abstract Until now the enumeration of connected graphs has been dealt with by probabilistic methods by special combinatorial decompositions or by somewhat indirect formal series manipulations. We show here that it is possible to make analytic sense of the divergent series that expresses the generating function of connected graphs. As a consequence it becomes possible to derive analytically known enumeration results using only first principles of combinatorial analysis and straight asymptotic analysis specifically the saddle-point method. In this perspective the enumeration of connected graphs by excess of number of edges over number of vertices derives from a simple saddle-point analysis. Furthermore a refined analysis based on coalescent saddle points yields complete asymptotic expansions for the number of graphs of fixed excess through an explicit connection with Airy functions. Introduction E. M. Wright of Hardy and Wright fame initiated the enumeration of labelled connected graphs by number of vertices and edges in a well-known series of articles 34 35 36 . In particular he discovered that the generating functions of graphs with a fixed excess of number of edges over number of vertices has a rational expression in terms of the tree function T z . Wright s approach is based on the fact that deletion of an edge in a THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R34 1 connected graph leads to either one or two connected graphs with smaller excess. This .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.