Properties of random triangulations and trees

Let T-n denote the set of triangulations of a convex polygon K with n sides . We study functions that measure very natural "geometric" features of a tr iangulation tau is an element of T-n, for trample, Delta(n)(tau) which coun ts the maximal number of diagonals in tau incident to a single vertex of K. It is familiar that T-n is bijectively equivalent to B-n, the set of roote d binary trees with n - 2 internal nodes, and also to P-n, the set of nonne gative lattice paths that start at 0, make 2n - 4 steps X-i of size +/-1, a nd end at X-1 +...+ X2n-4 = 0 Delta(n) and the other functions translate in to interesting properties of trees in B-n, and paths in P-n, that seem not to have been studied before. We treat these functions as random variables u nder the uniform probability on T-n and can describe their behavior quite p recisely. A main result is that Delta(n) is very close to log n tall logs a re base 2). Finally we describe efficient algorithms to generate triangulat ions in T-n uniformly, and in certain interesting subsets.