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