Enumeration of Geometric Configurations on a Convex Polygon

Marc Noy

Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya

Algorithms Seminar

December 16, 1999

[summary by Michel Nguyen-The]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
We survey recent work on the enumeration of non-crossing configurations on the set of vertices of a convex polygon, such as triangulations, trees, and forests. Exact formulæ and limit laws are determined for several parameters of interest. In the second part of the talk we present results on the enumeration of chord diagrams (pairings of 2n vertices of a convex polygon by means of n disjoint pairs). We present limit laws for the number of components, the size of the largest component and the number of crossings. The use of generating functions and of a variation of Levy's continuity theorem for characteristic functions enable us to establish that most of the limit laws presented here are Gaussian. (Joint work by Marc Noy with Philippe Flajolet and others.)



1   Analytic Combinatorics of Non-crossing Configurations [3]

1.1   Connected graphs and general graphs

Let Pn={v1,...,vn} be a fixed set of points in the plane, conventionally ordered counter-clockwise, that are vertices of a regular n-gon K. Define a non-crossing graph as a graph with vertex set Pn whose edges are straight line segments that do not cross. A graph is connected if any two vertices can be joined by a path. Parameters of interest are the number of edges of connected graphs and general graphs, and the number of components of general graphs.

-7pt

Figure 1: (a) A connected non-crossing graph; (b) an arbitrary non-crossing graph.

1.2   Trees and forests

A (general) tree is a connected acyclic graph and the number of edges in a tree is one less than the number of vertices. The study of trees becomes easier with the introduction of butterflies [3], defined to be ordered pairs of trees with a common vertex; a tree appears to be a sequence of butterflies attached to a root. A forest is an acyclic graph, in other words a graph whose components are trees.


Figure 2: (a) A tree; (b) a forest.

1.3   Triangulations

A triangulation [7] is a set  Tn of n-3 non-crossing diagonals vivj which partitions K into n-2 triangles. As each triangle corresponds to an internal node of a binary tree (see the generating function of exercise 7.22 of [6]) via a classical bijection due to Euler [11], the number T^n of triangulations is given by the (n-2)-th Catalan number T^n=Cn-2=(
2n-4
n-2
)/(n-1). Let di denote the degree of the vertex vi (i.e., the number of diagonals incident with vi) and ||vivj||=min(|i-j|,n-|i-j|) the length of a diagonal vivj. Define [2]:
Dn(t)=max  {  di|i=0,...,n-1  } ,
the maximal degree of the vertices, and
ln(t)=max  {  ||vivj|||vivjÎ Tn  } ,
the length of the longest diagonal in the triangulation.

Those features are of interest for a triangulation t because they convey information about the corresponding tree b(t): Dn(t) measures the external-node separation of b(t), i.e., the maximal distance between successive external nodes; ln(t) measures its nearly half measure, i.e., the size of the largest subtree with not more than half the external nodes.

Using combinatorial bijections and probability lemmas [2], we find:
E[Dn]~log2n, and E[ln]~a n,   where   a=
(3)1/2
p
+
1
3
-
log ( 2+(3)1/2  )
p
~0.4654.

Let an ear of a triangulation t be a triangle sharing two sides with the polygon, and en the number of ears of a triangulation. Let us view triangulations as binary trees and ears as leaves (internal node whose children are external nodes [11]) or roots with at least one child that is an external node, and let B^ enumerate binary trees by size and number of leaves and T^ enumerate triangulations by size and number of ears.1 These generating series satisfy [5]
z2
^
T
 
(z,w)= ( 1+2z(w-1) )
^
B
 
(z,w),   where   
^
B
 
(z,w)=z æ
ç
ç
è		 w+2
^
B
 
(z,w)+
^
B
 
(z,w)2 ö
÷
÷
ø		 ,
leading to Var[en]~(n)1/2/4 and a Gaussian limit law (see §1.5 below). The expectation
E[en]=
n(n-1)
2(2n-5)
~
n
4
was already known from a combinatorial manipulation of Catalan numbers described in [7].

1.4   Generating functions

The combinatorial objects and parameters above, except for extremal ones, lead to univariate and bivariate generating functions, given in Table 1 below.

Configuration Generating function equation
Connected graphs C3+C2-3zC+2z2=0
-----, edges wC3+wC2-(1+2w)zC+(1+w)z2=0
Graphs G2+(2z2-3z-2)G+3z+1=0
-----, edges wG2+((1+w)z2-(1+2w)z-2w)G+w+(1+2w)z=0
-----, components G3+(2w3z2-3w2z+w-3)G2+(3w2z-2w+3)G+w-1=0
Trees T3-zT+z2=0
-----, leaves T3+(z2w-z2-z)T+z2=0
Forests F3+(z2-z-3)F2+(z+3)F-1=0
-----, components F3+(w3z2-w2z-3)F2+(w3z+3)F-1=0
Triangulations z4T^2+(2z2-z)T^+1=0
-----, ears z4T^2+(1+2z(w-1))(2z2-z) T^+w(1+2z(w-1))2=0
-1.5pt

