High-order Phase Transition in Random Hypergrpahs

arXiv1409.1174MaRDI QIDQ6254366FDOQ6254366

Linyuan Lu, Xing Peng

Publication date: 3 September 2014

Abstract: In this paper, we study the high-order phase transition in random $r$-uniform hypergraphs. For a positive integer $n$ and a real $pin[0,1]$, let $H:=H^r(n,p)$ be the random $r$-uniform hypergraph with vertex set $[n]$, where each $r$-set is selected as an edge with probability $p$ independently randomly. For $1leqsleqr-1$ and two $s$-sets $S$ and $S^{\prime }$, we say $S$ is connected to $S^{\prime }$ if there is a sequence of alternating $s$-sets and edges $S_0,F_1,S_1,F_2,ldots,F_k,S_k$ such that $S_0,S_1,ldots,S_k$ are $s$-sets, $S_0=S$, $S_k=S^{\prime }$, $F_1,F_2,ldots,F_k$ are edges of $H$, and $S_{i-1}cup{S}_{i}subseteq{F}_i$ for each $1leqileqk$. This is an equivalence relation over the family of all $s$-sets $[n]chooses$ and results in a partition: $Vchooses=cu{p}_i{C}_i$. Each $C_i$ is called an { $s$-th-order} connected component and a component $C_i$ is {em giant} if $|C_i|=Theta(n^s)$. We prove that the sharp threshold of the existence of the $s$-th-order giant connected components in $H^r(n,p)$ is $$. Let $c=nchooser-sp$. If $c$ is a constant and $$, then with high probability, all $s$-th-order connected components have size $O(lnn)$. If $c$ is a constant and $$, then with high probability, $H^r(n,p)$ has a unique giant connected $s$-th-order component and its size is $(z+o(1))nchooses$, where ${\displaystyle }$z=1-sum_{j=0}^infty frac{left({rchoose s}j -j+1 ight)^{j-1}}{j!}c^je^{-cleft({rchoose s}j -j+1 ight)}.${\displaystyle }$

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Hypergraphs (05C65)

This page was built for publication: High-order Phase Transition in Random Hypergrpahs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6254366)