THE K-CORE IN PERCOLATED DENSE GRAPH SEQUENCES

Erhan Bayraktar, Suman Chakraborty, Xin Zhang

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
JournalJournal of Applied Probability
DOIs
StateAccepted/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

Fingerprint

Dive into the research topics of 'THE K-CORE IN PERCOLATED DENSE GRAPH SEQUENCES'. Together they form a unique fingerprint.

Cite this