the giant component phase transition Flashcards
1
Q
sprinkling graph
A
nq_n tends to λ as n grows
G1,G2 independent realisations of G(n,q_n) and G(n,n^-5/4)
G3 their union
then whp
|Cmax(G3)|/n>1-η(λ)-ε
2
Q
phase transition
A
if λ<=1 lots of small components
if λ>1 whp there exists a giant component
3
Q
order of G
A
number of vertices
4
Q
exploration process
A
discover the component of I, by looking at its neighbours and then the neighbours of the neighbours
5
Q
breadth-first order
A
root, children, first child of root, second child of root, …, first child of first child, … etc
6
Q
states
A
active, inactive, neutral
7
Q
random walk associated via
A
number of active members
8
Q
binomial branching process
A
n choose k * p^k (1-p)^n-k
9
Q
poisson branching process
A
e^-λ λ^k/k!
10
Q
total number
A
inf {t: S_t=0}
