Random subgraphs of finite graphs: I. The scaling window under the triangle condition

Christian Borgs, Jennifer T. Chayes, Remco Van Der Hofstad, Gordon Slade, Joel Spencer

Research output: Contribution to journalArticle

Abstract

We study random subgraphs of an arbitrary finite connected transitive graph G obtained by independently deleting edges with probability 1 - p. Let V be the number of vertices in G, and let Ω be their degree. We define the critical threshold p c = p c(G, λ) to be the value of p for which the expected cluster size of a fixed vertex attains the value λV 1/3, where λ is fixed and positive. We show that, for any such model, there is a phase transition at p c analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold p c. In particular, we show that the largest cluster inside a scaling window of size |p-p c| = Θ(Ω -1 V -1/3) is of size Θ(V 2/3), while, below this scaling window, it is much smaller, of order O(ε 2 log(Vε -3)), with ε = Ω(p c - p). We also obtain an upper bound O(Ω(p -p c)V) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order Θ(Ω(p - p c)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n-cube and certain Hamming cubes, as well as the spread-out n-dimensional torus for n > 6.

Original languageEnglish (US)
Pages (from-to)137-184
Number of pages48
JournalRandom Structures and Algorithms
Volume27
Issue number2
DOIs
StatePublished - Sep 2005

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Random subgraphs of finite graphs: I. The scaling window under the triangle condition'. Together they form a unique fingerprint.

  • Cite this