tailieunhanh - Báo cáo toán học: "Sharp threshold functions for random intersection graphs via a coupling method"

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: Sharp threshold functions for random intersection graphs via a coupling method. | Sharp threshold functions for random intersection graphs via a coupling method. Katarzyna Rybarczyk Faculty of Mathematics and Computer Science Adam Mickiewicz University 60-769 Poznan Poland kryba@ Submitted Nov 25 2009 Accepted Feb 7 2011 Published Feb 14 2011 Mathematics Subject Classification 05C80 keywords random intersection graphs threshold functions connectivity Hamilton cycle perfect matching coupling Abstract We present a new method which enables us to find threshold functions for many properties in random intersection graphs. This method is used to establish sharp threshold functions in random intersection graphs for k-connectivity perfect matching containment and Hamilton cycle containment. 1 Introduction In a general random intersection graph G n m P m as defined in 9 each vertex v from a vertex set V V n is assigned independently a subset of features Wv c W from an auxiliary set of features W W m . Namely for any vertex v G V independently of all other vertices first a cardinality of Wv is chosen according to the probability distribution P m P0 . Pm and then the set Wv is picked uniformly at random from all subsets of W having the chosen cardinality. Two vertices v and v are adjacent in a general intersection graph G n m P m if and only if Wv and Wv intersect. In this article we concentrate on the widely studied random intersection graph model G n m p first defined in 11 17 which is a special case of the one above-mentioned. However the obtained results may be extended to a wider subclass of the G n m P m model which will be also discussed. In G n m p as defined in 11 17 the cardinality of Wv has the binomial distribution Bin m p . Pr w G Wv p independently for all v G V and w G W. Usually it is assumed that m na for some constant a 0 see for example 2 6 8 11 16 17 18 . However the main theorem of this article does not require this additional assumption. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P36 1 Obviously Pr v v G E G n m p 1

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học