# Ok to post homework
# Lucy Martinez, 02-21-2025, Assignment 9

with(combinat):

######################
# Problem 1: Using the definition of the Cheeger constant
#  in this wikipedia article, write a procedure CheegerC(G)
#  that inputs a graph in our format [n,E] and outputs the Cheeger constant
#  [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)
CheegerC:=proc(G) local E,n,V,S,s,s1,S2,s2,e, i,cutSize,C,ratio:
n:=G[1]:
E:=G[2]:
V:={seq(op(e),e in E)}:
C:=infinity:
for i from 1 to floor(n/2) do
 for S in choose(V,i) do
  S2:=V minus S:
  cutSize:=0:
  for s1 in S do
   for s2 in S2 do
    if {s1,s2} in E then
	 cutSize:=cutSize+1:
	fi:
   od:
  od:
  ratio := cutSize / i:
  C:= min(C, ratio):
 od:
od:
C:
end:




# Problem 2: Write a procedure CheckBounds(G)
#  that 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

# What did you get for CheckBounds(G) for
# G=Gnd(n,2), 5 ≤ n ≤ 10
# n=5: [3, [2.500000000, 6.324555320]]
# n=6: [2, [2., 5.656854249]]
# n=7: [2, [1.599031132, 5.058112110]]
# n=8: [3/2, [1.292893219, 4.548218497]]
# n=9: [3/2, [1.060307379, 4.118849118]]
# n=10: [6/5, [0.881966012, 3.756521819]]


# G=Gnd(n,3), 5 ≤ n ≤ 10
# n=5: [3, [2.500000000, 6.324555320]]
# n=6: [3, [3.000000000, 7.745966692]]
# n=7: [4, [3.500000000, 9.165151390]]
# n=8: [3, [3., 8.485281374]]
# n=9: [3, [2.560307379, 7.838837739]]
# n=10: [12/5, [2.190983006, 7.251454484]]



CheckBounds:=proc(G) local Cheeger, Lambda_2,d:
Cheeger:=CheegerC(G):
d:=lam2(G)[1]:
Lambda_2:=lam2(G)[2]:
if Cheeger>=(d-Lambda_2)/2 and sqrt(2*d*(d-Lambda_2))>=Cheeger then
 return [Cheeger, [(d-Lambda_2)/2,sqrt(2*d*(d-Lambda_2))] ]:
fi:
end:




####################################previous classes
#C9.txt, Feb. 20, 2025
Help9:=proc():
print(`Gnd(n,d),AM(G),lam2(G),Vk(k),Nei(v),Ck(k)`):
end:

#Expanders
with(linalg):


#Gnd(n,d): the graph whose vertices are {0,1,...,n-1}
# and edges {i,i+j mod n} where j=1..d. The vertices will have degree 2d
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 adjancency matrix of the graph G (the stupid way)
AM:=proc(G) local n, E,e,i,j,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 returns [degree,Lambda_2] (Lambda_2 is the second largest eigenvalue 
# of the adjancencey 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 
# (starting at 00...0 and ends with 11..11
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:


#Nei(v): inputs the 0-1 vector and outputs all the vectors where exactly
# one bit is changed (hamming distance is 1) from the vector v
Nei:=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-dimensional unit cube as a graph in our format
Ck:=proc(k) local V,E,i,v:
V:=Vk(k):
E:={seq(seq({V[i],v},v in Nei(V[i])), i=1..nops(V))}:
E:=subs({seq(V[i]=i,i=1..nops(V))},E):
[nops(V),E]:
end: