#Please do not post homework
#Jeffrey Tang, 2/1/25, Assignment 2


with(combinat):

#Graphs(n): inputs a non-neg. integer and outputs the set of ALL
#graphs on {1,...,n} 
Graphs:=proc(n) local i,j,S,E,s:
E:={seq(seq({i,j},j=i+1..n),   i=1..n)};
S:=powerset(E):
{seq([n,s],s in S)}:
end:

#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:

#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:


#Anticlique(G,k): inputs a graph and an integer k and outputs the number of k-anticliques (independent sets)
AntiCliques := 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 {seq(seq({i, j}, j = i + 1 .. k), i = 1 .. k)} intersect E = {} then
            S := S union {c}:
        fi:
    od:
    S:
end:

#TotClique(G,k): inputs a graph and integer k and outputs the number of k-cliques and k-anticliques
TotClique := proc(G, k)
    local cliques, anti_cliques:
    cliques := nops(Cliques(G, k)):
    anti_cliques := nops(AntiCliques(G, k)):
    cliques + anti_cliques:
end:

#CheckRamsey: inputs a positive integer k and a large integer K that picks K random graphs and finds the 
#minimum of TotClique(G,4)
CheckRamsey := proc(k, K)
    local i, G, min_val:
    min_val := infinity:
    for i from 1 to K do
        G := RG(18, 1/2):
        min_val := min(min_val, TotClique(G, 4)):
    od:
    min_val:
end:

#EstimateAverageClique(n,p,k,K) inputs integers n,p,k,K and outputs estimated average number of k-cliques
EstimateAverageClique := proc(n, p, k, K)
    local i, G, total:
    total := 0:
    for i from 1 to K do
        G := RG(n, p):
        total := total + nops(Cliques(G, k)):
    od:
    total / K:
end:

#EstimateAverageClique(10,1/2,4,10000) = 

#6. The probability of an edge showing up is p and a k-clique requires k C 2 edges so we need p^{k C 2} edges to #form a k-clique. A k-clique requires that k of the n vertices form a clique, which is n C k. Thus, the 
#closed-form is (n C k) * p^{(k C 2)}.