Help:=proc(): print(`LC(p), RG(n,p), CC(G,i,n) `): print(`LaCu(G,n), N(n,eps,K), CER(n,eps,K) `): end: #LC(p): a loaded coin prob. p of success(1) , 1-p failure (0) LC:=proc(p) local a,b,ra,r: a:=numer(p): b:=denom(p): ra:=rand(1..b): r:=ra(): if r<=a then 1: else 0: fi: end: #RG(n,p): a random graph on n vertices {1, ..., n} #with prob. of an edge showing up being p RG:=proc(n,p) local G,i,j,c: G:={}: for i from 1 to n do for j from i+1 to n do c:=LC(p): if c=1 then G:=G union {{i,j}}: fi: od: od: G: end: #the connected component containing vertex i in graph G #that has n vertices CC:=proc(G,i,n) local F,T,i1,e,F1,f,F2: #T is the table of (immediate friends) for i1 from 1 to n do T[i1]:={}: od: for e in G do T[e[1]]:=T[e[1]] union {e[2]}: T[e[2]]:=T[e[2]] union {e[1]}: od: op(T): F:={i}: F1:= {i} union T[i]: while F<>F1 do F2:= {seq(op(T[f]), f in F1)} union F1: F:=F1: F1:=F2: od: F1: end: #LaCu(G,n): the largest cluster in the graph G on [1,n] LaCu:=proc(G,n) local i: max(seq(nops(CC(G,i,n)),i=1..n)): end: #N(n,eps,K): the average of the "largest cluster size" #of a random graph on n vertices with prob. of an edge #being 1/(n-1)*(1+eps) N:=proc(n,eps,K) local p, c,G,i: p:=1/(n-1)*(1+eps): c:=0: for i from 1 to K do G:=RG(n,p): c:=c+LaCu(G,n): od: evalf(c/K): end: #CER(n,eps,K): checks Erdos-Renyi (p. 4, col.1 of Slade's article in PCM) CER:=proc(n,eps,K) if eps<0 then evalf(N(n,eps,K)/2.*eps^2/log(n)): elif eps=0 then N(n,eps,K)/n^(2/3): else N(n,eps,K)/2/eps/n: fi: end: