#C11.txt, Feb. 27, 2025, the sensitivity conjecture of Hao Hunag (according to Knuth)
Help11:=proc(): print(` NeiList(G), MaxNN(G,H) , MinMaxNN(G,r) , MinMaxNNpablo(G,r), An(n), Bn(n), Mul(A,B)`):end:
with(combinat):
with(linalg):


#Mul(A,B): the product of matrix A and B (assuming that it exists)
Mul:=proc(A,B) local i,j,k,n:
[seq([seq(add(A[i][k]*B[k][j],k=1..nops(A[i])),j=1..nops(B[1]))],i=1..nops(A))]:
end:

#NeiList(G): inputs a graph G=[n,E] and outputs a list of length n
#whose i-th entry is the set of neighbors of vertex i
NeiList:=proc(G) local n, E,e,T,i:
n:=G[1]:
E:=G[2]:
for i from 1 to n do
T[i]:={}:
od:

for e in E do
T[e[1]]:=T[e[1]] union {e[2]}:
T[e[2]]:=T[e[2]] union {e[1]}:
od:
[seq(T[i],i=1..n)]:
end:

#MaxNN(G,H): inputs a graph G=[n,E] and a subset H of {1, ..., n} outputs the
#maximum number of neigbors a member that belong to H over all members of H 
MaxNN:=proc(G,H) local L,i:
L:=NeiList(G):
max(seq(nops(L[i] intersect H),  i in  H)):
end:

#MinMaxNN(G,r): minimum of MaxNN(G,H) over all subsets H of {1, ..., n} with cardinality r
#Note: the Hao Huang famous sensitivity conjecture says that
#MinMaxNN(Ck(n),2^(n-1)+1)>=sqrt(n)
MinMaxNN:=proc(G,r) local n,i,S,s:
n:=G[1]:
S:=choose({seq(i,i=1..n)},r):
min(seq(MaxNN(G,s), s in S)):
end:

# MinMaxNNpablo(G,r): minimum of MaxNN(G,H) over all subsets H of [n] with size r. more memory-efficient way 
#suggested by Pablo Blacno (after discussions with Auora Hiveley)
MinMaxNNpablo:=proc(G,r) local n,i,c,mini,curr:
 n:=G[1]:
 c:=firstcomb(n,r):  
 mini:=MaxNN(G,c):   # check {1,..,r} first

 while nextcomb(c,n)<>FAIL do:   # check all other r-subsets of [n] and update the minimum if they are better
  c:=nextcomb(c,n):
  curr:=MaxNN(G,c):
  if curr < mini then:
   mini:=curr:
  fi:
 od:

 mini:
end:

#An(n): the 2^n by 2^n matrix (given as a list of lists) in Knuth's writeup of Huang's proof
An:=proc(n) local A,i:
option remember:
if n=0 then
 RETURN([[0]]):
fi:
A:=An(n-1):
[
seq([op(A[i]),0$(i-1),1,0$(nops(A[i])-i)],i=1..nops(A)),
seq ([0$(i-1),1,0$(nops(A[i])-i), op(-A[i])],i=1..nops(A))
]:
end:

#Bn(n): the 2^(n-1) by 2^n matrix in the paper
Bn:=proc(n) local A,i:
A:=An(n-1):
[
seq(A[i]+ [0$(i-1),sqrt(n),0$(nops(A[i])-i)],i=1..nops(A)),
seq([0$(i-1),1,0$(nops(A[i])-i)],i=1..nops(A))
]:
end:


#old stuff

#C2.txt: Jan. 27, 2025
Help2:=proc(): print(`LC(p), RG(n,p), Cliques(G,k) `):end:
with(combinat):
#LC(p): inputs a rational number between 0 and 1 and outputs true with prob. p
LC:=proc(p) local a,b,ra:
if not (type(p,fraction) and p>=0 and p<=1) then
 RETURN(FAIL):
fi:
a:=numer(p):
b:=denom(p):
ra:=rand(1..b)():
if ra<=a then
 true:
else
 false:
fi:
end:

RG:=proc(n,p) local E,i,j:
E:={}:
for i from 1 to n do
 for j from i+1 to n do
   if LC(p) then
    E:=E union {{i,j}}:
   fi:
 od:
od:
[n,E]:
end:

#Cliques(G,k): inputs a graph G and a pos. integer k outputs the set of
#k-cliques
Cliques:=proc(G,k) local n, E,S,i,c,C:
n:=G[1]:
E:=G[2]:
S:={}:
C:=choose({seq(i,i=1..n)},k):
for c in C do
 if choose(c,2) minus E={} then
  S:=S union {c}:
 fi:
od:
S:
end:

###From C1
#C1.txt: Jan. 23, 2025 Exp Math (Dr. Z.)
Help1:=proc(): print(`Graphs(n), Tri(G) , TotTri(G) `):   end:



#An undirected  graph is a set of vertices V and a set of edges
#[V,E]   and edge e={i,j} where i and j belong to V
#Our vertices are labeled {1,2,...,n}
#Our data structure is [n,E] where E is the set of edges
[3,{{1,2},{1,3},{2,3}}];

#If there are n vertices how many (undirected) graphs there

#Graphs(n): inputs a non-neg. integer and outputs the set of ALL
#graphs on {1,...,n} 
Graphs:=proc(n) local i,j,S,E,s:
E:={seq(seq({i,j},j=i+1..n),   i=1..n)};
S:=powerset(E):
{seq([n,s],s in S)}:
end:

#Tri(G): inputs a graph [n,E] and outputs the set of all triples {i,j,k}
#such {{i,j},{i,k},{j,k}} is a subset of E
Tri:=proc(G) local n,S,E,i,j,k:
n:=G[1]:
E:=G[2]:
#S is the set of love triangles
S:={}:
for i from  1 to n do
 for j from i+1 to n do
   for k from j+1 to n do
    #if member({i,j},E) and member({i,k},E), and member({j,k},E) then
     if {{i,j},{i,k},{j,k}} minus E={} then
       S:=S union {{i,j,k}}:
    fi:
   od:
 od:
od:

S:
end:

#Comp(G): the complement of G=[n,E]
Comp:=proc(G) local n,i,j,E:
n:=G[1]:
E:=G[2]:
[n,{seq(seq({i,j},j=i+1..n),   i=1..n)} minus E]:
end:
#Tot(G): the total number of love triangles and hate triangles
TotTri:=proc(G)
nops(Tri(G))+nops(Tri(Comp(G))):
end:
#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: