On properties of random dissections and triangulations

ABSTRACT

In the past decades the G_n,p model of random graphs, introduced by Erdős and Rényi in the 60's, has led to numerous beautiful and deep theorems. A key feature that is used in basically all proofs is that edges in G_n,p appear independently. The independence of the edges allows, for example, to obtain extremely tight bounds on the number of edges of G_n,p and its degree sequence by straightforward applications of Chernoff bounds. This situation changes dramatically if one considers graph classes with structural side constraints. For example, in a random planar graph R_n (a graph drawn uniformly at random from the class of all labeled planar graphs on n vertices) the edges are obviously far from being independent. Consequently, so far basically all results about properties of random graphs with structural side constraints rely on completely different methods, mostly from analytic combinatorics.

In this paper we show that recent progress in the construction of so-called Boltzmann samplers by Duchon, Flajolet, Louchard, and Schaeffer [3] and Fusy [6] can be used to reduce the study of degree sequences and subgraph counts to properties of sequences of independent and identically distributed random variables -- to which we can then again apply Chernoff bounds to obtain extremely tight results.

We elaborate our ideas by studying random dissections and triangulations of a labeled convex n-gon. For both we obtain the degree sequence and the number of induced copies of given fixed graphs. The degree sequence for triangulations was already obtained previously by Gao and Wormald [8] using deep methods from analytic combinatorics. We do, however, get better bounds for the tails of the probability distribution.

REFERENCES

• 1: Nicla Bernasconi , Konstantinos Panagiotou , Angelika Steger, On properties of random dissections and triangulations, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 20-22, 2008, San Francisco, California
• 2: L. Comtet. Advanced combinatorics: The Art of Finite and Infinite Expansions. D. Reidel Publishing Co., Dordrecht, enlarged edition, 1974.
• 3: Philippe Duchon , Philippe Flajolet , Guy Louchard , Gilles Schaeffer, Boltzmann Samplers for the Random Generation of Combinatorial Structures, Combinatorics, Probability and Computing, v.13 n.4-5, p.577-625, July 2004 [doi>10.1017/S0963548304006315]
• 4: Philippe Flajolet , Marc Noy, Analytic combinatorics of non-crossing configurations, Discrete Mathematics, v.204 n.1-3, p.203-229, June 6, 1999 [doi>10.1016/S0012-365X(98)00372-0]
• 5: P. Flajolet and R. Sedgewick. Analytic combinatorics. Book in preparation, October, 2005.
• 6: É. Fusy. Quadratic exact size and linear approximate size random generation of planar graphs. In Conrado Martnez, editor, 2005 International Conference on Analysis of Algorithms, volume AD of DMTCS Proceedings, pages 125--138. Discrete Mathematics and Theoretical Computer Science, 2005.
• 7: Zhicheng Gao , Nicholas C. Wormald, The distribution of the maximum vertex degree in random planar maps, Journal of Combinatorial Theory Series A, v.89 n.2, p.201-230, Feb. 2000 [doi>10.1006/jcta.1999.3006]
• 8: Z. Gao and N. C. Wormald. Sharp concentration of the number of submaps in random planar triangulations. Combinatorica, 23(3):467--486, 2003.
• 9: Z. Gao and N. C. Wormald. Asymptotic normality determined by high moments, and submap counts of random maps. Probab. Theory Related Fields, 130(3):368--376, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Design, Theory