# OK to post homework
# Aurora Hiveley, 1/28/25, Assignment 2

Help := proc(): print(`TotClique(G,k), CheckRamsey(k,K), EstimateAverageClique(n,p,k,K)`): end:


## total cliques
# TotClique(G,k): inputs a graph G=[n,E] and a positive integer k, 
# outputs the total number of k-cliques and k-anti-cliques
TotClique := proc(G,k):
nops(Cliques(G,k))+nops(Cliques(Comp(G),k)):
end:

# sample call
# TotClique([4, {{1, 2}, {1, 3}, {1, 4}, {2, 4}}], 3):
# check TotClique([4, {{1, 2}, {1, 3}, {1, 4}, {2, 4}}], 3) = TotTri([4, {{1, 2}, {1, 3}, {1, 4}, {2, 4}}], 3):


## check ramsey
# CheckRamsey(k,K): inputs a positive integer k and a large integer K, then picks K random graphs (using RG(18,1/2)) 
# and finds the minimum of TotClique(G,4);

CheckRamsey := proc(k,K) local i,GG,G:
GG := []:   # list of graphs
# using a list instead of a set to ensure that we get K total graphs 
# since list allows for repetition, but note that list may have repeated random graphs

for i from 1 to K do 
  G := RG(18,1/2):
  GG := [op(GG),G]:
od:

min(seq(TotClique(G,k), G in GG)):
end:




## estimate average number cliques
# EstimateAverageClique(n,p,k,K): 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

EstimateAverageClique := proc(n,p,k,K) local GG,G,i:
GG := []:   # list of graphs

for i from 1 to K do 
  G := RG(n,p):
  GG := [op(GG),G]:
od:

add(TotClique(G,k), G in GG)/K:
end:

# What did you get for EstimateAverageClique(10,1/2,4,10000)?
# 65657/10000, or ~6.5 cliques






## copied from C2.txt 
#C2.txt: Jan. 27, 2025
Help2:=proc(): print(`LC(p), RG(n,p), Cliques(G,k) `):end:
with(combinat):
#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:

###From C1
#C1.txt: Jan. 23, 2025 Exp Math (Dr. Z.)
Help1:=proc(): print(`Graphs(n), Tri(G) , TotTri(G) `):   end:



#An undirected  graph is a set of vertices V and a set of edges
#[V,E]   and edge e={i,j} where i and j belong to V
#Our vertices are labeled {1,2,...,n}
#Our data structure is [n,E] where E is the set of edges
[3,{{1,2},{1,3},{2,3}}];

#If there are n vertices how many (undirected) graphs there

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

#Tri(G): inputs a graph [n,E] and outputs the set of all triples {i,j,k}
#such {{i,j},{i,k},{j,k}} is a subset of E
Tri:=proc(G) local n,S,E,i,j,k:
n:=G[1]:
E:=G[2]:
#S is the set of love triangles
S:={}:
for i from  1 to n do
 for j from i+1 to n do
   for k from j+1 to n do
    #if member({i,j},E) and member({i,k},E), and member({j,k},E) then
     if {{i,j},{i,k},{j,k}} minus E={} then
       S:=S union {{i,j,k}}:
    fi:
   od:
 od:
od:

S:
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:
#Tot(G): the total number of love triangles and hate triangles
TotTri:=proc(G)
nops(Tri(G))+nops(Tri(Comp(G))):
end: