For a given random graph, a connected component that contains a finite fraction of the entire graph’s vertices is called giant.

A well known result in random graphs is the existence and uniqueness of the giant component in Erdos-Rényi model: if $G\in G(n,p)$ with $p=c/n$ and $c>1$, then there is a unique giant component of size $\zeta$, the smallest positive solution to $$1-\zeta=e^{-c\zeta}$$.

This result has been generalized in many other settings :

  • Starting with Molloy and Reed who proved a condition for the existence and uniqueness of a giant component for graph with a given degree sequence, under some technical requirements.
  • Under other requirements by Bollobas and Riordan, or Janson and Luczak.
  • Aiello et al. proved a similar result for Power-Law model.
  • Some years ago, Joos et al. showed a condition for the existence of a giant component for any given degree sequence. The uniqueness is still an open problem (as far as I know).

My question is :

Is there any random graph model for which, under some supercritical regime, we do not have the uniqueness of the giant component, but rather multiple giant components with positive probability?

I would be quite surprised if there is one. But maybe some preferential attachment model, with a fitness parameter as per the Bianconi–Barabási model, or a more general Price's model, might have this property.

  • 2
    $\begingroup$ Consider an independent-edge model where vertices have two types and the edge probability within types is much greater than between types. You can adjust the parameters so that there will likely be two giant components. This example is not so interesting but it shows that you need to tighten your requirements if you want the question to be non-trivial. $\endgroup$ – Brendan McKay Jul 8 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.