#OK to post
#Soham Palande, Assignment 21, 11/22/2020


#PART 1

How many labeled connected graphs with 50 vertices and 70 edges are?

L:=WtEdConGclever(50,a):

coeff(L[50],a,70)
557570125262936299552095051452832858951958306952392379552719516748979534894703561052813706583449695070191616000000


#PART 2

Using the egf of labeled graphs with n vertices and k components and keeping track of the number of edges 

f:=(log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^k/k!

Then taking the Taylor expansion and coeff of x^50 since we have 50 vertices

coeff(taylor(f,x=0,51),x,50)

Then substituting i=2,3,4,5 for k, and taking the coeff of a^70 since we have 70 edges.

i=2:

f:=(log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^2/2!):

coeff(coeff(taylor(f,x=0,51),x,50)*50!,a,70);
2267762282072205271778791270680596849921516338574571823883456519281730035101965414722739023408444177334403072000000
 
i=3:

f:=(log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^3/3!):

coeff(coeff(taylor(f,x=0,51),x,50)*50!,a,70);
4084614615513849564059280183743190588234377301848961646892154560205839868330317696952259164363869748482983526400000


i=4:

f:=(log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^4/4!):

coeff(coeff(taylor(f,x=0,51),x,50)*50!,a,70);
4336520950646656327224993268880264842114984745013581637572959168612209444462829083123209142308423023328834795520000


i=5:

f:=(log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^5/5!):

coeff(coeff(taylor(f,x=0,51),x,50)*50!,a,70);
3046643850794698885807347271650949921058341236747610399052555568087884858386903803880100124793197196674954096998400


#PART 3


#A graph with n vertices must have at least n-1 edges to be connected. So we iterate from n-1 to nC2

#FROM HW 18


AveNuCC:=proc(n,K,M) local sum,G,avg,i:
sum:=0:
avg:=0:
for i from 1 to M do
    G:=RandGr(n,K):
    sum:=sum+nops(CCs(G)):
od:
avg:=sum/M:
end:

EstimateCutOff:=proc(n,M) local max,i:
max:=binomial(n,2):
for i from n-1 to max do:
    if (AveNuCC(n,i,M)<1.05) then:
           break;
    fi:
od:
i:
end:

#Example - took a long time to compute

EstimateCutOff(30,1000) 
84


#Compare with FindCutOff(30,1.05)

FindCutOff(30,1.05)
84

#Exact!!!


#PART 4


evalf(FindCutOff(20,1.05)/20)  	//49
2.450000000			35

evalf(FindCutOff(30,1.05)/30)  	//84
2.800000000			36

evalf(FindCutOff(40,1.05)/40)  	//120
3.				38

evalf(FindCutOff(50,1.05)/50)  	//158
3.160000000			40


evalf(FindCutOff(60,1.05)/60)  	//198
3.300000000

#The number of connected components increases by 35, 36, 38, 40...


#PART 5


#EstProbKcomps(n,m,k,N): estimates that the probability that a random  graph on n vertices with m edges hs k connected #components by simulating N times. 
#Try:
#EstProbKcomps:=proc(n,m,k,N) local i,co, G:

co:=0:

for i from 1 to N do

G:=RandGr(n,m):

if nops(CCs(G))=k then
 co:=co+1:
fi:

od:

evalf(co/N):
end:


#Comparison

EstProbKcomps(30,70,1,1000);
.8640000000

EstProbConn(30,70,1000)
.8540000000



#PART 6

#Modified WtEdConGclever(N,a) to WtEdKConCompGclever(N,a,k) below

#WtEdKConCompGclever(N,a,k): The first N terms of the sequence of
#generating functios of the set "connected (labeled) graphs with n #vertices and k components" according to the weight a^number of edges

WtEdKConCompGclever:=proc(N,a,k) local f,i,x:
option remember:
f:=(log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^k/k!):
f:=taylor(f,x=0,N+1):
[seq(expand(coeff(f,x,i)*i!),i=1..N)]:
end:

#Modified ProbConn(n,m) to ProbKcomponents(n,m,k) below using modified generating function

#ProbKcomponents(n,m,k): The probability that a random labeled graph on vertices and m edges is connected.
ProbKcomponents:=proc(n,m,k)  local a:
evalf(coeff(WtEdKConCompGclever(n,a,k)[n],a,m)/binomial(n*(n-1)/2,m)):
end:

#Comparison with EstProbKcomps

ProbKcomponents(40,50,2)
0.9801230118e-1

EstProbKcomps(40,50,2,300)
.1000000000