Random subgraphs of finite graphs: I. The scaling window under the triangle condition
| dc.creator | Borgs, Christian | |
| dc.creator | Chayes, Jennifer T. | |
| dc.creator | van der Hofstad, Remco | |
| dc.creator | Slade, Gordon | |
| dc.creator | Spencer, Joel | |
| dc.date | 2004-01-08 | |
| dc.date.accessioned | 2026-07-07T05:04:25Z | |
| dc.date.available | 2026-07-07T05:04:25Z | |
| dc.description | We study random subgraphs of an arbitrary finite connected transitive graph $\mathbb G$ obtained by independently deleting edges with probability $1-p$. Let $V$ be the number of vertices in $\mathbb G$, and let $Ω$ be their degree. We define the critical threshold $p_c=p_c(\mathbb 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|=Θ(\cn^{-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 $ε=\cn(p_c-p)$. We also obtain an upper bound $O(\cn(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 $Θ(\cn(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$. | |
| dc.identifier | https://arxiv.org/abs/math/0401069 | |
| dc.identifier | http://arxiv.org/abs/math/0401069 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69798 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80, 60K35, 82B43 | |
| dc.title | Random subgraphs of finite graphs: I. The scaling window under the triangle condition | |
| dc.type | text |