#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