The core in random hypergraphs and local weak convergence

Abstract

The degree of a vertex in a hypergraph is defined as the number of edges incident to it. In this paper we study the $k$-core, defined as the maximal induced subhypergraph of minimum degree $k$, of the random $r$-uniform hypergraph $H_r(n,p)$ for $r\ge 3$. We consider the case $k\ge 2$ and $p=d/n^{r-1}$ for which every vertex has fixed average degree $d>0$. We derive a multi-type branching process that describes the local structure of the $k$-core together with the mantle, i.e. the vertices outside the core.

27 pages, 2 figures. arXiv admin note: text overlap with arXiv:1503.09030

References in corpus (3)

• Differential equation approximations for Markov chains
• Finite size scaling for the core of large random hypergraphs
• Large deviations of empirical neighborhood distribution in sparse random graphs

Cited by in corpus (1)

• Warning Propagation: stability and subcriticality