Wright constants for connected graph enumeration

edit · history · discussion · files · long url · combinatorics generating function

Numbers

$k$

$\rho_k$

0.6266570686577501256039413212027613132517466851524845791574808940855734136519604937366489595945143165

5/24

0.04895758348888672856280791571896572759779270977753785774667819485043542294155941357317569996832143098

221/24192

0.001440678889126093835311795436521647713164212553349421334732978129713334060519847326502305754276125443

16565/83026944

0.00002488530441736540965177656202904500171767969692649061030417838241160086356996066525225880189930359609

51281261/18021496356864

3.021607918157577634613629168469447773913869296980984351897217753012124166454616503495567532531534959e-7

12188095/405116714483712

10:

2.829889156668449498654230171781235398511912319809836383109184237827433798010143911031981790214638236e-9

11:

17917174074467/70829601670880286474240

Definition

Let $C(n,m)$ count simple connected graphs on the labelled vertex set $\{1,\ldots,n\}$ with $m$ edges. For each fixed integer $k\geq-1$, Wright's constant $\rho_k$ is defined by $C(n,n+k)\sim\rho_k n^{n+(3k-1)/2}$ as $n\to\infty$ [1].

Parameters

$k$

— graph excess ($k\geq-1$)

Formulas

(1)

Cayley's formula gives $C(n,n-1)=n^{n-2}$ and $\rho_{-1}=1$ [1], Section 4.

(2)

Define $K_0=-\tfrac12$ and $K_j=\frac{3j-4}{4}K_{j-1}+\sum_{i=1}^{j-1}K_iK_{j-i}$ for $j\geq1$. The empty sum is zero [1], equation (7).

(3)

$\displaystyle \rho_k=\frac{2^{(3-k)/2}\sqrt{\pi}}{\Gamma((3k+2)/2)}K_{k+1}\quad(k\geq-1)$ [1], equations (6), (21), (36) and (37).

(4)

$\displaystyle \rho_k=\frac{\mathbb E[A^{k+1}]}{(k+1)!}\quad(k\geq-1)$, where $A$ is the standard Brownian excursion area defined in (8) [1], equation (36).

(5)

$\rho_0=\sqrt{2\pi}/4$, $\rho_1=5/24$, $\rho_2=5\sqrt{2\pi}/256$, and $\rho_3=221/24192$ [1], Table 1.

Comments

(6)

Graph excess is $k=m-n$, where $m$ is the number of edges and $n$ the number of vertices. A connected graph has $k+1$ independent cycles. Thus $k=-1$ corresponds to trees and $k=0$ to unicyclic graphs. Graphs have neither loops nor multiple edges, and no embedding is counted [1].

(7)

For odd $k\geq1$, $\rho_k$ is rational. For even $k\geq0$, it is a rational multiple of $\sqrt{2\pi}$, with the positive square root. This follows by reducing the integer and half-integer Gamma factors in (3).

(8)

Let $e(t)$ be the standard Brownian excursion of duration one, obtained from Brownian motion with variance $t$ and generator $\tfrac12 d^2/dx^2$, and put $A=\int_0^1 e(t)\,dt$. Its moments give the same constants by (4), a relation proved by Spencer and presented in [1], Section 5.

Programs

(P1)

Sage

import numberdb.sage as numberdb
from sage.rings.rational_field import QQ
from sage.rings.real_arb import RealBallField
R = RealBallField(512)
K = [QQ(-1)/2]
for j in range(1, 13):
    K.append(QQ(3*j-4)/4*K[j-1] + sum(K[i]*K[j-i] for i in range(1,j)))
for k in range(12):
    print(k, R(2)**(QQ(3-k)/2)*R.pi().sqrt()*K[k+1]/R(QQ(3*k+2)/2).gamma())

References

[1]

S. Janson, Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas, Probability Surveys 4 (2007), 80–145. Sections 2, 4–5 and 8–10. (arXiv) (doi)

Links

[2]

Janson: Brownian excursion area and Wright constants

Similar tables

Growth constants of the classes of planar graphs — asymptotic constants for labelled planar graph classes with unrestricted numbers of edges; Wright constants instead fix the graph excess

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds every excess $0\leq k\leq11$, a short initial reference for connected graphs with one through twelve independent cycles; the upper bound is editorial, and the tree value $\rho_{-1}=1$ is stated as a formula)

How they were obtained:

The recurrence coefficients are computed over the rational numbers. Integer and half-integer Gamma factors are simplified exactly, giving exact rational entries for odd excess and rational multiples of the positive square root of $2\pi$ for even excess. Arb encloses the even-excess values at 512 bits before writing 100 significant decimal digits. The minimum measured accuracy is 509 bits, and the written decimal intervals contain the computation balls.

An independent calculation takes the formal logarithm of the graph generating series in [1], equations (62)–(65), and converts its coefficients using equation (34). All twelve rational factors agree exactly. The first four values match the paper's Table 1; direct enumeration of labelled graphs through five vertices verifies the tree and unicyclic counting conventions. The attached checks also test the displayed recurrence, the direct Gamma formula, and the values read back from the database.