This talk addresses the random graph model originally introduced by Erdös et Rényi in 1959. This model gives rise to a large number of threshold phenomena that are evocative of phase transitions in statistical physics. The talk illustrates the way several results on random graphs can be reexamined in a new perspective provided by a simple model of statistical physics, the Potts model. The problem addressed is principally that of the size of the giant component for which quantitative estimates are derived.
More generally, the talk is motivated by a desire to understand what statistical physics models may bring to the realm of threshold problems, not only in random graphs but also in the satisfiability of random boolean formulæ.
n 
2 
The characteristics of G_{n,p} resemble those of G^{^}_{n,e} provided e» Np.We refer globally to Bollobás's book [4] for a discussion of these rich models and for precise conditions that make the assertion above into a valid mathematical statement. (The transfer from G^{^}_{n,e} to G_{n,p} is an Abelian one, whereas the converse transfer has a Tauberian flavour.)
E(S)= 


1 

, 
Z(g,n)= 

e 

, 
P 

(G)= 
æ ç ç è 

ö ÷ ÷ ø 

æ ç ç è 
1 

ö ÷ ÷ ø 

, 
Z(g,n)» e 


P 

(G) q^{c(G)}. (3) 
X 

(S) = 


1 

, 
E(S)= 

 


X 

. 
Z(g,n) » 


exp 
æ ç ç è 
 


X 

ö ÷ ÷ ø 
, 
Z 

:= 

P(G) q^{c(G)}, Z 

= 

e 

. 
sin^{2} 

+cos^{2} 

=1, 
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.