tailieunhanh - Báo cáo toán học: "Rate of convergence of the short cycle distribution in random regular graphs generated by pegging"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Rate of convergence of the short cycle distribution in random regular graphs generated by pegging. | Rate of convergence of the short cycle distribution in random regular graphs generated by pegging Pu Gao and Nicholas Wormald Department of Combinatorics and Optimization University of Waterloo 200 University Ave W Ontario Canada p3gao@ nwormald@ Submitted Aug 30 2008 Accepted Mar 24 2009 Published Mar 31 2009 Mathematics Subject Classification 05C80 Abstract The pegging algorithm is a method of generating large random regular graphs beginning with small ones. The e-mixing time of the distribution of short cycle counts of these random regular graphs is the time at which the distribution reaches and maintains total variation distance at most e from its limiting distribution. We show that this e-mixing time is not o e-1 . This demonstrates that the upper bound O e-1 proved recently by the authors is essentially tight. 1 Introduction Different random graph models have been applied to analyse the behavior of real-world networks. The most classical and commonly studied one is the Erdos-Renyi model 1 which is the probability space of random graphs on n vertices with each edge appearing independently with some probability p. The properties of the random network degree distribution connectivity diameter etc. vary when p is assigned different values. However the Erdos-Renyi model cannot produce scale-free networks 2 whose degree distribution obeys the power law. The scale-free network caught a lot of attention because a diverse group of networks of interest are thought to be scale-free such as the collaboration network and the World Wide Web. The preferential attachment model was first introduced by Yule 13 and then studied by many other authors 3 7 in an attempt to simulate the properties of such scale-free networks. A new type of peer-to-peer ad-hoc network called the SWAN network was introduced recently by Bourassa and Holt 4 . The underlying topology of the SWAN network is a random regular graph. In the SWAN network clients arrive and .