##############################################################################################
##This is ComboProject6.txt, a Maple package to generate and investigate minimal degrees     #
#and average degrees of vertices in induced subgraphs of famous families                     #
#inspired by Hao Huang's amazing proof of the Sensitivity Conjecture                         #
####It is the Maple package created by Team 6 in Dr. Z.'s Combinatorics Class at             #
#Rutgers University, Fall 2020.                                                              #
# Save this file as `ComboProject6.txt`, to use it                                           #
#Type, in a Maple session                                                                    #
#read `ComboProject6.txt`):                                                                  #
#and then to get a list of the functions type                                                #
#Help():                                                                                     #
#For Help with any of the functions, type                                                    # 
#Help(FunctionName)                                                                          #
#Team Leader:                                                                                #
#Team members:                                                                               #
##############################################################################################


with(combinat):

print(`This is ComboProject6.txt, a Maple package that is part of Project 6 in Dr. Z.'s Combinatorics Class at Rutgers University`):
print(`to generate and investigate minimal degrees             `):
print(`and average degrees of vertices in induced subgraphs of famous families of graphs`):
print(`inspired by Hao Huang's amazing proof of the Sensitivity Conjecture `):
print(``):
print(`Team Leader: tbd `):
print(``):
print(`Other Team members: tbd `):
print(``):
print(`For a list of all the functions type: Help(); `):
print(`For Help with any of the functions, type  Help(FunctionName):`):                                                                        
with(combinat):
Help:=proc()
if nargs=0 then
print(`The available procedures are: AvDegIG, Bn, Cn , DegIG, MaxDegIG, SimuAvDegree, SimuMaxDegree `):
print(` `): 

elif nargs=1 and args[1]=AvDegIG then
print(`AvDegIG(G,S): Given a graph G (in canonical form i.e. where the vertices are called {1,...N}, where N=nops(G)), a subset S of {1, ...,n}`):
print(`finds the average degree in the induced subgraph of G induced by S. Try`):
print(`DegIG(Bn(3)[1],{1,3,4,5});`):

elif nargs=1 and args[1]=Bn then
print(`Bn(n): The canonical form of the n-dimensional unit cube, followed by the dictionary. Try:`):
print(`Bn(3);`):

elif nargs=1 and args[1]=Cn then
print(`The list of vertices of the n-dimensional unit cube. Try: `):
print(`Cn(3);`):

elif nargs=1 and args[1]=DegIG then
print(`DegIG(G,S,i): Given a graph G (in canonical form i.e. where the vertices are called {1,...N}, where N=nops(G)), a subset S of {1, ...,n}`):
print(`and a vertex in S, finds the number of neighbors of i in G that also belong to S. Try:`):
print(`DegIG(Bn(3)[1],{1,3,4,5},3); `):

elif nargs=1 and args[1]=MaxDegIG then
print(`MaxDegIG(G,S): Given a graph G (in canonical form i.e. where the vertices are called {1,...N}, where N=nops(G)), a subset S of {1, ...,n}`):
print(`finds the average degree in the induced subgraph of G induced by S. Try: `):
print(`MaxDegIG(Bn(3)[1],{1,3,4,5});`):


elif nargs=1 and args[1]=SimuAvDegree then
print(`SimuAvDegree(G,r,K): Inputs a graph G a positive integer r, a large positive integer K`):
print(`picks random subsets of size r  of the set of vertices K times and records the Average degree of the`):
print(`induced subgraph and returns the average and standard eviation ccording to that. Try:`):
print(`SimuAvDegree(Bn(9)[1],257,1000);`):

elif nargs=1 and args[1]=SimuMaxDegree then
print(`SimuMaxDegree(G,r,K,x): Inputs a graph G a positive integer r, a large positive integer K, and a variable x`):
print(`picks random subsets of size r  of the set of vertices K times and records the Maximal degree of the`):
print(`induced subgraph and returns the weight-enumerator according to that. Try:`):
print(`SimuMaxDegree(Bn(9)[1],257,1000,x);`):

else
 print(`There is no Help for`):

print(args):
fi:

end:


#Cn(n): [0,1]^n. Try:
#Cn(3)
Cn:=proc(n) local S,s:
option remember:

if n=0 then
 RETURN({[]}):
fi:
S:=Cn(n-1):
[seq([0,op(s)],s  in S), seq([1,op(s)],s  in S)]:
end:

#Bn(n): The canonical form of the n-dimensional unit cube, followed by the dictionary
Bn:=proc(n) local G,V,T,Neis,v,nei,i,j:


#V is the list of edges

V:=Cn(n):


#Assign an id from 1 to 2^n to each vertex so that we can use the canonical form
for i from 1 to nops(V) do
T[V[i]]:=i:
od:


G:=[]:

for i from 1 to nops(V) do

v:=V[i]:
#Find the neighbors of  V[i]

Neis:={seq([op(1..j-1,v),1-v[j],op(j+1..n,v)], j=1..n)}:

#Convert then to their IDs

Neis:={seq(T[nei], nei in Neis)}:

G:=[op(G),Neis]:
od:

G,V:

end:


#DegIG(G,S,i): Given a graph G (in canonical form i.e. where the vertices are called {1,...N}, where N=nops(G)), a subset S of {1, ...,n}
#and a vertex in S, finds the number of neighbors of i in G that also belong to S. Try:
#DegIG(Bn(3)[1],{1,3,4,5},3);
DegIG:=proc(G,S,i):
nops(G[i] intersect S):
end:


#AvDegIG(G,S): Given a graph G (in canonical form i.e. where the vertices are called {1,...N}, where N=nops(G)), a subset S of {1, ...,n}
#finds the average degree in the induced subgraph of G induced by S. Try
#DegIG(Bn(3)[1],{1,3,4,5});
AvDegIG:=proc(G,S) local s:
add(DegIG(G,S,s),s in S)/nops(S):
end:



#MaxDegIG(G,S): Given a graph G (in canonical form i.e. where the vertices are called {1,...N}, where N=nops(G)), a subset S of {1, ...,n}
#finds the average degree in the induced subgraph of G induced by S. Try
#MaxIG(Bn(3)[1],{1,3,4,5});
MaxDegIG:=proc(G,S) local s:
max(seq(DegIG(G,S,s),s in S)):
end:


#SimuMaxDegree(G,r,K,x): Inputs a graph G a positive integer r, a large positive integer K, and a variable x
#picks random subsets of size r  of the set of vertices K times and records the Maximal degree of the
#induced subgraph and returns the weight-enumerator according to that. Try:
#SimuMaxDegree(Bn(9)[1],257,1000,x);
SimuMaxDegree:=proc(G,r,K,x) local n,S,i,f:
f:=0:
n:=nops(G):

for i from 1 to K do

S:=randcomb(n,r):

f:=f+x^MaxDegIG(G,S):
od:

f:

end:


#SimuAvDegree(G,r,K): Inputs a graph G a positive integer r, a large positive integer K,
#picks random subsets of size r  of the set of vertices K times and records the Average degree of the
#induced subgraph and returns the average of the average degree and the starndard deviation
#SimuAvDegree(Bn(9)[1],257,1000);
SimuAvDegree:=proc(G,r,K) local n,S,i,L,av,sd:

n:=nops(G):

L:=[]:
for i from 1 to K do

S:=randcomb(n,r):

L:=[op(L),AvDegIG(G,S)]:
od:

av:=evalf(convert(L,`+`)):

sd:=sqrt(add((L[i]-av)^2,i=1..nops(L))/nops(L)):

[av,sd]:
end: