tailieunhanh - Báo cáo toán học: "he largest component in an inhomogeneous random intersection graph with clustering"

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 .