Table 1: Generating function equations (z and w mark vertices and the secondary parameter).

A few tricks enable one to make Lagrange inversion applicable and to derive exact formulæ---sometimes involving summations---for all coefficients. For example, the change of variable T=z+zy followed by Lagrange's formula yields:
Tn=
1
2n-1
æ
è
3n-3
n-1
ö
ø
  and   Tn,k=
1
n-1
æ
è
n-1
k
ö
ø
k-1
å
j=0
æ
è
n-1
j
ö
ø
æ
è
n-k-1
k-1-j
ö
ø
2n-2k+j.
Finding Cn,k goes through a parameterization of the functional equation of C. To get the coefficients T^, we use the equality T^n,k=B^n+2,k-1+2B^n+1,k -2B^n+1,k deduced from z2T^(z,w)=(1+2z(w-1))B^(z,w).

1.5   Asymptotics

All of the univariate generating functions above, and a few others (dissections and partitions of convex polygons) not presented in the talk but available in [3], have a unique dominant singularity r in (0,1), and can be written
f(z)=c0+c1 æ
ç
ç
è		 1-
z
r
ö
÷
÷
ø
1/2



 
+O æ
ç
ç
è		 1-
z
r
ö
÷
÷
ø		 ,   entailing   [zn]f(z)=
c1
G(-1/2)
æ
ç
ç
è		 1+O æ
ç
ç
è
1
n
ö
÷
÷
ø		 ö
÷
÷
ø		 .

For example the numbers Tn and Fn of respectively general trees and forests satisfy
Tn~(27/4)n=6.75n  and   Fn~8.2246n,   whence   Tn=o(Fn).
The numbers Cn and Gn of respectively connected and general graphs satisfy
Cn~ æ
ç
ç
è
(6)1/2
9
-
(2)1/2
6
ö
÷
÷
ø		 ~10.39n   and   Gn~
1
4
(99(2)1/2-140)1/2×
2n(3+2+(2)1/2)n
(p)1/2n3/2
~11.65n,
entailing Cn/Gn®0 when n®¥.

The bivariate generating function seen before admits the form
f(z,w)=c0(w)+c1(w) æ
ç
ç
è		 1-
z
r(w)
ö
÷
÷
ø
1/2



 
+O æ
ç
ç
è		 1-
z
r(w)
ö
÷
÷
ø		 ;
this leads to
fn(w)=g(w) æ
ç
ç
è
1
r(w)
ö
÷
÷
ø
n



 
æ
ç
ç
è		 1+O æ
ç
ç
è
1
(n)1/2
ö
÷
÷
ø		 ö
÷
÷
ø		 , or
fn(w)
fn(1)
=
g(w)
g(1)
æ
ç
ç
è
r(1)
r(w)
ö
÷
÷
ø
n



 
æ
ç
ç
è		 1+O æ
ç
ç
è
1
(n)1/2
ö
÷
÷
ø		 ö
÷
÷
ø		 .
From the Quasi-Powers theorem [5, 8], which is a consequence of Levy's continuity theorem for characteristic functions, one deduces that fn is asymptotically normal. The mean µn and variance sn satisfy µn~k n and sn2~l n for algebraic numbers k and l.

For instance, for the distribution of the number of edges in the space of connected graphs of given size, we have k=(1+(3)1/2)/2~1.366.

2   Analytics Combinatorics of Chord Diagrams [4]

2.1   Definitions

Take 2n points on a circle, labelled 1, 2, ..., 2n, and join them in disjoint pairs by n chords. The resulting configuration is called a chord diagram. A diagram is connected if no set of chords can be separated from the remaining chords by a line. A component is a maximal connected subdiagram.

2.2   Components

2.2.1   Number of components

Let C(z)=ån³0Cnzn be the generating function of connected diagrams of size n. The bivariate generating function I(z,w)=ån,k³0In,kwkzn of diagrams of size n and k components satisfies I(z,w)=1+wC(zI(z,w)2).

We have the following result:
Theorem 1   Let Xn be the number of components in a random diagram of size n.
  1. For k³1, one has P[Xn=k]= e-1/(k-1)!(1+o(1)),    n®¥.

  2. The mean µn and the variance sn of the distribution satisfy µn~2 and sn2~1 as n®¥.

Proof.[Sketch of proof] The proof of the first point makes use of ``monoliths,'' or ``monolithic diagrams,'' where a diagram is said to be monolithic if: (i) it consists solely of the connected component that contains 1 (called the root component) and of isolated edges; (ii) for any two such isolated edges (a,b) and (c,d), one never has a<c<d<b or c<a<b<d (in other words, two isolated chords are never in a dominance relation).

The ordinary generating function of monoliths reads M(z)=C(z/(1-z)2), and according to Stein and Everett [12] Cn/In=e-1+o(1), so one can deduce the relation Mn~ In, i.e., that almost every diagram is a monolith. The number Mn,k of monoliths of size n with k components is given by
Mn,k=
æ
è
2n-k
k-1
ö
ø
Cn-k+1~
e-1
(k-1)!
In.

