Premium
Large deviations and moments for the Euler characteristic of a random surface
Author(s) -
Fleming Kevin,
Pippenger Nicholas
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20331
Subject(s) - permutation (music) , mathematics , struct , random permutation , distribution (mathematics) , surface (topology) , combinatorics , euler's formula , euler characteristic , moment (physics) , geometry , mathematical analysis , physics , symmetric group , computer science , quantum mechanics , acoustics , programming language
We study random surfaces constructed by glueing together N / k filled k ‐gons along their edges, with all ( N − 1)!! = ( N − 1)( N − 3)···3 · 1 pairings of the edges being equally likely. (We assume that lcm{2, k } divides N .) The Euler characteristic of the resulting surface is related to the number of cycles in a certain random permutation of {1,…, N }. Gamburd has shown that when 2 l c m {2, k } divides N , the distribution of this random permutation converges to that of the uniform distribution on the alternating group A N in the total‐variation distance as N → ∞. We obtain large‐deviations bounds for the number of cycles that, together with Gamburd's (Ann Probab 34 (2006), 1827–1848) result, allow us to derive sharp estimates for the moments of the number of cycles. These estimates allow us to confirm certain cases of conjectures made by Pippenger and Schleich (Random Struct Algorithm 28 (2006), 247–288). © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010