Abstract
We determine the order of the k-core in a large class of dense graph sequences. Let Gn be a sequence of undirected, n-vertex graphs with edge weights {ani,j}i,j∈[n] that converges to a graphon W : [0, 1]2 → [0, +∞) in the cut metric. Keeping an edge (i,j) of Gn with probability ani,j/n independently, we obtain a sequence of random graphs Gn(1/n). Using a branching process and the theory of dense graph limits, under mild assumptions we obtain the order of the k-core of random graphs Gn(1/n). Our result can also be used to obtain the threshold of appearance of a k-core of order n.
Original language | English (US) |
---|---|
Journal | Journal of Applied Probability |
DOIs | |
State | Accepted/In press - 2024 |
Keywords
- branching process
- dense graph limit
- graphon
- k-core
- percolation
- phase transition
- Random graphs
ASJC Scopus subject areas
- Statistics and Probability
- General Mathematics
- Statistics, Probability and Uncertainty