# OK to post homework # Aurora Hiveley, 1/30/25, Assignment 3 Help := proc(): print(`PC(n,p,K), NuCGx(n,x), NuCGk(n,k)`): end: ## copied from Dr. Z's website PC:=proc(n,p,K) local i:evalf(coeff(add(IsCo(RG(n,p)),i=1..K),true,1)/K):end: # With n=10,20,30, and p=1/10, 2/10, ... and K=200 experiment and try to estimate the threshhold for connectivity, # i.e. when it changes being very unlikely to very likely. # [seq(PC(10,i/10,200), i=1..10)]; # output: [0.005, 0.14, 0.625, 0.94, 0.995, 1, 1, 1, 1, 0] # [seq(PC(20,i/10,200), i=1..10)]; # output: [0.065, 0.71, 0.98, 1, 1, 1, 1, 1, 1, 1, 0] # [seq(PC(30,i/10,200), i=1..10)]; # output: [0.19, 0.955, 0.99, 1, 1, 1, 1, 1, 1, 0] # as n increases, a smaller p is needed to make the probability very likely # for n=10, it shifts at ~ p = 4/10 # for n=20, it shifts at ~ p = 3/10 # for n=30, it shifts at ~ p = 2/10 ## NuCG(x) # NuCGx(n,x): inputs a pos. integer n and a variable x, and outputs a list of length n whose i-th entry is P[i](x) NuCGx:=proc(n,x) local f,i: f:=log(add((1+x)^(i*(i-1)/2)*z^i/i!,i=0..n)): f:=taylor(f,z=0,n+1); [seq(i!*coeff(f,z,i),i=1..n)]: end: ## NuCGk(n,k) # NuCGk(n,k): inputs a positive integer n and a non-negative integer k and outputs the sequence of coefficients of x^(n-1+k) of P[n](x) NuCGk := proc(n,k) option remember: coeff(NuCGx(n,x)[n],x,n-1+k): end: # examples: # [seq(NuCGk(n,0), n=1..8)]; # output: [1, 1, 3, 16, 125, 1296, 16807, 262144] --> A000272 # [seq(NuCGk(n,1), n=1..8)]; # [0, 0, 1, 15, 222, 3660, 68295, 1436568] --> A-57500 # the OEIS has entries for sequences up to (and including) k=12 ### copied from C3.txt #C3.txt: Jan.30, 2025 Help3:=proc(): print(`AM(G), Neis(G), IsCo(G), NuCG(n), NuCGc(n) `): end: #Neis(G): inputs a graph G=[n,E] and outputs a list of length n, N, such that #N[i] is the set of neighbors of vertexi Neis:=proc(G) local n,E,N,i,e: n:=G[1]: E:=G[2]: for i from 1 to n do N[i]:={}: od: for e in E do N[e[1]]:=N[e[1]] union {e[2]}: N[e[2]]:=N[e[2]] union {e[1]}: od: [seq(N[i],i=1..n)]: end: #C(G,i): The connected component of vertex i CC:=proc(G,i) local n,C1,C2,C3,N,i1: if not (type(G,list) and nops(G)=2 and type(G[1],integer) and G[1]>=0 and type(G[2],set)) then RETURN(FAIL): fi: n:=G[1]: N:=Neis(G): C1:={i}: C2:=C1 union { seq(op(N[i1]), i1 in C1)}: while C1<>C2 do C3:=C2 union { seq(op(N[i1]), i1 in C2)}: C1:=C2: C2:=C3: od: C2: end: #IsCo(G): Is the graph G connected? IsCo:=proc(G): evalb(nops(CC(G,1))=G[1]):end: #NuCG(n): the first n terms of the sequence enumerating CONNECTED labeled graphs on n vertices #OEIS A001187 NuCG:=proc(n) local i,g: [seq(coeff(add(IsCo(g), g in Graphs(i)),true,1),i=1..n)]: end: NuCGc:=proc(n) local f,z,i: #The number of labeled graphs on n vertices is 2^binomial(n,2) f:=log(add(2^binomial(i,2)*z^i/i!,i=0..n)): f:=taylor(f,z=0,n+1): [seq(i!*coeff(f,z,i),i=1..n)]: end: ## adjacency matrices Code by Aurora Hiveley # AM(G): inputs a graph [n,E] and outputs the adjacency matrix, represented as a list of length n of lists of length n, # such that M[i][j]=1 if {i,j} belongs to E and 0 otherwise. # For example AM([2,{{1,2}}]); should output [[0,1],[1,0]] . AM := proc(G) local n,E,e,M: n := G[1]: E := G[2]: M := [[0$n]$n]: # initialize n x n matrix of all 0's for e in E do M[e[1]][e[2]]++: M[e[2]][e[1]]++: od: M: end: #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: