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: A note on the component structure in random intersection graphs with tunable clustering. | A note on the component structure in random intersection graphs with tunable clustering Andreas N. Lagerảs Mathematical Sciences and Centre for Theoretical Biology Chalmers University of Technology and Goteborg University 412 96 Gothenburg Sweden Mathias Lindholmy Department of Mathematics Stockholm University 106 91 Stockholm Sweden Submitted Sep 10 2007 Accepted Apr 4 2008 Published Apr 10 2008 Mathematics Subject Classification 05C80 Abstract We study the component structure in random intersection graphs with tunable clustering and show that the average degree works as a threshold for a phase transition for the size of the largest component. That is if the expected degree is less than one the size of the largest component is . of logarithmic order but if the average degree is greater than one . a single large component of linear order emerges and the size of the second largest component is at most of logarithmic order. 1 Introduction The random intersection graph denoted Qpp with a set of vertices V v1 . vn and a set of edges E is constructed from a bipartite graph Bm p with two sets of vertices V identical to those of Qmp and A a15. am which we call auxiliary vertices. Edges in Bm p between vertices and auxiliary vertices are included independently with probability p 2 0 1 . An edge between two vertices Vị and Vj in Qp is only present in E if both Vị and Vj are adjacent to some auxiliary vertex ak in Bmp Along the lines of Karonski et al. 5 we set m LdnJ and p -yn_ 1 2 where a y 0 to obtain an interesting graph structure and bounded average vertex degree. For random multi graphs the vertex degree distribution is defined as the distribution of the degree . the number of adjacent supported by the Faculty of Science Goteborg University. y supported by the Swedish Foundation for Strategic Research SSF . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N10 1 z 1 z n 1 j 1 p p 1 p n 1 j edges of a vertex chosen uniformly at random. As has been shown by .
