cliques and threshold functions

Question 1

isomorphic graphs

Answer 1

bijection such that {x,y} in E iff {φ(x), φ(y)} in E’

Question 2

clique

Answer 2

subgraph that is isomorphic to complete graph

Question 3

clique number of G

Answer 3

clique of highest order

Question 4

monotone increasing collection of graphs

Answer 4

G spanning subgraph of G’ and G in P then G’ in P

Question 5

threshold function

Answer 5

if pn«f(n) as n increases, then P(G(n,p) in P) tends to 0
if pn»f(n) then P(G(n,p) in P) tends to 1

Question 6

counting lemma

Answer 6

as n tends to infinity,
|A_n(k)|=Θ(n^k)
|A_n,j(k)|=O(n^{2k-j})

Question 7

order of clique

Answer 7

k for which there exists a subgraph isomorphic to K_k

Question 8

first moment method

Answer 8

sequence of nonnegative integer-valued RVs with E[X_n] tends to 0 and apply Markov’s inequality

Question 9

coupling

Answer 9

arranging both events to take place on a common probability space

Question 9

second moment method

Answer 9

Var(N_n)/E(N_n)^2 tends to 0 then N_n>0 with high probability

Question 10

threshold function to contain k-clique

Answer 10

n^{-2/(k-1)}

Question 11

balanced H

Answer 11

for any subgraph H’
e(H)/v(H)>=e(H’)/v(H’)