#OK to post homework #Joseph Koutsoutis, 02-02-2025, Assignment 2 read `C2.txt`: #3 TotClique := proc(G,k): nops(Cliques(G,k)) + nops(Cliques(Comp(G),k)): end: #4 CheckRamsey := proc(k,K) local i, curr_min: curr_min := binomial(18,k): for i from 1 to K do: curr_min := min(curr_min, TotClique(RG(18,1/2), k)): od: curr_min: end: #5 EstimateAverageClique := proc(n,p,k,K) local i: add(nops(Cliques(RG(n,p),k)), i=1..K) / K: end: # EstimateAverageClique(10,1/2,4,10000) outputted 2098/625 = 3.3568. #6 # Let S be a subset of [n] of size k. # We compute Pr[G[S] = K_k] = p^(binomial(k, 2)). # Let X_S be the indicator RV that indicates if G[S] = K_k. # By linearity of expectation: # E[number of k-cliques] = add(E[X_S], S in choose(n,k)) # = binomial(n,k) p^(binomial(k, 2)). # If we take n=10 and k=4, we get that E[number of k-cliques] = 3.28125, # which is close to the output of EstimateAverageClique(10,1/2,4,10000).