#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).