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