A note on Hamiltonicity of uniform random intersection graphs

被引:0
|
作者
Mindaugas Bloznelis
Irmantas Radavičius
机构
[1] Vilnius University,Faculty of Mathematics and Informatics
来源
Lithuanian Mathematical Journal | 2011年 / 51卷
关键词
random graph; random intersection graph; Hamilton cycle; clustering; 05C45; 05C80;
D O I
暂无
中图分类号
学科分类号
摘要
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 Gn,m,d. We fix d = 2, 3, . . . and study when, as n,m → ∞, the graph Gn,m,d contains a Hamilton cycle (the event denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ {G_{n,m,d}} \in \mathcal{H} $\end{document}). We show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = o(1) $\end{document} for d2nm−1− lnm − 2 ln lnm → −∞ and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = 1 - o(1) $\end{document} for 2nm−1− lnm − ln lnm → +∞.
引用
收藏
页码:155 / 161
页数:6
相关论文
共 50 条
  • [1] A NOTE ON HAMILTONICITY OF UNIFORM RANDOM INTERSECTION GRAPHS
    Bloznelis, Mindaugas
    Radavicius, Irmantas
    LITHUANIAN MATHEMATICAL JOURNAL, 2011, 51 (02) : 155 - 161
  • [2] Sharp thresholds for Hamiltonicity in random intersection graphs
    Efthymiou, Charilaos
    Spirakis, Paul G.
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) : 3714 - 3730
  • [3] A Note on the Vertex Degree Distribution of Random Intersection Graphs
    Mindaugas Bloznelis
    Lithuanian Mathematical Journal, 2020, 60 : 452 - 455
  • [4] A Note on the Vertex Degree Distribution of Random Intersection Graphs
    Bloznelis, Mindaugas
    LITHUANIAN MATHEMATICAL JOURNAL, 2020, 60 (04) : 452 - 455
  • [5] On the Hamiltonicity of random bipartite graphs
    Yilun Shang
    Indian Journal of Pure and Applied Mathematics, 2015, 46 : 163 - 173
  • [6] ON THE HAMILTONICITY OF RANDOM BIPARTITE GRAPHS
    Shang, Yilun
    INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2015, 46 (02) : 163 - 173
  • [7] Assortativity and clustering of sparse random intersection graphs
    Bloznelis, Mindaugas
    Jaworski, Jerzy
    Kurauskas, Valentas
    ELECTRONIC JOURNAL OF PROBABILITY, 2013, 18 : 1 - 24
  • [8] Perfect matchings in random intersection graphs
    Mindaugas Bloznelis
    Tomasz Łuczak
    Acta Mathematica Hungarica, 2013, 138 : 15 - 33
  • [9] Perfect matchings in random intersection graphs
    Bloznelis, M.
    Luczak, T.
    ACTA MATHEMATICA HUNGARICA, 2013, 138 (1-2) : 15 - 33
  • [10] Hamiltonicity of random graphs produced by 2-processes
    Telcs, Andras
    Wormald, Nicholas
    Zhou, Sanming
    RANDOM STRUCTURES & ALGORITHMS, 2007, 31 (04) : 450 - 481