{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Asymptotics of the Erdos-Renyi model G(n,p)\n",
"\n",
"\n",
"This is a supplementary file for the paper\n",
" \n",
" \"Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae\"\n",
" by Sergey Dovgal and Khaydar Nurligareev.\n",
" \n",
"Here, you can find the code for obtaining asymptotic coefficients from Section A.5, Table 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"By the variable t, we mark connected components of a labeled graph.\n",
"
\n",
"Also, we use the parameter a = sqrt{alpha}, where alpha = 1 + p/(1-p)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Preliminary section\n",
""
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"N = 15 # Our accuracy\n",
"disp = 11 # How many terms we want to display\n",
"P. = PolynomialRing(QQ)\n",
"PP. = PolynomialRing(P)\n",
"PR. = PolynomialRing(PP)\n",
"R. = PowerSeriesRing(PR,N)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 1, a^2, a^6, a^12, a^20, a^30, a^42, a^56, a^72, a^90]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# EGF of labeled graphs (or tournaments with ties)\n",
"# we take the parameter a = sqrt{alpha}\n",
"g = sum((a^(i*(i-1)) / i.factorial()) * z^i for i in srange(N))\n",
"G = [g[i] * i.factorial() for i in srange(disp)]\n",
"G"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0,\n",
" 1,\n",
" a^2 - 1,\n",
" a^6 - 3*a^2 + 2,\n",
" a^12 - 4*a^6 - 3*a^4 + 12*a^2 - 6,\n",
" a^20 - 5*a^12 - 10*a^8 + 20*a^6 + 30*a^4 - 60*a^2 + 24,\n",
" a^30 - 6*a^20 - 15*a^14 + 20*a^12 + 120*a^8 - 90*a^6 - 270*a^4 + 360*a^2 - 120,\n",
" a^42 - 7*a^30 - 21*a^22 + 42*a^20 - 35*a^18 + 210*a^14 - 70*a^12 + 210*a^10 - 1260*a^8 + 210*a^6 + 2520*a^4 - 2520*a^2 + 720,\n",
" a^56 - 8*a^42 - 28*a^32 + 56*a^30 - 56*a^26 - 35*a^24 + 336*a^22 - 336*a^20 + 560*a^18 + 420*a^16 - 1960*a^14 - 5040*a^10 + 12810*a^8 + 3360*a^6 - 25200*a^4 + 20160*a^2 - 5040,\n",
" a^72 - 9*a^56 - 36*a^44 + 72*a^42 - 84*a^36 + 378*a^32 - 504*a^30 + 1008*a^26 + 1386*a^24 - 4536*a^22 + 5544*a^20 - 7000*a^18 - 11340*a^16 + 15120*a^14 - 2520*a^12 + 90720*a^10 - 128520*a^8 - 90720*a^6 + 272160*a^4 - 181440*a^2 + 40320,\n",
" a^90 - 10*a^72 - 45*a^58 + 90*a^56 - 120*a^48 + 720*a^44 - 930*a^42 - 126*a^40 + 1680*a^36 + 1260*a^34 - 5040*a^32 + 5040*a^30 + 5040*a^28 - 11970*a^26 - 27930*a^24 + 60480*a^22 - 105840*a^20 + 65100*a^18 + 189000*a^16 - 75600*a^14 + 201600*a^12 - 1489320*a^10 + 1247400*a^8 + 1663200*a^6 - 3175200*a^4 + 1814400*a^2 - 362880]"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# EGF of connected labeled graphs\n",
"# we take the parameter a = sqrt{alpha}\n",
"cg = log(g)\n",
"CG = [cg[i] * i.factorial() for i in srange(disp)]\n",
"CG"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816]"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The numbers of connected labeled graphs\n",
"CGsub = [cg[i][0][0].subs(a=sqrt(2)) * i.factorial() for i in srange(disp)]\n",
"CGsub"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0,\n",
" 1,\n",
" a^2 - 2,\n",
" a^6 - 6*a^2 + 6,\n",
" a^12 - 8*a^6 - 6*a^4 + 36*a^2 - 24,\n",
" a^20 - 10*a^12 - 20*a^8 + 60*a^6 + 90*a^4 - 240*a^2 + 120,\n",
" a^30 - 12*a^20 - 30*a^14 + 70*a^12 + 360*a^8 - 390*a^6 - 1080*a^4 + 1800*a^2 - 720,\n",
" a^42 - 14*a^30 - 42*a^22 + 126*a^20 - 70*a^18 + 630*a^14 - 420*a^12 + 630*a^10 - 5040*a^8 + 1680*a^6 + 12600*a^4 - 15120*a^2 + 5040,\n",
" a^56 - 16*a^42 - 56*a^32 + 168*a^30 - 112*a^26 - 70*a^24 + 1008*a^22 - 1344*a^20 + 1680*a^18 + 1260*a^16 - 8400*a^14 + 1680*a^12 - 20160*a^10 + 64680*a^8 + 10080*a^6 - 151200*a^4 + 141120*a^2 - 40320,\n",
" a^72 - 18*a^56 - 72*a^44 + 216*a^42 - 168*a^36 + 1260*a^32 - 2016*a^30 + 3024*a^26 + 4158*a^24 - 18144*a^22 + 22680*a^20 - 28560*a^18 - 45360*a^16 + 90720*a^14 - 20160*a^12 + 453600*a^10 - 793800*a^8 - 483840*a^6 + 1905120*a^4 - 1451520*a^2 + 362880,\n",
" a^90 - 20*a^72 - 90*a^58 + 270*a^56 - 240*a^48 + 2160*a^44 - 3300*a^42 - 252*a^40 + 5040*a^36 + 3780*a^34 - 22680*a^32 + 25200*a^30 + 15120*a^28 - 51030*a^26 - 115920*a^24 + 302400*a^22 - 483840*a^20 + 361200*a^18 + 982800*a^16 - 756000*a^14 + 1058400*a^12 - 8958600*a^10 + 9298800*a^8 + 11037600*a^6 - 25401600*a^4 + 16329600*a^2 - 3628800]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# EGF of irreducible labeled tournaments with ties\n",
"# we take the parameter a = sqrt{alpha}\n",
"it = 1 - 1/g\n",
"IT = [it[i] * i.factorial() for i in srange(disp)]\n",
"IT"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 1, 0, 2, 24, 544, 22320, 1677488, 236522496, 64026088576, 33832910196480]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The numbers of irreducible labeled tournaments\n",
"ITsub = [it[i][0][0].subs(a=sqrt(2)) * i.factorial() for i in srange(disp)]\n",
"ITsub"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Principal section\n",
""
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"# How many terms we want to display\n",
"disp = 7"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,\n",
" t,\n",
" t^2 + (a^2 - 1)*t,\n",
" t^3 + (3*a^2 - 3)*t^2 + (a^6 - 3*a^2 + 2)*t,\n",
" t^4 + (6*a^2 - 6)*t^3 + (4*a^6 + 3*a^4 - 18*a^2 + 11)*t^2 + (a^12 - 4*a^6 - 3*a^4 + 12*a^2 - 6)*t,\n",
" t^5 + (10*a^2 - 10)*t^4 + (10*a^6 + 15*a^4 - 60*a^2 + 35)*t^3 + (5*a^12 + 10*a^8 - 30*a^6 - 45*a^4 + 110*a^2 - 50)*t^2 + (a^20 - 5*a^12 - 10*a^8 + 20*a^6 + 30*a^4 - 60*a^2 + 24)*t,\n",
" t^6 + (15*a^2 - 15)*t^5 + (20*a^6 + 45*a^4 - 150*a^2 + 85)*t^4 + (15*a^12 + 60*a^8 - 105*a^6 - 270*a^4 + 525*a^2 - 225)*t^3 + (6*a^20 + 15*a^14 - 35*a^12 - 180*a^8 + 175*a^6 + 495*a^4 - 750*a^2 + 274)*t^2 + (a^30 - 6*a^20 - 15*a^14 + 20*a^12 + 120*a^8 - 90*a^6 - 270*a^4 + 360*a^2 - 120)*t]"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# EGF of labeled graphs within the Erdös-Rényi model, \n",
"# with the marking variable t for connected components\n",
"# we take the parameter a = sqrt{alpha}\n",
"gt = exp(t*cg)\n",
"GT = [gt[i] * i.factorial() for i in srange(disp)]\n",
"GT"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,\n",
" t,\n",
" t^2 + t,\n",
" t^3 + 3*t^2 + 4*t,\n",
" t^4 + 6*t^3 + 19*t^2 + 38*t,\n",
" t^5 + 10*t^4 + 55*t^3 + 230*t^2 + 728*t,\n",
" t^6 + 15*t^5 + 125*t^4 + 825*t^3 + 5098*t^2 + 26704*t]"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# EGF of labeled graphs within the Erdös-Rényi model with p = 1/2,\n",
"# with the marking variable t for connected components\n",
"# we take the parameter a = sqrt{2}\n",
"GTsub = [sum(gt[i][0][k].subs(a=sqrt(2)) * i.factorial() * t^k for k in srange(N)) for i in srange(disp)]\n",
"GTsub"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[t,\n",
" (a^2*t^2 - a^2*t)*w,\n",
" (a^4*t^3 + (a^6 - 3*a^4)*t^2 + (-a^6 + 2*a^4)*t)*w^2,\n",
" (a^6*t^4 + (3*a^8 - 6*a^6)*t^3 + (a^12 - 9*a^8 + 11*a^6)*t^2 + (-a^12 + 6*a^8 - 6*a^6)*t)*w^3,\n",
" (a^8*t^5 + (6*a^10 - 10*a^8)*t^4 + (4*a^14 + 3*a^12 - 36*a^10 + 35*a^8)*t^3 + (a^20 - 12*a^14 - 9*a^12 + 66*a^10 - 50*a^8)*t^2 + (-a^20 + 8*a^14 + 6*a^12 - 36*a^10 + 24*a^8)*t)*w^4,\n",
" (a^10*t^6 + (10*a^12 - 15*a^10)*t^5 + (10*a^16 + 15*a^14 - 100*a^12 + 85*a^10)*t^4 + (5*a^22 + 10*a^18 - 60*a^16 - 90*a^14 + 350*a^12 - 225*a^10)*t^3 + (a^30 - 15*a^22 - 30*a^18 + 110*a^16 + 165*a^14 - 500*a^12 + 274*a^10)*t^2 + (-a^30 + 10*a^22 + 20*a^18 - 60*a^16 - 90*a^14 + 240*a^12 - 120*a^10)*t)*w^5,\n",
" (a^12*t^7 + (15*a^14 - 21*a^12)*t^6 + (20*a^18 + 45*a^16 - 225*a^14 + 175*a^12)*t^5 + (15*a^24 + 60*a^20 - 185*a^18 - 450*a^16 + 1275*a^14 - 735*a^12)*t^4 + (6*a^32 + 15*a^26 - 80*a^24 - 360*a^20 + 610*a^18 + 1575*a^16 - 3375*a^14 + 1624*a^12)*t^3 + (a^42 - 18*a^32 - 45*a^26 + 135*a^24 + 660*a^20 - 835*a^18 - 2250*a^16 + 4110*a^14 - 1764*a^12)*t^2 + (-a^42 + 12*a^32 + 30*a^26 - 70*a^24 - 360*a^20 + 390*a^18 + 1080*a^16 - 1800*a^14 + 720*a^12)*t)*w^6]"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# CGF of labeled graphs within the Erdös-Rényi model,\n",
"# with the marking variable t for connected components\n",
"# we take the parameter a = sqrt{alpha}\n",
"qgt = t * exp((t-1) * cg.subs(z = a^2*z*w))\n",
"QGT = [qgt[i] * i.factorial() for i in srange(disp)]\n",
"QGT"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[t,\n",
" 2*t^2*w - 2*t*w,\n",
" 4*t^3*w^2 - 4*t^2*w^2,\n",
" 32/3*t^4*w^3 + 32/3*t^2*w^3 - 64/3*t*w^3,\n",
" 128/3*t^5*w^4 + 256/3*t^4*w^4 + 896/3*t^3*w^4 + 1792/3*t^2*w^4 - 1024*t*w^4,\n",
" 4096/15*t^6*w^5 + 4096/3*t^5*w^5 + 20480/3*t^4*w^5 + 94208/3*t^3*w^5 + 1630208/15*t^2*w^5 - 2228224/15*t*w^5,\n",
" 131072/45*t^7*w^6 + 131072/5*t^6*w^6 + 1703936/9*t^5*w^6 + 11927552/9*t^4*w^6 + 424411136/45*t^3*w^6 + 810549248/15*t^2*w^6 - 65011712*t*w^6]"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# CGF of labeled graphs within the Erdös-Rényi model with p = 1/2,\n",
"# with the marking variable t for connected components\n",
"# we take the parameter a = sqrt{2}\n",
"QGTsub = [sum(sum(qgt[i][j][k].subs(a=sqrt(2)) * 2**(i*(i-1)/2) * t^k * w^j for k in srange(N)) for j in srange(N)) for i in srange(disp)]\n",
"QGTsub"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 0, 0, 0, 0, 0, 0],\n",
" [1,\n",
" -1,\n",
" -a^2 + 2,\n",
" -a^6 + 6*a^2 - 6,\n",
" -a^12 + 8*a^6 + 6*a^4 - 36*a^2 + 24,\n",
" -a^20 + 10*a^12 + 20*a^8 - 60*a^6 - 90*a^4 + 240*a^2 - 120,\n",
" -a^30 + 12*a^20 + 30*a^14 - 70*a^12 - 360*a^8 + 390*a^6 + 1080*a^4 - 1800*a^2 + 720],\n",
" [0,\n",
" 1,\n",
" a^2 - 3,\n",
" a^6 - 9*a^2 + 11,\n",
" a^12 - 12*a^6 - 9*a^4 + 66*a^2 - 50,\n",
" a^20 - 15*a^12 - 30*a^8 + 110*a^6 + 165*a^4 - 500*a^2 + 274,\n",
" a^30 - 18*a^20 - 45*a^14 + 135*a^12 + 660*a^8 - 835*a^6 - 2250*a^4 + 4110*a^2 - 1764],\n",
" [0,\n",
" 0,\n",
" 1,\n",
" 3*a^2 - 6,\n",
" 4*a^6 + 3*a^4 - 36*a^2 + 35,\n",
" 5*a^12 + 10*a^8 - 60*a^6 - 90*a^4 + 350*a^2 - 225,\n",
" 6*a^20 + 15*a^14 - 80*a^12 - 360*a^8 + 610*a^6 + 1575*a^4 - 3375*a^2 + 1624],\n",
" [0,\n",
" 0,\n",
" 0,\n",
" 1,\n",
" 6*a^2 - 10,\n",
" 10*a^6 + 15*a^4 - 100*a^2 + 85,\n",
" 15*a^12 + 60*a^8 - 185*a^6 - 450*a^4 + 1275*a^2 - 735],\n",
" [0, 0, 0, 0, 1, 10*a^2 - 15, 20*a^6 + 45*a^4 - 225*a^2 + 175],\n",
" [0, 0, 0, 0, 0, 1, 15*a^2 - 21]]"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Refined coefficients of the CGF of labeled graphs within the Erdös-Rényi model (Section A.5, Table 3)\n",
"# we take the parameter a = sqrt{alpha}\n",
"QGTmatrixFact = [[qgt[i][i][j] * i.factorial() / a^(2*i) for i in srange(disp)] for j in srange(disp)]\n",
"QGTmatrixFact"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 9.0",
"language": "sage",
"name": "sagemath"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}