Introduction to Random Graphs

Question 1

graph

Answer 1

pair of vertex set and edge set

Question 2

complete graph

Answer 2

n vertices and all possible edges

Question 3

subgraph

Answer 3

subset of vertices and subset of edges

Question 4

G(n,p) Erdos-Renyi random graph

Answer 4

random spanning subgraph of Kn
P(E(G(n,p))=s)=p^s(1-p)^{{n choose 2} - s}

Question 5

connected

Answer 5

there is a path between any pair of vertices
//one component

Question 6

cycle

Answer 6

sequence of distinct vertices and there is edge v_n to v_1

Question 7

occurs with high probability

Answer 7

lim P(A_n) =1 as n tends to infinity

Question 8

neighbour

Answer 8

(v,w) in E

Question 9

edges in complete

Answer 9

n choose 2

Question 10

spanning subgraph

Answer 10

V’=V

Question 11

tree

Answer 11

connected graph with no cycles

Question 12

component

Answer 12

maximal connected subgraph

Question 13

Cayley’s formula/number of trees on n vertices

Answer 13

n^{n-2}

Question 14

a_n=o(b_n)

Answer 14

a_n/b_n tends to 0 as n tends to infinity

Question 15

a_n=O(b_n)

Answer 15

there exists C such that a_n =< Cb_n for all n

Question 16

a_n ~ b_n

Answer 16

lim (a_n/b_n)=1

Question 17

a_n«b_n

Answer 17

a_n=o(b_n)

Question 18

a_n»b_n

Answer 18

b_n=o(a_n)

Question 19

a_n=Θ(b_n)

Answer 19

a_n=O(b_n) and b_n=O(a_n)

Question 20

union bound

Answer 20

P(unions)<=sum of Ps

Question 21

expectation

Answer 21

sum of xP(X=x)

Question 22

Var(X)

Answer 22

E(X^2)-E(X)^2

Question 23

covariance

Answer 23

E(XY)-E(X)E(Y)

Question 24

markov’s inequality

Answer 24

nonnegative RV, t>0
P[X>=t]<=E[X]/t

Question 25

tends to x in probability

Answer 25

for all ε |X_n-x|<ε with high probability//
lim P[|X_n-x|>=ε]=0

Question 26

branching process with offspring distribution q

Answer 26

sequence of RVs taking values in NN_0 representing the sizes of successive generations when each individual independently has k offspring with probability q_k

Question 27

total size

Answer 27

sum of Zs

Question 28

survives

Answer 28

if T = inf

Question 29

extinction occurs

Answer 29

T<inf