#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: