Combinatorics: Using the Transfer Theorem for Multiple Singularities on the class of 2-regular graphs

74 Views Asked by At

Use the Transfer Theorem for multiple singularities to derive an asymptotic expression for $G_n$, where $G_n$ is the number of vertex-labelled 2-regular (simple) graphs on the vertex set $[n]$, all whose components have even size.

REMARK: I wrote down said theorem below.

The first thing I did was to note that the class $\mathcal{G}_n$ of vertex-labelled 2-regular (simple) graphs on the vertex set $[n]$ can be described via:

$$\mathcal{G}_n = SET(UCYC_{\ge 3, \text{even}} (\mathcal{Z})),$$

where $UCYC$ denotes the undirected cylce construction and $\mathcal{Z}$ the atomic class. This yields the EGF

$$ G(z) = \exp \bigg(\frac{1}{2} \bigg[ \log \bigg( \frac{1}{1-z} \bigg) - z -\frac{z^2}{2} \bigg] \bigg) = \frac{e^{\frac{-z}{2} - \frac{z^2}{4}}}{\sqrt{1-z}}.$$

Analogously to the example of "Permutations of Odd Cycle length" in the Flajolet & Sedgewick book on page 64 I suppose that I now need to write this as a closed expression, but I do not see how to find one. Could you please give me a hint?

Transfer Theorem for multiple singularities: Consider a function $f$ that is analytic in $\lvert z \rvert < \rho$, has a finite number of singularities $\rho_1, \ldots, \rho_r$ satisfying $\lvert \rho_i \rvert = \rho$ for all $1 \le i \le r$, and is $\Delta$-analytic in some $\Delta$-domain $D_i$ at $z = \rho_i$ for each $1 \le i \le r$,

$$f(z) = A_i(z) \cdot \big(1 - \frac{z}{\rho_i} \big)^{-\alpha_i} + \mathcal{O} \big( (1-z)^{-\alpha_i-1)} \big)$$

for some $A_i(z)$ analytic at $\rho_i$. Then for each $1 \le i \le r$, the singular expansion of $f(z)$ for $z \rightarrow \rho_i$ in $D$ is given by multiplication of the Taylor Series Expansion of $A(z_i$ at $\rho_i$ and $\big(1 - \frac{z}{\rho_i} \big)^{-\alpha_i}$ as follows:

$$f(z) = \sum_{k \ge 0} \frac{ (-1)^k A_i^{(k)}(\rho_i)}{k!} \bigg(\frac{z}{\rho_i}\bigg)^{k-\alpha_i} \text{, for $z \rightarrow \rho_i$ in $D$}$$

In particular we have for each $1 \le i \le r$ that

$$f(z) = A_i(\rho_i) \cdot \bigg(1 - \frac{z}{\rho_i} \bigg)^{-\alpha_i} + \mathcal{O} \big( (1-z)^{1-\alpha_i} \big).$$

Furthermore we have

$$[z^n]f(z) = \sum_{i=1}^r A_i(\rho_i)\rho_i^{-n} \bigg[ \frac{n^{\alpha_i-1}}{\Gamma(\alpha_i)} + \mathcal{O}(n^{\alpha_i-2}) \bigg]$$ REMARK: This is a variant of a theorem in the Flajolet & Sedgewick book on page 398.

1

There are 1 best solutions below

0
On BEST ANSWER

Basically a comment. Using combinatorial classes we have the following class $\mathcal{G}$ of sets of undirected cycles of even length

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{G} = \textsc{SET}( \textsc{DHD}_{=4}(\mathcal{Z}) + \textsc{DHD}_{=6}(\mathcal{Z}) + \textsc{DHD}_{=8}(\mathcal{Z}) + \cdots).$$

This gives the EGF (the dihedral group $D_n$ has order $2n$)

$$G(z) = \sum_{n\ge 0} G_n \frac{z^n}{n!} = \exp\left( \frac{1}{2} \frac{z^4}{4} + \frac{1}{2} \frac{z^6}{6} + \frac{1}{2} \frac{z^8}{8} + \cdots\right) \\ = \exp\left( \frac{1}{4} \frac{z^4}{2} + \frac{1}{4} \frac{z^6}{3} + \frac{1}{4} \frac{z^8}{4} + \cdots\right) \\ = \exp\left(- \frac{z^2}{4} + \frac{1}{4} \log\frac{1}{1-z^2}\right) = \frac{\exp(-z^2/4)}{(1-z^2)^{1/4}}.$$

We are interested in $n! [z^n] G(z).$ Note however that these graphs have an even number of nodes so the generating function must also be even, which indeed it is. With $n=2m$ we have

$$(2m)! [z^{2m}] G(z) = (2m)! [z^m] \frac{\exp(-z/4)}{(1-z)^{1/4}}.$$

We see that we are only dealing with one singularity. We use the expansion

$$\exp(-z/4) = \exp(-1/4) + \exp(-1/4)\frac{1}{4} (1-z) + \exp(-1/4)\frac{1}{32} (1-z)^2 + \cdots$$

to get the first term in the asymptotic expansion for $G_n$,

$$(2m)! \exp(-1/4) [z^m] \frac{1}{(1-z)^{1/4}} = (2m)! \exp(-1/4) (-1)^m {-1/4\choose m} \\ = (2m)! \exp(-1/4) {m-3/4\choose m}.$$

Using the standard asymptotics of the binomial coefficient as given e.g. on page 180 of Wilf's generatingfunctionology this becomes

$$(2m)! \exp(-1/4) \frac{m^{-3/4}}{\Gamma(1/4)} = (2m)! \exp(-1/4) m^{-3/4} \Gamma(3/4) \sin(\pi/4) \frac{1}{\pi} \\ = (2m)! \exp(-1/4) \frac{1}{\sqrt{2}\pi} \Gamma(3/4) m^{-3/4} = (2m)! \exp(-1/4) 2^{1/4} \frac{\Gamma(3/4)}{(2m)^{3/4} \pi}.$$

These data are from OEIS A202065.