zbMATH — the first resource for mathematics

Random subgraphs of finite graphs. I: The scaling window under the triangle condition. (English) Zbl 1076.05071
Let \(G\) be a finite connected transitive graph with \(V\) vertices. Transitive: For every pair of vertices \(x\), \(y\) there is a graph isomorphism \(\varphi\) with \(\varphi(x)= y\). Then every vertex has the same degree \(\Omega\). The edges of \(G\) are deleted independently with probability \(1-p\), so that a stochastic subgraph \(H\) of \(G\) results. Let \(\tau_p(x,y)= P(x\leftrightarrow y)\) where \(x\leftrightarrow y\) means that there is a path from \(x\) to \(y\) in \(H\). Let \(C(x)\) be the cluster of vertex \(x\), i.e. \(C(x)= \{y\in G: x\leftrightarrow y\}\). The distribution of \(|C(x)|=\) cardinality of \(C(x)\) is independent of \(x\). Put \(\chi(p)= E|C(0)|= \sum_x\tau_p(0,x)\) (susceptibility). Dependence on \(p\) and \(V\) is sometimes omitted.
The paper studies the phenomenon that in a (small) neighbourhood (the window) of a suitable probability \(p_c\) (the critical threshold) the behaviour of \(\chi(p)\), \(E|C_{\max}|= E\max\{|C(x)|:x\) vertex} and related quantities for large \(V\) is different from the behaviour above and below the window (the latter also different). This is classical for the random graph, i.e. for \(H\) when \(G\) is complete. The threshold \(p_c\) is taken as the unique solution \(p\) of \(\chi(p)=\lambda V^{1/3}\) for some small constant \(\lambda> 0\), a choice based on known behaviour of the random graph. Some variation of \(p_c\) in a window is allowed. A typical window is \([p_c- \varepsilon\Omega^{-1}, p_c+ \varepsilon\Omega^{-1}]\), \(0< \varepsilon\leq\Lambda V^{-1/3}\), \(\Lambda\) constant.
Throughout the paper the authors assume the finite-graph triangle condition \(\Delta(p_c, x,y)\leq \delta(x,y)+ a_0\) for a sufficiently small constant \(a_0\) , where \(\Delta(p,x,y)= \sum\tau_p(x,u)\tau_p(u, v)\tau_p(v,y)\) with sum over all vertices \(u\), \(v\) of \(G\). General results on the above behaviour are proved: bounds on \(p_c\) and bounds for \(\chi(p)\) and \(E|C_{\max}|\) in, below and above the window. Also for percolation probability \(P(|C(0)|\geq N)\), \(N= \varepsilon^{\alpha- 2} V^{\alpha/3}\), \(0<\alpha< 1\), and the magnetization \(1-\sum_{k\leq V}(1- \gamma)^k P(|C(0)|= k)\), \(0< \gamma< 1\).
It is shown that the triangle condition holds for the random graph. This implies theorems approximating known results for the random graph. Other special cases are tori where the authors invoke their paper [Random subgraphs of finite graphs. II: The lace expansion and the triangle condition. Ann. Probab., in press].
Proofs make use of the differential inequality \([1-\max\Delta(p,x,y)]\Omega\leq d\psi/dp\leq \Omega\), where \(\max\) is over all edges \([x, y]\) in \(G\) and \(\psi= 1/\chi\). Bounds on the magnetization, that imply estimates for \(P(C(0)\geq k)\), are derived by other differential inequalities.

05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
Full Text: DOI arXiv
[1] Aizenman, Nucl Phys B [FS] 485 pp 551– (1997)
[2] Aizenman, Comm Math Phys 108 pp 489– (1987)
[3] Aizenman, J Stat Phys 44 pp 393– (1986)
[4] Aizenman, J Stat Phys 36 pp 107– (1984)
[5] Ajtai, Combinatorica 2 pp 1– (1982)
[6] Alon, Ann Probab 32 pp 1727– (2004)
[7] Barsky, Ann Probab 19 pp 1520– (1991)
[8] van den Berg, Ann Probab 15 pp 354– (1987)
[9] Bollobás, Trans Amer Math Soc 286 pp 257– (1984)
[10] Bollobás, Random Structures Algorithms 3 pp 55– (1992)
[11] Borgs, J Stat Phys 82 pp 1235– (1996)
[12] Borgs, Ann Probab
[13] Borgs, Combinatorica
[14] Borgs, Comm Math Phys 224 pp 153– (2001)
[15] Chayes, Phys Rev Lett 56 pp 1619– (1986)
[16] and , ”The mean field bound for the order parameter of Bernoulli percolation,” Percolation theory and ergodic theory of infinite particle systems, Ed. . Springer, New York, 1987, pp. 49-71.
[17] Erdõs, Magyar Tud Akad Mat Kutató Int Közl 5 pp 17– (1960)
[18] , , and , Random walks, critical phenomena, and triviality in quantum field theory, Springer, Berlin, 1992. · Zbl 0761.60061
[19] Frieze, Random Structures Algorithms 24 pp 42– (2004)
[20] , Percolation, 2nd edition, Springer, Berlin, 1999. · Zbl 0926.60004
[21] , Critical two-point functions for nearest-neighbour high-dimensional self-avoiding walk and percolation, in preparation.
[22] Hara, Ann Probab 31 pp 349– (2003)
[23] Hara, Commun Math Phys 128 pp 333– (1990)
[24] and , ”Mean-field behaviour and the lace expansion,” Probability and phase transition, Ed. . Kluwer, Dordrecht, 1994, pp. 87-122. · Zbl 0831.60107
[25] Hara, J Math Phys 41 pp 1244– (2000)
[26] Hara, J Stat Phys 99 pp 1075– (2000)
[27] van der Hofstad, Random Structures Algorithms
[28] van der Hofstad, Combin Probab Comput
[29] , , and , Random graphs, Wiley, New York, 2000.
[30] Łuczak, Random Structures Algorithms 1 pp 287– (1990)
[31] Menshikov, Sov Math Dokl 33 pp 856– (1986)
[32] Schonmann, Comm Math Phys 219 pp 271– (2001)
[33] Schonmann, Comm Math Phys 225 pp 453– (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.