with(combinat): with(GraphTheory): #OLD CODE #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 := proc(G, k) local n, E, S, i, j, c, C, edge_pair: n := G[1]: E := G[2]: S := {}: C := choose({seq(i, i=1..n)}, k): for c in C do edge_pair := {}; for i in c do for j in c do if i < j then edge_pair := edge_pair union {{i,j}}: fi: od: od: if edge_pair subset E then S := S union {c}; fi: od: return S; end: #END OLD CODE #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. #first I'm going to make a proc to give the graph complement #and the edges of a complete graph: CompleteGraphEdges:=proc(n) local i, j, edges: edges := {}; for i from 1 to n-1 do for j from i+1 to n do edges := edges union {{i, j}}: od: od: return edges; end proc: Complement:=proc(G) local n, E, nonE, x, y, Cplete, Comp: n:=G[1]: E:=G[2]: Cplete:=[n, CompleteGraphEdges(n)]: nonE:=convert(convert(Cplete[2], set) minus convert(E, set), set): Comp:=[n, nonE]: return(Comp): end: TotClique:=proc(G, k) local n, E, verts, subsets, cliques, vertices, anticliques, S, i: n:=G[1]: E:=G[2]: vertices:={seq(i,i=1..n)}: cliques:=Cliques(G,k): #print(cliques): anticliques:=Cliques(Complement(G),k): #print(anticliques): #SANITY CHECK if nops(choose(n,k))= nops(cliques)+nops(anticliques) then #print(verified); fi: [nops(cliques), nops(anticliques)]; end: #4: Writing a procedure #CheckRamsey(k,K), that inputs a positive intgeger k and a large #integer K that picks K random graphs (using RG(18,1/2)) and finds the #minimum of ToClique(G,4); CheckRamsey:=proc(k,K) local mincli,graphlist,totclilist,i, cliquelist,g : graphlist:=[]: for i from 1 to K do: graphlist:=[op(graphlist),RG(18,1/2)]: od: totclilist:=[]: for g in graphlist do: totclilist:=[op(totclilist), TotClique(g,4)]: od: print(kaylee): print(min(totclilist)); end: #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)? EstimateAverageClique:=proc(n,p,k,K) local i,Numer,graphlist,g, kcliquecounts: graphlist:=[]: for i from 1 to K do: graphlist:=[op(graphlist), RG(n,p)]: od: kcliquecounts:=[]: for g in graphlist do: kcliquecounts:=[op(kcliquecounts), TotClique(g, k)[1]]: od: Numer:=add(op(kcliquecounts)): return(Numer/K); end: #I got EstimateAverageClique(10,1/2, 3, 1000)= 7627/500 #and EstimateAverageClique(10, 1/2, 4, 1000)=3171/1000 #EstimateAverageClique(10,1/2,4,10000)=6563/2000 which is approx 3.3