The phase transition in multitype binomial random graphs

Mihyun Kang, Christoph Koch, Angelica Pachon

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


We determine the asymptotic size of the largest component in the 2-type binomial random graph G(n, P) near criticality using a refined branching process approach. In G(n, P) every vertex has one of two types, the vector n describes the number of vertices of each type, and any edge {u, v} is present independently with a probability that is given by an entry of the probability matrix P according to the types of u and v. We prove that in the weakly supercritical regime, i.e., if the "distance" to the critical point of the phase transition is given by ε = ε(n) → 0, with probability 1-o(1), the largest component in G(n, P) contains asymptotically 2ε||n||1 vertices and all other components are of size o(ε||n||1).

Original languageEnglish
Pages (from-to)1042-1064
Number of pages23
JournalSIAM Journal on Discrete Mathematics
Issue number2
Publication statusPublished - 1 Jan 2015
Externally publishedYes


  • Branching process
  • Largest component
  • Phase transition
  • Random graphs


Dive into the research topics of 'The phase transition in multitype binomial random graphs'. Together they form a unique fingerprint.

Cite this