#OK to post homework #Joseph Koutsoutis, 02-23-2025, Assignment 9 read `C9.txt`: with(combinat): #1 CheegerC := proc(G) local n, E, i, C, T, S, k, e, V: C := infinity: n, E := op(G): V := {seq(i, i=1..n)}: for i from 1 to floor(n/2) do: T := choose(V, i): for S in T do: k := 0: for e in E do: if (e[1] in S and not e[2] in S) or (e[2] in S and not e[1] in S) then: k++: fi: od: if k / i < C then: C := k / i: fi: od: od: C: end: #The procedure above is slow but I think that this can be approximated within a factor of #O(log n) by using the standard approximation algorithm for the sparsest cut problem. #2 CheckBounds := proc(G) local C, d, lambda2, lb, ub: C := evalf(CheegerC(G)): d, lambda2 := op(lam2(G)): lb := (d - lambda2) / 2: ub := sqrt(2*d*(d - lambda2)): [C, [lb, ub], evalb(C >= lb and C <= ub)]: end: #{seq(CheckBounds(Gnd(n, 2))[3], n=5..10)} and {seq(CheckBounds(Gnd(n, 3))[3], n=5..10)} #both outputted {true}. #3 #After playing with values of k from 1 to 7, my guess was that #charpoly(AM(Ck(k)), x) = prod((x - (k - 2i))^binomial(k, i) , i=0..k). #I got to the point where I noticed AM(Ck(k)) = [[ AM(Ck(k-1)), I(2^(k-1))], # [ I(2^(k-1)), AM(Ck(k-1))]] #Where I(2^(k-1)) is the identity matrix of dimension 2^(k-1) by 2^(k-1). #I couldn't figure out how to compute the determinant but the computation can be found here: #https://math.stackexchange.com/questions/300105/how-to-find-the-spectrum-of-the-hypercube