DEGREE SEQUENCE OF RANDOM PERMUTATION GRAPHS

• 成果类型: Article
• 署名作者: Bhattacharya, Bhaswar B.; Mukherjee, Sumit
• 署名单位: University of Pennsylvania; Columbia University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1207
• 发表日期: 2017
• 页码: 439-484
• 关键词: convergent sequences; number; LIMITS; MODEL

摘要

In this paper, we study the asymptotics of the degree sequence of permutation graphs associated with a sequence of random permutations. The limiting finite-dimensional distributions of the degree proportions are established using results from graph and permutation limit theories. In particular, we show that for a uniform random permutation, the joint distribution of the degree proportions of the vertices labeled [nr(1)], [nr(2)],..., [nr(s)] in the associated permutation graph converges to independent random variables D(r(1)), D(r(2)),..., D(r(s)), where D (r(i)) similar to Unif(r(i), 1-r(i)), for r(i) epsilon [0, 1] and i epsilon {1, 2,..., s}. Moreover, the degree proportion of the mid-vertex (the vertex labeled n/2) has a central limit theorem, and the minimum degree converges to a Rayleigh distribution after an appropriate scaling. Finally, the asymptotic finite-dimensional distributions of the permutation graph associated with a Mallows random permutation is determined, and interesting phase transitions are observed. Our results extend to other nonuniform measures on permutations as well.