Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The largest component in an inhomogeneous random intersection graph with clustering. | The largest component in an inhomogeneous random intersection graph with clustering Mindaugas Bloznelis Faculty of Mathematics and Informatics Vilnius University Vilnius LT-03225 Lithuania Submitted Feb 24 2010 Accepted Jul 18 2010 Published Aug 9 2010 Mathematics Subject Classifications 05C80 05C82 60J85 Abstract Given integers n and m bn and a probability measure Q on 0 1 . m consider the random intersection graph on the vertex set n 1 2 . n where i j E n are declared adjacent whenever S i nS j 0. Here S 1 . S n denote the iid random subsets of m with the distribution P S i A A 1Q A A c m . For sparse random intersection graphs we establish a first-order asymptotic as n TO for the order of the largest connected component N1 n 1 Q 0 p op n . Here p is the average of nonextinction probabilities of a related multitype Poisson branching process. 1 Introduction Let Q be a probability measure on 0 1 . m and let S1 . Sn be random subsets of a set W w1 . wm drawn independently from the probability distribution P S A - Q A A c W for i 1 . n. A random intersection graph G n m Q with vertex set V v1 . vn is defined as follows. Every vertex vi is prescribed the set S vi Si and two vertices vi and Vj are declared adjacent denoted vi Vj whenever S vi n S Vj 0. The elements of W are sometimes called attributes and S vi is called the set of attributes of Vi . Random intersection graphs G n m Q with the binomial distribution Q Bi m p were introduced in Singer-Cohen 15 and Karonski et al. 13 see also 10 and 16 . The emergence of a giant connected component in a sparse binomial random intersection graph was studied by Behrish 2 for m _n _ a 1 and by Lageras and Lindholm 14 for m _dn_ where d 0 is a constant. They have shown in particular that for a 1 the largest connected component collects a fraction of all vertices whenever the average THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R110 1 vertex degree say d is larger than 1 E. For d 1 E the order .
