2015/02/02 by Jun Zhao, Zhao, Jun, Osman Yağan +4
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Probability (math.PR) #Social and Information Networks (cs.SI) #Stochastic processes and statistical mechanics #cs.DM #cs.SI #math.CO #math.PR #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1502.00405
arxiv created 2015/02/02 · openalex publication_date 2015/02/02 · arxiv updated 2015/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Uniform random intersection graphs have received much interest and been used in diverse applications. A uniform random intersection graph with n nodes is constructed as follows: each node selects a set of Kn different items uniformly at random from the same pool of Pn distinct items, and two nodes establish an undirected edge in between if and only if they share at least one item. For such graph denoted by G(n, Kn, Pn), we present the following results in this paper. First, we provide an exact analysis on the probabilities of G(n, Kn, Pn) having a perfect matching and having a Hamilton cycle respectively, under Pn = ω(n (ln n)5) (all asymptotic notation are understood with n → ∞). The analysis reveals that just like (k-)connectivity shown in prior work, for both properties of perfect matching containment and Hamilton cycle containment, G(n, Kn, Pn) also exhibits phase transitions: for each property above, as Kn increases, the limit of the probability that G(n, Kn, Pn) has the property increases from 0 to 1. Second, we compute the phase transition widths of G(n, Kn, Pn) for k-connectivity (KC), perfect matching containment (PMC), and Hamilton cycle containment (HCC), respectively. For a graph property R and a positive constant a < (1)/(2), with the phase transition width dn(R, a) defined as the difference between the minimal Kn ensuring G(n, Kn, Pn) having property R with probability at least 1-a or a, we show for any positive constants a<(1)/(2) and k: (i) If Pn=Ω(n) and Pn=o(nln n), then dn(KC, a) is either 0 or 1 for each n sufficiently large. (ii) If Pn=Θ(nln n), then dn(KC, a)=Θ(1). (iii) If Pn=ω(nln n), then dn(KC, a)=ω(1). (iv) If Pn=ω(n (ln n)5), dn(PMC, a) and dn(HCC, a) are both ω(1).