#OK to post
#Sam Minkin, 11/22, Assignment 21

QUESTION #1:

The number of labeled connected graphs with 50 vertices and 70 edges is given by:
L:=WtEdConGclever(51,a)
coeff(L[50],a,70)*70! gives 
6678893706496172623794219461553469915123814659073702287727314794211056297086702606937551368344081300751051325219423271670839885690607519603625245266149743695060139449497266423978528978375802880000000000000000000000 graphs

QUESTION #2:

How many labeled graphs with i connected components with 50 vertices and 70 edges are for i=2,3,...? Explain how you do it, by using the taylor command in Maple.

For k connected components, our egf, f, is:
f:=expand(log(add((a + 1)^binomial(i, 2)*x^i/i!, i = 0 .. 50 + 1))^k/k!).
Then, to get a polynomial in terms of a, we do:
f := taylor(f, x = 0, 50 + 1)
L := [seq(expand(coeff(f, x, i)*i!), i = 1 .. 50)]

Then, to get the number of labeled graphs for 50 vertices and 70 edges with i components we do:
coeff(L[50],a,70)

Doing so for i=2,3,4,5, we get:

For i=2: 2267762282072205271778791270680596849921516338574571823883456519281730035101965414722739023408444177334403072000000

For i=3:
2267762282072205271778791270680596849921516338574571823883456519281730035101965414722739023408444177334403072000000

QUESTION #3:

Results:
EstimateCutOff(30, 200): 81
FindCutOff(30, 1.05): 84

Running with M=25,50,100,200, the value of EstimateCutOff(30, M) increases to 81, so it seems to be fairly accurate.

QUESTION #4:

Running seq(evalf(FindCutOff(10*i + 20, 1.05)/(10*i + 20)), i = 0 .. 4), we get:
2.450000000, 2.800000000, 3., 3.160000000, 3.300000000

QUESTION #5:

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:

QUESTION #6:

Generalize procedure

First, we will write WtEdConGKclever(n,a,k) using the egf in the hint:

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

ProbKcomponents:=proc(n,m,k) local a:
evalf(coeff(WtEdConGKclever(n,a,k)[n],a,m)/binomial(n*(n-1)/2,m)):
end:
	
Running ProbKcomponents(40, 50, 2), we get: 0.09801230118
Running EstProbKcomps(40, 50, 2, 300) we get: 0.1300000000
They differ by 0.03198769882.