A NOTE ON HAMILTONICITY OF UNIFORM RANDOM INTERSECTION GRAPHS

被引:4
作者
Bloznelis, Mindaugas [1 ]
Radavicius, Irmantas [1 ]
机构
[1] Vilnius State Univ, Fac Math & Informat, LT-03225 Vilnius, Lithuania
关键词
random graph; random intersection graph; Hamilton cycle; clustering; COMPONENT EVOLUTION; VERTEX;
D O I
10.1007/s10986-011-9115-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We consider a collection of n independent random subsets of [m] = {1, 2, ... , m} that are uniformly distributed in the class of subsets of size d, and call any two subsets adjacent whenever they intersect. This adjacency relation defines a graph called the uniform random intersection graph and denoted by G(n,m,d). We fix d = 2,3, ... and study when, as n, m -> infinity, the graph G(n,m,d) contains a Hamilton cycle (the event denoted G(n,m,d) is an element of H). We show that P(G(n,m,d) is an element of H) = o(1) for d(2)nm(-1) - ln m - 2 ln ln m -> -infinity and P(G(n,m,d) is an element of H) = 1 - o(1) for 2nm(-1) - ln m - ln ln m -> +infinity.
引用
收藏
页码:155 / 161
页数:7
相关论文
共 50 条
  • [21] The Number of Triangles in Random Intersection Graphs
    Liang Dong
    Zhishui Hu
    Communications in Mathematics and Statistics, 2023, 11 : 695 - 725
  • [22] The Number of Triangles in Random Intersection Graphs
    Dong, Liang
    Hu, Zhishui
    COMMUNICATIONS IN MATHEMATICS AND STATISTICS, 2023, 11 (04) : 695 - 725
  • [23] Finding Hamilton cycles in random intersection graphs
    Rybarczyk, Katarzyna
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2018, 20 (01)
  • [24] COLORING RANDOM INTERSECTION GRAPHS AND COMPLEX NETWORKS
    Behrisch, Michael
    Taraz, Anusch
    Ueckerdt, Michael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (01) : 288 - 299
  • [25] The jamming constant of uniform random graphs
    Bermolen, Paola
    Jonckheere, Matthieu
    Moyal, Pascal
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2017, 127 (07) : 2138 - 2178
  • [26] Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs
    Chen, Ailian
    Zhang, Liping
    FILOMAT, 2023, 37 (26) : 9039 - 9050
  • [27] Large random intersection graphs inside the critical window and triangle counts
    Wang, Minmin
    ELECTRONIC JOURNAL OF PROBABILITY, 2025, 30
  • [28] A Note on the Conductance of the Binomial Random Intersection Graph
    Rybarczyk, Katarzyna
    Bloznelis, Mindaugas
    Jaworski, Jerzy
    ALGORITHMS AND MODELS FOR THE WEB GRAPH, WAW 2020, 2020, 12091 : 124 - 134
  • [29] A note on the width of sparse random graphs
    Do, Tuan Anh
    Erde, Joshua
    Kang, Mihyun
    JOURNAL OF GRAPH THEORY, 2024, 106 (02) : 273 - 295
  • [30] Hamiltonicity and colorings of arrangement graphs
    Felsner, S
    Hurtado, F
    Noy, M
    Streinu, I
    PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2000, : 155 - 164