# OK to post homework
# Lucy Martinez, 01-29-2025, Assignment 2

with(combinat):

# Problem 3: Write a procedure TotClique(G,k) that inputs a graph G=[n,E]
#  and a positive integer k, and outputs the total number of
#  k-cliques and k-anti-cliques.
TotClique:=proc(G,k) local kcliques,kanticliques:
kcliques:=Cliques(G,k):
kanticliques:=AntiCliques(G,k):
[nops(kcliques),nops(kanticliques)]:
end:


######################Helper procedures for TotClique
# AntiCliques(G,k): inputs a graph G and a pos. integer k, outputs the set
#  of k-cliques
AntiCliques:=proc(G,k) local Gcomp:
Gcomp:=Comp(G):
#anticliques of G are cliques of the complement graph
Cliques(Gcomp,k):
end:


# Comp(G): the complement of G=[n,E]
Comp:=proc(G) local n,i,j,E:
n:=G[1]:
E:=G[2]:
[n,{seq(seq({i,j},j=i+1..n),i=1..n)} minus E]:
end:

# Cliques(G,k): inputs a graph G and a pos. integer k outputs the set of
#  k-cliques
Cliques:=proc(G,k) local n, E,S,i,c,C:
n:=G[1]:
E:=G[2]:
S:={}:
C:=choose({seq(i,i=1..n)},k):
for c in C do
 if choose(c,2) minus E={} then
  S:=S union {c}:
 fi:
od:
S:
end:
######################


# Problem 4: Writing a procedure CheckRamsey(k,K), that inputs a positive integer k
#  and a large integer K that picks K random graphs (using RG(18,1/2))
#  and finds the minimum of TotClique(G,4);
CheckRamsey:=proc(k,K) local i,S,G,total:
S:={}:
for i from 1 to K do
 G:=RG(18,1/2):
 total:=TotClique(G,4):
 S:=S union {total}:
od:
min(S):
end:


######################Helper procedure for CheckRamsey(k,K)
#LC(p): inputs a rational number between 0 and 1 and outputs true with prob. p
LC:=proc(p) local a,b,ra:
if not (type(p,fraction) and p>=0 and p<=1) then
 RETURN(FAIL):
fi:
a:=numer(p):
b:=denom(p):
ra:=rand(1..b)():
if ra<=a then
 true:
else
 false:
fi:
end:


RG:=proc(n,p) local E,i,j:
E:={}:
for i from 1 to n do
 for j from i+1 to n do
   if LC(p) then
    E:=E union {{i,j}}:
   fi:
 od:
od:
[n,E]:
end:
######################


# Problem 5: Write a procedure EstimateAverageClique(n,p,k,K) that estimates
#  the average number of cliques of size k in a random graph given
#  by RG(n,p) by picking K of them and averaging

# What did you get for EstimateAverageClique(10,1/2,4,10000)?
#  Answer: 3.273500000

EstimateAverageClique:=proc(n,p,k,K) local co,G,i:
co:=0:
for i from 1 to K do
 G:=RG(n,p):
 co:=co+nops(Cliques(G,k)):
od:
evalf(co/K):
end: