The size of the giant high-order component in random hypergraphs

被引：12
作者：
Cooley, Oliver [1 ]
Kang, Mihyun [1 ]
Koch, Christoph [1 ]
机构：
[1] Graz Univ Technol, Inst Discrete Math, Steyrergasse 30, A-8010 Graz, Austria
来源：
RANDOM STRUCTURES & ALGORITHMS | 2018年 / 53卷 / 02期
基金：
奥地利科学基金会;
关键词：
branching process; degree; giant component; high-order connectedness; phase transition; random hypergraphs; PHASE-TRANSITION; EVOLUTION;
D O I：
10.1002/rsa.20761
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
The phase transition in the size of the giant component in random graphs is one of the most well-studied phenomena in random graph theory. For hypergraphs, there are many possible generalizations of the notion of a connected component. We consider the following: two j-sets (sets of j vertices) are j-connected if there is a walk of edges between them such that two consecutive edges intersect in at least j vertices. A hypergraph is j-connected if all j-sets are pairwise j-connected. In this paper, we determine the asymptotic size of the unique giant j-connected component in random k-uniform hypergraphs for any k3 and 1j <= k-1.
引用
收藏
页码：238 / 288
页数：51
相关论文
共 24 条
  • [1] [Anonymous], 2002, THEORY BRANCHING PRO
  • [2] [Anonymous], 2000, WIL INT S D, DOI 10.1002/9781118032718
  • [3] Local Limit Theorems for the Giant Component of Random Hypergraphs
    Behrisch, Michael
    Coja-Oghlan, Amin
    Kang, Mihyun
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2014, 23 (03) : 331 - 366
  • [4] The Order of the Giant Component of Random Hypergraphs
    Behrisch, Michael
    Coja-Oghlan, Amin
    Kang, Mihyun
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2010, 36 (02) : 149 - 184
  • [5] THE EVOLUTION OF RANDOM GRAPHS
    BOLLOBAS, B
    [J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1984, 286 (01) : 257 - 274
  • [6] Bollobas B., 2012, ELECTRON J COMB, V19, pP21
  • [7] Bollobas B., 1984, The Evolution of Sparse Graphs, Graph Theory and Combinatorics, P35
  • [8] Exploring hypergraphs with martingales
    Bollobas, Bela
    Riordan, Oliver
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2017, 50 (03) : 325 - 352
  • [9] Asymptotic normality of the size of the giant component in a random hypergraph
    Bollobas, Bela
    Riordan, Oliver
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2012, 41 (04) : 441 - 450
  • [10] Coja-Oghlan A., 2017, PREPRINT
123