As to the second point, using 2zC(z)C'(z)=C(z)2+C(z)-z, which is deduced from
Cn=(n-1)
n-1
å
j=1
CjCn-j
and C1=1 [9, 13], one finds
µn=
I
w
(z,w) ½
½
½
½
 



w=1
=
1
z
( I(z)+h(z)-2 ) ,  where   h(z)=I(z)-1.

Hence, letting gn=hn/In, one obtains
gn=1-
n-1
å
k=1
gk
æ
è
n
k
ö
ø
æ
è
2n
2k
ö
ø
-1 =1-
1
n
+
3
4n2
+O(n-3),
and µn=In+1+hn+1/In=2n+1/n+1+O(n-1)~2. Similar computations yield the variance.


2.2.2   Largest connected component

Theorem 2   Let Ln be the size of the largest connected component in a random diagram of size n. Then, as n®¥, the mean µn and the variance sn of the distribution of Ln are
E[Ln]=n-1+o(1),    Var[Ln]=1+o(1),
and for any fixed k³1, one has P[n-Ln=k]=e-1/k!(1+o(1)). In other words, thre random variable n-Ln follows a Poisson law of parameter 1.

The proof relies on the analysis of the largest component in a monolith, namely, the root component with probability 1-o(1), the other components being only edges. The number Mn,k of monoliths of size n with root component of size n-k is given by:
Mn,k=
æ
è
2n-k-1
k
ö
ø
Cn-k~
e-1
(k-1)!
In,    n®¥.

2.3   Crossings

Let k denote the number of chord crossings in a chord diagram, and let In be the set of all diagrams of size n. Flajolet and Noy proved the following result:
Theorem 3   Let Xn be the random variable equal to the value of k taken over the set of chord diagrams In of size n endowed with the uniform probability distribution.

  1. The mean µn and the variance sn of the distribution of Xn are given by
    µn=E[Xn]=
    n(n-1)
    6
    		  and   sn2=Var[Xn]=
    n(n-1)(n+3)
    45
    		,   respectively.

  2. The distribution of Xn is Gaussian in the asymptotic limit: for all real x, one has
     
    lim
    n®¥
    		P é
    ê
    ê
    ë
    Xn-µn
    sn
    		£ x ù
    ú
    ú
    û    		 =
    1
    (2p)1/2
    		ó
    õ
    x


    -¥
    		e
    -y2
    [3]
    Flajolet (Philippe) and Noy (Marc). -- Analytic combinatorics of non-crossing configurations. Discrete Mathematics, vol. 204, n°1-3, 1999, pp. 203--229.

    [4]
    Flajolet (Philippe) and Noy (Marc). -- Analytic combinatorics of chord diagrams. In Krob (D.), Mikhalev (A. A.), and Mikhalev (A. V.) (editors), Formal Power Series and Algebraic Combinatorics. pp. 191--201. -- Springer Verlag, 2000. Proceedings of FPSAC'2000, June 2000, Moscow.

    [5]
    Flajolet (Philippe) and Sedgewick (Robert). -- The average case analysis of algorithms: multivariate asymptotics and limit distributions. -- Research Report n°3162, Institut National de Recherche en Informatique et en Automatique, 1997. 123 pages.

    [6]
    Graham (Ronald L.), Knuth (Donald E.), and Patashnik (Oren). -- Concrete mathematics. -- Addison-Wesley Publishing Co., Reading, MA, 1989, xiv+625p. A foundation for computer science.

    [7]
    Hurtado (F.) and Noy (M.). -- Ears of triangulations and Catalan numbers. Discrete Mathematics, vol. 149, n°1-3, 1996, pp. 319--324.

    [8]
    Hwang (Hsien-Kuei). -- Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques. -- Thèse de doctorat, École polytechnique, December 1994.

    [9]
    Nijenhuis (Albert) and Wilf (Herbert S.). -- The enumeration of connected graphs and linked diagrams. Journal of Combinatorial Theory. Series A, vol. 27, n°3, 1979, pp. 356--359.

    [10]
    Riordan (John). -- The distribution of crossings of chords joining pairs of 2n points on a circle. Mathematics of Computation, vol. 29, 1975, pp. 215--222. -- Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday.

    [11]
    Sedgewick (Robert) and Flajolet (Philippe). -- An introduction to the analysis of algorithms. -- Addison-Wesley Publishing Co., Reading, MA, 1996.

    [12]
    Stein (P. R.) and Everett (C. J.). -- On a class of linked diagrams. II. Asymptotics. Discrete Mathematics, vol. 21, n°3, 1978, pp. 309--318.

    [13]
    Stein (Paul R.). -- On a class of linked diagrams. I. Enumeration. Journal of Combinatorial Theory. Series A, vol. 24, n°3, 1978, pp. 357--366.

    [14]
    Touchard (Jacques). -- Sur un problème de configurations et sur les fractions continues. Canadian Journal of Mathematics, vol. 4, 1952, pp. 2--25.
    1
    The expression of T^, entailing the Gaussian limit of the distribution of ears of triangulations, was established by the author of this summary.
    This document was translated from LATEX by HEVEA.