# OK to post homework # Aurora Hiveley, 2/21/25, Assignment 9 Help := proc(): print(`Cheeger(G), dS(G,S), CheckBounds(G)`): end: with(combinat): with(linalg): # CheegerC(G): inputs a graph [n,E] and outputs the Cheeger constant # cheeger constant h(G) = min_{0 < |S| <= n/2} |delta(S)|/|S| # delta(S) = {(u,v) s.t. u in S, v notin S} # Hints: # 1. with the combinat package loaded, choose(S,i) gives you the set of subsets of S of size i # 2. To get the number of edges between S and its complement, form the set of potential edges {s1,s2} # where s1 is in S and s2 is in its complement, and then intersect it with E and then take its nops Cheeger := proc(G) local n,E,collS,S,L,i: n := G[1]: E := G[2]: collS := {seq(op(choose(n,i)), i=1..floor(n/2))}: # set of possible vertex subsets S to test L := [seq( nops(dS(G,S))/nops(S) , S in collS)]: min(L): end: dS := proc(G,S) local n,E,T,AE,i,s,t: n := G[1]: E := G[2]: T := {seq(i,i=1..n)} minus convert(S,set): # V\S AE := {seq( seq({s,t}, t in T ), s in S )}: # all edges between S and V\S AE intersect E: # keep only edges in E end: # CheckBounds(G): outputs the Cheeger constant and the interval [(d-Lambda_2)/2,sqrt(2*d*(d-Lambda_2))] and checks # that the former is inside the latter. CheckBounds := proc(G) local L,d,l,h: L := lam2(G): d := L[1]: l := L[-1]: h := Cheeger(G): if (d-l)/2 <= h and h <= sqrt(2*d*(d-l)) then [h, [(d-l)/2, sqrt(2*d*(d-l))]]: else fail: fi: end: # What did you get for CheckBounds(G) for # G=Gnd(n,2), 5 ≤ n ≤ 10 # [seq(CheckBounds(Gnd(n,2)), n=5..10)]: # output: [[3, [2.500000000, 6.324555320]], [2, [2., 5.656854249]], [2, [1.599031132, 5.058112110]], [3/2, [1.292893219, 4.548218497]], [3/2, [1.060307379, 4.118849118]], [6/5, [0.881966012, 3.756521819]]] # G=Gnd(n,3), 5 ≤ n ≤ 10 # [seq(CheckBounds(Gnd(n,3)), n=5..10)]: # output: [[3, [2.500000000, 6.324555320]], [3, [3.000000000, 7.745966692]], [4, [3.500000000, 9.165151390]], [3, [3., 8.485281374]], [3, [2.560307379, 7.838837739]], [12/5, [2.190983006, 7.251454484]]] ### copied from C9.txt #C9.txt: Feb. 20,2025 Help9:=proc(): print(` Gnd(n,d), AM(G) ,lam2(G), Vk(k), HD1(v) , Ck(k) `):end: with(linalg): #Gnd(n,d): the graph whose vertices are {0,...,n-1} and edges {i, i+j mod n} j=1..d Gnd:=proc(n,d) local i,j,E: E:={ seq(seq({ i,i+j mod n},j=1..d),i=0..n-1)}: [n,subs({seq(i=i+1,i=0..n-1)},E)]: end: #AM(G): the adjacency matrix of the graph G (the stupid way) AM:=proc(G) local n,E,i,j,e,A: n:=G[1]: E:=G[2]: for i from 1 to n do for j from 1 to n do A[i,j]:=0: od: od: for e in E do A[e[1],e[2]]:=1: A[e[2],e[1]]:=1: od: [seq([seq(A[i,j],j=1..n)],i=1..n)]: end: #lam2(G): inputs a graph and returns FAIL if it is not regular, otherwise it recurns #[degree, Lambda_2] (Lambda_2 is the second largestg eigenvalue of the adjacency matrix) lam2:=proc(G) local A,x,d,S,i: A:=AM(G): S:={seq(add(A[i]),i=1..nops(A))}: if nops(S)<>1 then RETURN(FAIL): fi: d:=S[1]: [d,fsolve(charpoly(A,x))[-2]]: end: #Vk(k): The list of all 0-1 vectors of length k in lex order Vk:=proc(k) local S,i: option remember: if k=0 then RETURN([[]]): fi: S:=Vk(k-1): [seq([0, op(S[i])], i=1..nops(S)),seq([1, op(S[i])], i=1..nops(S))]: end: #HD1(v): inputs a 0-1 vector and outputs all the vectors where exactly one bit is changed HD1:=proc(v) local k,i: k:=nops(v): if {op(v)} minus {0,1}<>{} then RETURN(FAIL): fi: {seq([op(1..i-1,v), 1-v[i] , op(i+1..k,v)], i=1..k)}: end: #Ck(k): the k-dim unit cube as a graph in our format Ck:=proc(k) local V,E,i,v: V:=Vk(k): #E is the set of edges {v,n} where n is a member of HD1(v) E:={seq(seq({V[i],v},v in HD1(V[i])),i=1..nops(V))}: E:=subs({seq(V[i]=i,i=1..nops(V))},E): [nops(V),E]: end: