#OK to post homework #Nick Belov, Feb 16nd 2025, Assignment 9 read "C9.txt"; with(combinat): CheegerC := proc(G) local n, e, E, V, i, minVal, allSubsets, S, T, boundary, ratio; n := G[1]; E := G[2]; V := {seq(1..n)}; minVal := infinity; for i to floor(n/2) do allSubsets := choose(V, i); for S in allSubsets do T := V minus S; boundary := {}; for e in E do if (e[1] in S) <> (e[2] in S) then boundary := boundary union {e}; fi; od; ratio := nops(boundary) / i; if ratio < minVal then minVal := ratio; fi; od; od; return minVal; end proc: CheckBounds := proc(G) local d, lambda, h, lower, upper, inside, tmp; tmp := lam2(G); d := op(1, tmp); lambda := op(2, tmp); h := CheegerC(G); lower := (d - lambda) / 2; upper := sqrt(2 * d * (d - lambda)); if h >= lower and h <= upper then inside := true; else inside := false; fi; return [h, [lower, upper], inside]; end proc: TestBounds := proc() local n, res; for n from 5 to 10 do res := CheckBounds(Gnd(n,2)); print(n,2): print(res); od; for n from 5 to 10 do res := CheckBounds(Gnd(n,3)); print(n,3): print(res); od; end proc: #for 2, it was always true until n=9 then it was false #for 3, it was true the entire time P:= proc(k) return charpoly(AM(Ck(k)),x); end: