DIFFERENTIAL EQUATIONS FOR RANDOM PROCESSES AND RANDOM GRAPHS
成果类型：
Article
署名作者：
Wormald, Nicholas C.
署名单位：
University of Melbourne
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/aoap/1177004612
发表日期：
1995
页码：
1217-1235
关键词：
摘要：
General criteria are given to ensure that in a family of discrete random processes, given parameters exhibit convergence to the solution of a system of differential equations. As one application we consider random graph processes in which the maximum degree is bounded and show that the numbers of vertices of given degree exhibit this convergence as the total number of vertices tends to infinity. Two other applications are to random processes which generate independent sets of vertices in random r-regular graphs. In these cases, we deduce almost sure lower bounds on the size of independent sets of vertices in random r-regular graphs.