# Chordal graphs with bounded tree-width

Jordi Castellví  Michael Drmota  Marc Noy  Clément Requilé

###### Abstract

Given $t\geq 2$ and $0\leq k\leq t$, we prove that the number of labelled
$k$-connected chordal graphs with $n$ vertices and tree-width at most $t$ is
asymptotically $cn^{-5/2}\gamma^{n}n!$, as $n\to\infty$, for some constants
$c,\gamma>0$ depending on $t$ and $k$. Additionally, we show that the number
of $i$-cliques ($2\leq i\leq t$) in a uniform random $k$-connected chordal
graph with tree-width at most $t$ is normally distributed as $n\to\infty$.

The asymptotic enumeration of graphs of tree-width at most $t$ is wide open
for $t\geq 3$. To the best of our knowledge, this is the first non-trivial
class of graphs with bounded tree-width where the asymptotic counting problem
is solved. Our starting point is the work of Wormald [Counting Labelled
Chordal Graphs, Graphs and Combinatorics (1985)], were an algorithm is
developed to obtain the exact number of labelled chordal graphs on $n$
vertices.

##  1 Introduction

Tree-width is a fundamental parameter in structural and algorithmic graph
theory, as illustrated for instance in [CFKLMPPS15]. It can be defined in
terms of tree-decompositions or equivalently in terms of $k$-trees. A $k$-tree
is defined recursively as either a complete graph on $k+1$ vertices or a graph
obtained by adjoining a new vertex adjacent to a $k$-clique of a $k$-tree. The
tree-width of a graph $\Gamma$ is the minimum $k$ such that $\Gamma$ is a
subgraph of a $k$-tree. In particular, $k$-trees are the maximal graphs with
tree-width at most $k$. The number of $k$-trees on $n$ labelled vertices was
independently shown [BP69, M69] to be

$\binom{n}{k}(k(n-k)+1)^{n-k-2}=\frac{1}{\sqrt{2\pi}\,k!\,k^{k+2}}\,n^{-5/2}\,(ek)^{n}\,n!\,(1+o(1)),$
(1)

where the estimate holds for $k$ fixed and $n\to\infty$. However, there are
relatively few results on the enumeration of graphs of given tree-width or on
properties of random graphs with given tree-width. Graphs of tree-width one
are forests (acyclic graphs) and their enumeration is a classical result,
while graphs of tree-width at most two are series-parallel graphs and were
first counted in [BGKN07]. The problem of counting graphs of tree-width three
is still open. From now on, we will use $t$ to denote the tree-width while $k$
will denote the connectivity of a graph. All graphs we consider are labelled.

Given that tree-width is non-increasing under taking minors, the class of
graphs with tree-width at most $t$ is ‘small’ when $t$ is fixed, in the sense
that the number $g_{n,t}$ of labelled graphs with $n$ vertices and tree-wdith
at most $t$ grows at most like $c^{n}n!$ for some $c>0$ depending on $t$ (see
[NSTW06, DN10]). The best bounds known for $g_{n,t}$ are, up to lower order
terms,

$\left(\frac{2^{t}tn}{\log t}\right)^{n}\leq g_{n,t}\leq(2^{t}tn)^{n}.$

The upper bound follows by considering all possible subgraphs of $t$-trees,
and the lower bound uses a suitable construction developed in [BNS18]. In the
present work we determine the asymptotic number of labelled chordal graphs
with tree-width at most $t$, following the approach in [FS09] and [D09], and
based on the analysis of systems of equations satisfied by generating
functions.

A graph is chordal if every cycle of length greater than three contains at
least one chord, that is, an edge connecting non-consecutive vertices of the
cycle. Chordal graphs have been extensively studied in structural graph theory
and graph algorithms (see for instance [G04]), but not so much from the point
of view of enumeration. Wormald [W85] used generating functions to develop a
method for finding the exact number of chordal graphs with $n$ vertices for a
given value of $n$. It is based on decomposing chordal graphs into
$k$-connected components for each $k\geq 1$. As remarked in [W85], it is
difficult to define the $k$-connected components of arbitrary graphs for
$k>3$, but for chordal graphs they are well defined. Wormald introduces
generating functions $C_{k}(x)$ for $k$-connected chordal graphs and finds an
equation linking $C_{k}(x)$ and $C_{k+1}(x)$ reflecting the decomposition into
$k$-connected components. This is precisely the starting point of our work.

An important parameter in [W85] is the size $w$ of the largest clique. For
chordal graphs one can show that the tree-width is equal to $w-1$, hence
bounding the tree-width by $t$ is the same as bounding $w$ by $t+1$. The
parameter $w$ also plays a substantial rôle in showing that almost all chordal
graphs are split graphs [BRW85], which in turn implies that the number of
chordal graphs with $n$ vertices is of order $2^{n^{2}/4}(1+o(1))$.

For fixed $n,t\geq 1$ and $0\leq k\leq t$, let $\mathcal{G}_{t,k,n}$ be the
set of $k$-connected chordal graphs with $n$ labelled vertices and tree-width
at most $t$. Our two main results are the following.

######  Theorem 1.1.

For $t\geq 1$ and $0\leq k\leq t$, there exist constants $c_{t,k}>0$ and
$\gamma_{t,k}\in(0,1)$ such that

$|\mathcal{G}_{t,k,n}|=c_{t,k}\,n^{-5/2}\,\gamma_{t,k}^{n}\,n!\,(1+o(1))\qquad\text{as
}n\to\infty.$

Remark that by setting $t=k$ in Theorem 1.1 one recovers the general form of
the asymptotic estimate of the number of $k$-trees (1). The fact that
$\gamma_{k,k}=ek$ is reproven in Section 3. In principle, for fixed $t$ and
$k$ the constants $c_{t,k}$ and $\gamma_{t,k}$ can be computed, at least
approximately. Table 1 in Section 4 displays approximations of
$1/\gamma_{t,k}$ for $1\leq k\leq t\leq 7$.

######  Theorem 1.2.

Let $t\geq 1$, $0\leq k\leq t$. For $i\in\\{2,\ldots,t\\}$ let $X_{n,i}$
denote the number of $i$-cliques in a uniform random graph in
$\mathcal{G}_{t,k,n}$, and set ${\bf X_{n}}=(X_{n,2},\ldots,X_{n,t})$. Then
${\bf X_{n}}$ satisfies a multivariate central limit theorem, that is, as
$n\to\infty$ we have

$\frac{1}{\sqrt{n}}\left({\bf X}_{n}-\mathbb{E}\,{\bf
X}_{n}\right)\overset{d}{\to}N(0,\Sigma),\qquad\text{with}\quad\mathbb{E}\,{\bf
X}_{n}\sim\alpha n\quad\mbox{and}\quad\mathbb{C}\mathrm{ov}\,{\bf
X}_{n}\sim\Sigma n,$

and where $\alpha$ is a $(t-1)$-dimensional vector of positive numbers and
$\Sigma$ is a $(t-1)\times(t-1)$-dimensional positive semi-definite matrix.

Let us mention that more structural asymptotic results can be expected.
Notably, the class of chordal graphs with tree-width at most $t$ is
subcritical in the sense of [DFKKR11], as further discussed in the concluding
Section 4. It follows from [PSW16] that the uniform random connected chordal
graph with tree-width at most $t$ with distances rescaled by $1/\sqrt{n}$
admits the Continuum Random Tree (CRT) [A91] as a scaling limit, multiplied by
a constant that depends on $t$.

The proofs of Theorems 1.1 and 1.2 are based on a recursive decomposition of
chordal graphs translated in the combinatorial language of generating
functions, the so-called symbolic method [FS09], into a system of functional
equations explicited in Section 2 and analysed in Section 3 by means of
analytic methods [FS09]. More precisely, in Section 2.1 we show the unicity of
the decomposition of chordal graphs into their $k$-connected components. This
is translated in Section 2.2 into a system of funtional equations satisfied by
exponential generating functions encoding the numbers of graphs in each class.
In Section 2.3 we prove an alternative encoding of an integral operator, which
is instrumental for computing the numerical values in Table 1. The subsequent
asymptotic analysis is rather delicate as it involves singularity functions
depending on several variables. Our notions of proper and fully movable
singularity functions are key ingredients, and are defined along several
technical notions in Section 3.1. Some useful propeties are proven in Section
3.2, before embarking in the proofs of the main results in Section 3.3.

##  2 Decomposition of chordal graphs

All graphs considered in this work will be simple and labelled, that is with
vertex-set $[n]$. Let $\Gamma$ be a graph and $k\geq 1$. A $k$-separator of
$\Gamma$ is a subset of $k$ vertices whose removal disconnects $\Gamma$. The
graph $\Gamma$ is said to be $k$-connected if it contains no $i$-separator for
$i\in[k-1]$. Notice that with this definition we consider the complete graph
on $k$ vertices to be $k$-connected, for any $k\geq 1$, contrary to the usual
definition of connectivity (see for instance [D16]). A $k$-connected component
of $\Gamma$ is a $k$-connected subgraph that is maximal, in term of subgraph
containment, with that property.

An essential consequence of chordality is that $k$-connected chordal graphs
admit a unique decomposition into $(k+1)$-connected components through its
$k$-separators. This is the subject of the next section.

###  2.1 Unicity of the components

The following well-known result will play a central role in our definition of
the decomposition of a chordal graph into $k$-connected components. For
completeness we provide a short proof.

######  Proposition 2.1 (Dirac [D61]).

In a chordal graph every minimal separator is a clique.

###### Proof.

Let $\Gamma$ be a chordal graph and let $S$ be a minimal separator with at
least two vertices. Suppose for contradiction that there are $u,v\in S$ such
that $uv$ is not an edge. Let $A$ and $B$ be different components of
$\Gamma-S$, and consider shortest paths $P$ and $Q$ between $x$ and $y$ whose
inner vertices are, respectively, in $A$ and $B$. Then the concatenation of
$P$ and $Q$ is a chordless cycle of length at least four, contradicting the
fact that $\Gamma$ is chordal. ∎

For the rest of this section, we fix $k\geq 1$.

######  Definition 2.2.

Let $\Gamma$ be a $k$-connected chordal graph with a $k$-separator $S$, and,
for $m\geq 1$, let $C_{1},\ldots,C_{m}$ be the (possibly empty) connected
components of $\Gamma-S$. Then, for $i\in[m]$, the induced subgraphs
$\Gamma_{i}=\Gamma[V(C_{i})\cup S]$ will be called the slices of $\Gamma$,
obtained after cutting $\Gamma$ through $S$.

Remark that by Proposition 2.1, $S$ is a clique of $\Gamma$. Furthermore, as
each slice $\Gamma_{i}$ ($i\in[m]$) contains a copy of $S$, $\Gamma$ can be
obtained by identifying together these $m$ copies of $S$. This operation will
be called gluing through $S$. The next Proposition 2.3 implies that the slices
$\Gamma_{i}$ are $k$-connected.

######  Proposition 2.3.

Let $\Gamma$ be a $k$-connected chordal graph with a $k$-separator $S$
inducing the slices $\Gamma_{1},\ldots,\Gamma_{m}$. If, for some $i\in[m]$,
$\Gamma_{i}$ has a separator $T$, then $T$ is also a separator of $\Gamma$.
Furhtermore, $T\neq S$ is a $k$-separator of $\Gamma$ if it is a separator of
the slice $\Gamma_{i}$ it belongs to.

###### Proof.

If $S\subseteq T$, the first claim is direct. Suppose now that $v\in
S\setminus T$. Then, $T$ separates $v$ from some other vertex
$w\in\Gamma_{i}$, because otherwise every vertex would be reachable from $v$
and $T$ would not be a separator. Since the vertices in $S$ form a clique, $w$
is in fact separated from all vertices in $S\setminus T$. Then, in $\Gamma$,
the same set $T$ also separates $w$ from $S\setminus T$.

For the second claim, observe that since all the vertices and edges in
$\Gamma$ are also in some $\Gamma_{i}$ and vice-versa, a set of vertices
$T\neq S$ is a subclique of $\Gamma$ if and only if it is a subclique of some
slice $\Gamma_{i}$. Now suppose to a contradiction that $\Gamma_{i}-T$ is
connected. Since, for $j\neq i$, $T$ is not entirely contained in any other
slice $\Gamma_{j}$, and $\Gamma_{j}$ is $k$-connected, it follows that
$\Gamma_{j}-T$ is also connected. In particular, every vertex in $\Gamma-T$ is
reachable from some vertex $v\in S\setminus T$, a contradiction. ∎

Consider now the set of slices obtained after cutting $\Gamma$ through all its
$k$-separators. Because they contain no $k$-separators, all these slices are
$(k+1)$-connected and form in fact the $(k+1)$-connected components of
$\Gamma$. They are well defined thanks to the following result.

######  Proposition 2.4.

Let $\Gamma$ be a $k$-connected chordal graph with $k$-separators $S$ and $T$.
Then the slices $\Gamma_{1},\ldots,\Gamma_{m}$ obtained after cutting $\Gamma$
first through $S$ then through $T$ can be characterised as follows:

  1. (i)

Let $i\in[m]$. For each connected component $C_{i}$ of $\Gamma-(S\cup T)$
there will be a slice $\Gamma_{i}$ with vertex set $V_{i}$, in such a way that
$\Gamma_{i}=\Gamma[V_{i}]$. The set $V_{i}$ contains the vertices in $C_{i}$,
and also contains the vertices of $S$ (resp. $T$) if there is some vertex in
$S\setminus T$ (resp. $T\setminus S$) that has a neighbour in $C_{i}$.

  2. (ii)

If none of the slices described in (i) contains the vertices in both $S$ and
$T$, there will be an additional slice $\Gamma_{m+1}=\Gamma[S\cup T]$, and
these are all the possible slices.

In particular, doing the cuts first through $T$ and then through $S$ results
in the same slices.

###### Proof.

We first consider the slices obtained after cutting only through $S$. For
$1\leq i\leq m_{S}$, each of the slices $\Gamma^{S}_{i}$ corresponds to a
connected component $C^{S}_{i}$ of $\Gamma-S$. Among these slices there is
only one containing $T$ as a subclique, say $\Gamma^{S}_{1}$, because the
vertices in $T\setminus S$ necessarily belong to the same component
$C^{S}_{1}$. Therefore $\Gamma^{S}_{1}$ is the unique slice that will be cut
through $T$ while the others stay unchanged. For $2\leq i\leq m_{S}$, each of
the other slices $\Gamma^{S}_{i}$ contains the vertices of $C^{S}_{i}$, which
is certainly a connected component of $\Gamma-(S\cup T)$, and the vertices in
$S$, but contains no vertex in $T\setminus S$. This agrees with $(i)$ because
all the vertices in $S$ have a neighbour in $C^{S}_{i}$, since $S$ is a
minimal separator, while the vertices in $T\setminus S$ have no neighbours in
$C^{S}_{i}$.

We now consider the slices obtained after cutting $\Gamma^{S}_{1}$ through
$T$. Again, for $1\leq i\leq m_{T}$ each of these slices corresponds to a
connected component $C^{T}_{i}$ of $\Gamma^{S}_{1}-T$, denoted by
$\Gamma^{T}_{i}$. Among these slices, there is only one containing $S$ as a
subclique, say $\Gamma^{T}_{1}$, because the vertices in $T\setminus S$
necessarily belong to the same component $C^{T}_{1}$. The rest of the slices
contain no vertex in $S\setminus T$. In fact, they are analogous to the slices
$\Gamma^{S}_{i}$, $2\leq i\leq m_{S}$, and they agree with $(i)$ for the same
reasons.

There are two possibilities for $C_{1}^{T}$: either it contains vertices other
than the ones in $S\setminus T$ or it does not. In the first case, observe
that $C^{T}_{1}-S$ is connected. Indeed, if this was not the case
$\Gamma^{S}_{1}$ would have $S\cup T$ as a separator, while neither $S$ nor
$T$ are separators. But then there would be a minimal $k$-separator of
$\Gamma^{S}_{1}$ that is not a clique, which is not possible. Therefore,
$C^{T}_{1}-S$ is a connected component of $\Gamma-(S\cup T)$, which has some
neighbour in $S\setminus T$ and also in $T\setminus S$, since $C^{S}_{1}$ is
connected. This also agrees with $(i)$. On the other hand, if $C^{T}_{1}$
contains no vertices other than the ones in $S\setminus T$, then it is not a
component of $\Gamma-(S\cup T)$ and we are in the case $(ii)$.

Since this characterisation does not depend on the order of the cuts, the last
claim follows. ∎

The $k$-connected components of $\Gamma$ are thus the maximal $k$-connected
subgraphs, since, for $i\in[k-1]$, there is a single way of cutting through
all the $i$-separators. And we can uniquely define the $2$-connected
components of a connected chordal graph, the $3$-connected components of these
$2$-connected components, the $4$-connected components of these $3$-connected
components, and so on. An illustration is given in Figure 1.

Figure 1: Decomposition of a connected graph with tree-width 3 into its 2, 3
and 4-connected components. Vertices with the same label are identified.

This decomposition is the generalisation of the well-known decomposition of a
connected graph into blocks (i.e. maximal 2-connected components). And it
induces, as shown in the next section, a system of functional equations
satisfied by the generating function counting chordal graphs of tree-width at
most $k$.

###  2.2 Functional equations for the generating functions

For the rest of this section, we fix some $t\geq 1$ and let $\mathcal{G}$ be
the family of chordal graphs with tree-width at most $t$. For a graph
$\Gamma\in\mathcal{G}$ and $j\in[t]$, let us denote by $n_{j}(\Gamma)$ the
number of $j$-cliques of $\Gamma$. In the rest of the paper, we will write
$\mathbf{x}$ as a short-hand for $x_{1},\ldots,x_{t}$, and define the
multivariate (exponential) generating function associated to $\mathcal{G}$ to
be

$G(\mathbf{x})=G(x_{1},\dots,x_{t})=\sum_{\Gamma\in\mathcal{G}}\frac{1}{n_{1}(\Gamma)!}\prod_{j=1}^{t}x_{j}^{n_{j}(\Gamma)},$

Let $g_{n}$ denote the number of chordal graphs with $n$ vertices and tree-
width at most $t$. Then,

$G(x,1,\dots,1)=\sum_{n\geq 1}\frac{g_{n}}{n!}x^{n}.$

For $0\leq k\leq t+1$, let $\mathcal{G}_{k}$ be the family of $k$-connected
chordal graphs with tree-width at most $t$ and $G_{k}(\mathbf{x})$ be the
associated generating function. In particular, we have

$G_{t+1}(\mathbf{x})=\frac{1}{(t+1)!}\prod_{j\in[t]}x_{j}^{\binom{t+1}{j}}.$
(2)

For other values of $k$, we need to consider graphs rooted at a clique.
Rooting the graph $\Gamma\in\mathcal{G}_{k}$ at an $i$-clique means
distinguishing one $i$-clique $K$ of $\Gamma$ and choosing an ordering of (the
labels of) the vertices of $K$. In order to avoid over-counting, we will
discount the subcliques of $K$. Let $i\in[k]$ and define
$\mathcal{G}_{k}^{(i)}$ to be the family of $k$-connected chordal graphs with
tree-width at most $t$ and rooted at an $i$-clique. Let then
$G_{k}^{(i)}(\mathbf{x})$ be the associated generating function, where now for
$1\leq j\leq i$ the variables $x_{j}$ mark the number of $j$-cliques that are
not subcliques of the root.

Figure 2: Recursive decomposition of a $k$-connected chordal graph into
$(k+1)$-connected components.

######  Lemma 2.5.

Let $k\in[t]$. Then the following equations hold:

$\displaystyle G_{k+1}^{(k)}(\mathbf{x})$
$\displaystyle=k!\prod_{j=1}^{k-1}x_{j}^{-\binom{k}{j}}\frac{\partial}{\partial
x_{k}}G_{k+1}(\mathbf{x}),$ (3) $\displaystyle G_{k}^{(k)}(\mathbf{x})$
$\displaystyle=\exp\left(G_{k+1}^{(k)}\big{(}x_{1},\ldots,x_{k-1},x_{k}G_{k}^{(k)}(\mathbf{x}),x_{k+1},\ldots,x_{t}\big{)}\right),$
(4) $\displaystyle G_{k}(\mathbf{x})$
$\displaystyle=\frac{1}{k!}\prod_{j=1}^{k-1}x_{j}^{\binom{k}{j}}\int
G_{k}^{(k)}(\mathbf{x})\,\,dx_{k}.$ (5)

###### Proof.

As per the symbolic method, taking the derivative of a generating function
with respect to the variable $x_{i}$ amounts to rooting a graph at an
$i$-clique, while taking the integral will correspond to “unrooting”. Thus,
both Equations (3) and (5) follow from the definition.

On the other hand, Equation (4) is derived from the decomposition of
$k$-connected chordal graphs into their $(k+1)$-connected components, and is
illustrated in Figure 2. Indeed, a $k$-connected chordal graph rooted at a
$k$-clique $K$ is obtained by gluing through $K$ a set of $(k+1)$-connected
graphs $\Gamma_{1},\ldots,\Gamma_{m}$ containg $K$, and then further gluing
some $k$-connected chordal graph at each $k$-clique of $\Gamma_{i}$, other
than $K$, for all $i\in[m]$. Recall that the $k$-clique is itself considered
to be $k$-connected. The substitution of $x_{k}$ by $x_{k}G_{k}^{(k)}$ in
Equation (4) reflects the recursive process of gluing through $k$-cliques.
Finally, the fact that the graphs are rooted at ordered cliques ensures that
the gluing process is made in all possible ways. ∎

Finally, the fact that a graph is the set of its connected components can be
translated as

$G(\mathbf{x})=G_{0}(\mathbf{x})=\exp(G_{1}(\mathbf{x})),$

Observe then that one can derive $G_{0}(\mathbf{x})$ from
$G_{t+1}(\mathbf{x})$ by successively using Identities (3), (4) and (5) from
Lemma 2.5, as illustrated in Figure 3. Furthermore, in the steps where
Identity (5) is used, one needs to compute a formal integral. An alternative
is to use the dissymmetry theorem for tree-decomposable classes, as presented
in Proposition 2.6. This is the purpose of the next section.

$\displaystyle G_{t+1}\rightarrow\,\,$ $\displaystyle G_{t+1}^{(t)}$
$\displaystyle\downarrow$ $\displaystyle G_{t}^{(t)}\rightarrow
G_{t}\rightarrow\,\,G_{t}^{(t-1)}$ $\displaystyle\hskip 68.28644pt\downarrow$
$\displaystyle\hskip 68.28644ptG_{t-1}^{(t-1)}\rightarrow
G_{t-1}\rightarrow\,\,G_{t-1}^{(t-2)}$ $\displaystyle\hskip
159.3356pt\downarrow$ $\displaystyle\hskip 163.60333pt\vdots$
$\displaystyle\hskip 159.3356pt\downarrow$ $\displaystyle\hskip
159.3356ptG_{2}^{(2)}\rightarrow G_{2}\rightarrow G_{2}^{(1)}$
$\displaystyle\hskip 227.62204pt\downarrow$ $\displaystyle\hskip
227.62204ptG_{1}^{(1)}\rightarrow
G_{1}\stackrel{{\scriptstyle\exp}}{{\longrightarrow}}G_{0}$ Figure 3: The
schema to derive $G_{0}(\mathbf{x})$ from $G_{t+1}(\mathbf{x})$.

###  2.3 Combinatorial integration

In this section, we prove an alternative equation for (5) which does not
involve an integral operator. It is useful when computing the numerical values
in Table 1.

A class of graphs ${\cal A}$ is said to be tree-decomposable if for each graph
$\Gamma\in{\cal A}$ we can associate in a unique way a tree $\tau(\Gamma)$
whose nodes are distinguishable, for instance by using the labels. Let ${\cal
A}_{\bullet}$ denote the class of graphs in ${\cal A}$ where a node of
$\tau(\Gamma)$ is distinguished. Similarly, ${\cal A}_{\bullet-\bullet}$ is
the class of graphs in ${\cal A}$ where an edge of $\tau(\Gamma)$ is
distinguished, and ${\cal A}_{\bullet\rightarrow\bullet}$ those where an edge
$\tau(\Gamma)$ is distinguished and given a direction. As presented in
[CFKS08], the dissymmetry theorem for tree-decomposable classes is a
generalisation of the well-known dissymetry theorem for trees of [BLL97], and
allows one to express the class of unrooted graphs in $\mathcal{A}$ in terms
of the rooted classes.

######  Proposition 2.6 (Dissymmetry Theorem [CFKS08]).

Let ${\cal A}$ be a tree-decomposable class, then

${\cal A}+{\cal A}_{\bullet\rightarrow\bullet}\simeq{\cal A}_{\bullet}+{\cal
A}_{\bullet-\bullet},$

where $\simeq$ is a bijection preserving the number of nodes. In particular,
if the encoding trees have no adjacent nodes of the same type then we have

${\cal A}\simeq{\cal A}_{\bullet}-{\cal A}_{\bullet-\bullet}.$

An example of the decomposition of a chordal graph $\Gamma$ of bounded tree-
width and its associated tree $\tau(\Gamma)$ is depicted in Figure 4.

Figure 4: Tree-decomposition (right) associated to a $2$-connected chordal
graph (left) of tree-width 3.

Next, we make use of this decomposition to obtain, via the above Proposition,
the generating function of unrooted chordal graphs of bounded tree-width.

######  Lemma 2.7.

Let $k\in[t]$. Then the following equation holds:

$\begin{split}G_{k}(\mathbf{x})&=G_{k+1}\big{(}x_{1},\ldots,x_{k-1},x_{k}G_{k}^{(k)}(\mathbf{x}),x_{k+1},\ldots,x_{t}\big{)}\\\
&\qquad+\frac{1}{k!}\prod_{j\in[k]}x_{j}^{\binom{k}{j}}G_{k}^{(k)}(\mathbf{x})\left(1-G_{k+1}^{(k)}\big{(}x_{1},\ldots,x_{k-1},x_{k}G_{k}^{(k)}(\mathbf{x}),x_{k+1},\ldots,x_{t}\big{)}\right).\end{split}$
(6)

###### Proof.

To each $\Gamma\in\mathcal{G}_{k}$ different from the comple graph on $k$
vertices, we associate a unique tree $\tau(\Gamma)$ as follows. The tree
$\tau(\Gamma)$ admits two different types of nodes, namely $b$ and $c$. Nodes
of type $b$ represent the $(k+1)$-connected components of $\Gamma$, while
those of type $c$ represent the $k$-cliques of $\Gamma$ through which the
$(k+1)$-connected components are glued together.

Let $B_{k}$ and $C_{k}$ be the generating functions counting the trees
$\tau(\Gamma)$ ($\Gamma\in\mathcal{G}_{k}$) rooted at nodes of type $b$ and
$c$, respectively, and $E_{k}$ be the generating function of those trees
rooted at an undirected edge between nodes of types $b$ and $c$. They can also
be respectively seen as the generaring functions counting $k$-connected graphs
with a distinguished $(k+1)$-connected component, a distinguished $k$-clique
that belongs to more than one $(k+1)$-connected components, or a distinguished
$(k+1)$-connected component $C$ together with a distinguished $k$-clique in
$C$ that belongs to at least another $(k+1)$-connected component $C^{\prime}$.
They are specified next using the symbolic method:

$\displaystyle B_{k}(\mathbf{x})$
$\displaystyle=G_{k+1}\big{(}x_{1},\ldots,x_{k-1},x_{k}G_{k}^{(k)}(\mathbf{x}),x_{k+1},\ldots,x_{t}\big{)},$
$\displaystyle C_{k}(\mathbf{x})$
$\displaystyle=\frac{1}{k!}\prod_{j\in[k]}x_{j}^{\binom{k}{j}}\left(G_{k}^{(k)}(\mathbf{x})-\left(1+G_{k+1}^{(k)}\big{(}x_{1},\ldots,x_{k-1},x_{k}G_{k}^{(k)}(\mathbf{x}),x_{k+1},\ldots,x_{t}\big{)}\right)\right),$
$\displaystyle E_{k}(\mathbf{x})$
$\displaystyle=\frac{1}{k!}\prod_{j\in[k]}x_{j}^{\binom{k}{j}}G_{k+1}^{(k)}\big{(}x_{1},\ldots,x_{k-1},x_{k}G_{k}^{(k)}(\mathbf{x}),x_{k+1},\ldots,x_{t}\big{)}\left(G_{k}^{(k)}(\mathbf{x})-1\right).$

The equation defining $B_{k}(\mathbf{x})$ follows directly from the
decomposition discussed in the previous section, while the equation for
$C_{k}(\mathbf{x})$ is obtained from Equation (4) by substracting the first
two terms of the exponential (because there are at least two $(k+1)$-connected
components glued through the $k$-clique). The equation for $E_{k}(\mathbf{x})$
can be derived by considering a $(k+1)$-connected chordal graph $\Gamma$
rooted at a $k$-clique $K$ and gluing through it a $k$-connected chordal graph
$\Gamma^{\prime}$ rooted at $K$, and containing at least one $(k+1)$-connected
component, then further gluing some $k$-connected chordal graph to other
$k$-cliques of $\Gamma^{\prime}$. The correcting factors in the last two
equations are there to mark all the subcliques of the root $k$-clique and
forget the order of its vertices.

Finally, recall that we consider the complete graph on $k$ vertices to be
$k$-connected. So that Proposition 2.6 directly implies that the unrooted
graphs are counted by

$\displaystyle
G_{k}(\mathbf{x})=\frac{1}{k!}\prod_{j\in[k]}x_{j}^{\binom{k}{j}}+B_{k}(\mathbf{x})+C_{k}(\mathbf{x})-E_{k}(\mathbf{x}).$

By translating this equation in light of the above three equations, one
concludes the proof. ∎

##  3 Asymptotic analysis

Fix $t\geq 1$. In this section we prove Theorems 1.1 and 1.2. We use rather
classical methods from [FS09], which consist in deriving asymptotic estimates
from local expansions of the generating functions from Section 2 at their
singularities. Those expansions are in turn derived from successive
applications of the implicit system of equations described in Lemma 2.5, to
“transfer” the local expansion of $G_{t+1}(\mathbf{x})$ to
$G_{0}(x_{1},1,\ldots,1)$, as illustrated by the schema in Figure 3.

We will follow the method developed in [D09, Chapter 2], but will need to
extend some of the tools and notions present there in order to deal with
multivariate generating functions and the fact that the local expansions are
with respect to different variables from one step to the next. This is the
purpose of the next section.

###  3.1 Proper singularity functions and singular expansions

Let $\rho:U\to\mathbb{C}$ be an analytic function defined on an open set. For
$u\in U$ and $\delta,\eta>0$, a $\Delta$-domain at $\rho(u)$ is a complex
region of the form

$\displaystyle\Delta(\rho(u),\delta,\eta)=\Delta(\rho(u))=\\{z\in\mathbb{C}:|z|<\rho(u)+\eta\text{
and }|\arg(z/\rho(u)-1)|>\delta\\}.$

Our main tool is a “transfer theorem”. The proof can be found in [D09] (see
also [FS09, Chapter VI.3]).

######  Proposition 3.1.

(Transfer Theorem [D09, Lemma 2.18]). Let $f(z,u)$ be a power series in $z$
and a parameter $u\in U$, and suppose that it admits an expansion of the form

$\displaystyle
f(z,u)=C(u)\left(1-\frac{z}{\rho(u)}\right)^{-\alpha(u)}+O\left(\left(1-\frac{z}{\rho(u)}\right)^{-\beta(u)}\right),$

that is uniform for $u\in U$ and $z\in\Delta(\rho(u))$, and with functions
$C(u)$, $\rho(u)$, $\alpha(u)$ and $\beta(u)$ that remain bounded and satisfy
$\beta(u)<\Re(\alpha(u))$ for all $u\in U$.

Then the following estimate holds uniformly for $u\in U$ and as $n\to\infty$

$\displaystyle[z^{n}]f(z,u)=C(u)\frac{n^{\alpha(u)-1}}{\Gamma(\alpha(u))}\rho(u)^{-n}+O\left(\rho(u)^{-n}\,n^{\max\left(\Re(\alpha(u))-2,\,\,\beta(u)-1\right)}\right).$

By setting $u=1$ in Proposition 3.1, one recovers the “classical” transfer
theorem for univariate analytic functions, see for instance [D09, Lemma 2.15].

Next we introduce several definitions which will allow us to extend the notion
of local expansion of an analytic function at an algebraic singularity to our
multivariate setting. First is the notion of fully movable proper singularity
function.

######  Definition 3.2.

We say that a function $\rho(x_{2},\ldots,x_{t})$ is a proper singularity
function if it satisfies the following conditions:

  * (i)

It is defined in a $(t-1)$-dimensional proper complex neighbourhood of
$\mathbb{R}_{+}^{t-1}$, where it is also analytic.

  * (ii)

It is positive and real if $x_{2},\ldots,x_{t}$ are positive and real, and it
is strictly decreasing with negative derivatives in all $t-1$ positive real
variables.

Furthermore we say it is fully movable with respect to the variables
$x_{2},\ldots,x_{k}$ if the following condition holds:

  * (iii)

$\rho(x_{2},\ldots,x_{t})\to 0$ (resp. $\infty$) if one of the variables
$x_{2},\ldots,x_{k}$ tends to $\infty$ (resp. $0$), whereas all the other
variables including $x_{k+1},\ldots,x_{t}$ are fixed positive real numbers.

With this notion at hand, we can define that of a positive function with a
proper $\alpha$-singularity.

######  Definition 3.3.

Let $\alpha\in\mathbb{R}\setminus\mathbb{Z}$. We say that a function
$G(\mathbf{x})$ is a positive function with a proper $\alpha$-singularity if
the following properties hold:

  * (i)

$G(\mathbf{x})$ is a power series in $\mathbf{x}=(x_{1},\ldots,x_{t})$ with
non-negative coefficents.

  * (ii)

There exists a proper singularity function $\rho(x_{2},\ldots,x_{t})$ such
that for every fixed choice of $x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$,
$\rho(x_{2},\ldots,x_{t})$ is the radius of convergence of the power series
$x_{1}\mapsto G(\mathbf{x})$.

  * (iii)

For every choice of $X_{0},X_{1}\in\mathbb{R}$ with $0<X_{0}<X_{1}$, there
exist $\delta>0$ and analytic functions $g_{1}(\mathbf{x})$,
$g_{2}(\mathbf{x})$, that are defined and non-zero for
$X_{0}<|x_{2}|,\ldots,|x_{t}|<X_{1}$ and
$|x_{1}-\rho(x_{2},\ldots,x_{t})|<\delta$ with $x_{1},\ldots,x_{t}$
sufficiently close to the positive real axis, such that in this range,
provided that $\arg(x_{1}-\rho(x_{2},\ldots,x_{t}))\neq 0$, we have

$G(\mathbf{x})=g_{1}(\mathbf{x})+g_{2}(\mathbf{x})\left(1-\frac{x_{1}}{\rho(x_{2},\ldots,x_{t})}\right)^{\alpha}.$
(7)

In this case we say that $x_{1}$ is the leading variable of $G(\mathbf{x})$.

Finally, in order to apply Proposition 3.1 to a positive function with a
proper $\alpha$-singularity, we need some notion of analytic continuation to a
$\Delta$-domain.

######  Definition 3.4.

A positive function $G(\mathbf{x})$ with a proper $\alpha$-singularity
($\alpha\in\mathbb{R}\setminus\mathbb{Z}$) and proper singularity function
$\rho(x_{2},\ldots,x_{t})$ is said to be aperiodic and analytically
continuable with respect to the variable $x_{1}$ if the following holds:

  * (i)

For every fixed choice of $x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$,
$\rho(x_{2},\ldots,x_{t})$ is the unique singularity of the function
$x_{1}\mapsto G(\mathbf{x})$ on the circle $|x_{1}|=\rho(x_{2},\ldots,x_{t})$.

  * (ii)

There exists $\delta>0$ such that $x_{1}\mapsto G(\mathbf{x})$ can be
analytically continued to the region

$|x_{1}|<|\rho(x_{2},\ldots,x_{t})|+\delta/2\quad\text{and}\quad|x_{1}-\rho(x_{2},\ldots,x_{t})|>\delta.$
(8)

In particular this function cannot be represented as a function of the form
$x_{1}^{a}f(x_{1}^{b})$ for some positive integers $a,b$, where $b>1$.

Fix $k\in\\{2,\ldots,t\\}$ and observe that setting $x_{i}=1$ for $i\neq k$ in
Definition 3.4(ii) implies that $G(x_{1},1,\ldots,1,x_{k},1,\ldots,1)$ can be
analytically continued to a domain of the form $\Delta(x_{k})$.

###  3.2 Transfer properties of proper singular expansions

We now prove certain “transfer properties” of proper $\alpha$-singular
expansions in the neighbourhood of a proper singularity function. Our main
tools here will be the Implicit Function Theorem (IFT) for analytic functions,
and its refinement known as the Weierstrass Preparation Theorem (WPT). For a
statement and a proof of those famous theorems, we refer the reader to [KK83].

The first property generalises [D09, Lemma 2.28] to proper singularity
functions. The proof follows the same line and we only sketch it here.

######  Lemma 3.5.

Let $k\in\\{2,\ldots,t-1\\}$ and suppose that $\rho(x_{2},x_{3},\ldots,x_{t})$
is a proper singularity function that is fully movable with respect to the
variables $x_{2},\ldots,x_{k}$. Then there exists a proper singularity
function $\kappa(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})$ that is fully
movable with respect to $x_{1},\ldots,x_{k-1}$ such that

$x_{1}=\rho(x_{2},\ldots,x_{k-1},\kappa(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t}),x_{k+1},\ldots,x_{t}).$
(9)

Furthermore there exists a function $K(\mathbf{x})$ that is analytic and non-
zero on a $t$-dimensional complex neighbourhood of $\mathbb{R}_{+}^{t}$ such
that

$x_{1}-\rho(x_{2},\ldots,x_{t})=K(\mathbf{x})\left(x_{k}-\kappa(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})\right).$
(10)

###### Proof.

Suppose first that $x_{1},\ldots,x_{t}$ are positive real variables. Since
$\rho$ is strictly decreasing and tends to $0$ (resp. $\infty$), if one of the
variables $x_{2},\ldots,x_{k}$ tends to $\infty$ (resp. $0$) then it
immediately follows from the continuity of $\rho$ and the IFT that a function
$\kappa=\kappa(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})$ satisfying (9)
exists. Furthermore, $\kappa$ is strictly decreasing and tends to $0$ (resp.
$\infty$) if one of the variables $x_{1},\ldots,x_{k-1}$ tends to $\infty$
(resp. $0$).

Next, fix $x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$ and set
$x_{1}=\rho(x_{2},\ldots,x_{t})$. Since from Definition 3.2 $\rho$ is analytic
and satisfies $\frac{\partial}{\partial x_{k}}\rho<0$ for $2\leq k\leq t$, it
follows, by applying the IFT to (9), that the function $\kappa$ can be
(uniquely) analytically continued to a complex neighbourhood of
$(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})$. In fact, using the WPT in the
degree one case, it can further be shown that there exists a function
$K(\mathbf{x})$ that is analytic and non-zero in a complex neighbourhood of
$\mathbf{x}$ such that (10) holds.

Finally, a standard analytic continuation argument shows that both $\kappa$
and $K$ can be globally defined so that (10) holds in the proposed range, that
is, a complex neighbourhood of $\mathbb{R}_{+}^{t}$. ∎

An important consequence of Lemma 3.5 is that for $k\in[t]$ the representation
(7) can be rewritten into

$G(\mathbf{x})=g_{1}(\mathbf{x})+\overline{g}_{2}(\mathbf{x})\left(1-\frac{x_{k}}{\kappa}\right)^{\alpha},$

with $\kappa=\kappa(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})$ and where the
analytic function

$\overline{g}_{2}(\mathbf{x})=g_{2}(\mathbf{x})\left(\frac{K(\mathbf{x})\kappa}{\rho(x_{2},\ldots,x_{t})}\right)^{\alpha}$

is defined and non-zero for $X_{0}<|x_{2}|,\ldots,|x_{t}|<X_{1}$. This means
that any of the variables $x_{1},\ldots,x_{k}$ can be the leading one in the
definition of a positive function with a proper $\alpha$-singularity, provided
that the proper singularity function $\rho(x_{2},\ldots,x_{t})$ is fully
movable with respect to $x_{2},\ldots,x_{k}$. Furthermore $\kappa$ is
certainly a singularity of the mapping $x_{k}\mapsto G(\mathbf{x})$. And by
the monotonicity property in Definition 3.2(ii) there is no smaller positive
real singularity. Thus, $\kappa$ is the radius of convergence of the mapping
$x_{k}\mapsto G(\mathbf{x})$, provided that
$x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t}\in\mathbb{R}_{+}$.

Next, we extend [D09, Lemma 2.27] to the context of positive function with a
proper $\alpha$-singularity.

######  Lemma 3.6.

For $k\in[t]$ and $\alpha\in\mathbb{R}\setminus\mathbb{Z}$, let
$G(\mathbf{x})$ be a positive function with a proper $\alpha$-singularity,
aperiodic and analytically continuable with respect to $x_{1}$, and with a
proper singularity function $\rho(x_{2},\ldots,x_{t})$ that is fully movable
with respect to $x_{2},\ldots,x_{k}$. Set

$D(\mathbf{x})=\frac{\partial}{\partial
x_{k}}G(\mathbf{x})\quad\text{and}\quad
H(\mathbf{x})=\int_{0}^{x_{k}}G(x_{1},\ldots,x_{k-1},y,x_{k+1},\ldots,x_{t})\,dy.$
(11)

Then $D(\mathbf{x})$ is a positive function with a proper
$(\alpha-1)$-singularity, while and $H(\mathbf{x})$ is a positive function
with a proper $(\alpha+1)$-singularity, and both are aperiodic and
analytically continuable with respect to $x_{1}$. Furthermore the proper
singularity functions of $G(\mathbf{x})$, $D(\mathbf{x})$ and $H(\mathbf{x})$
coincide.

###### Proof.

Fix $\delta>0$. First, the analytic continuability of both mappings
$x_{1}\mapsto D(\mathbf{x})$ and $x_{1}\mapsto H(\mathbf{x})$ to a region of
the form (8) is immediate by assumption on $G(\mathbf{x})$ and properties of
the derivative and the integral. Second, if
$|x_{1}-\rho(x_{2},\ldots,x_{t})|<\delta$ then Lemma 3.5 implies that there
exist $\delta^{\prime}>0$ and a proper singularity function
$\kappa=\kappa(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})$ such that for
$|x_{k}-\kappa|<\delta^{\prime}$, $G(\mathbf{x})$ can be represented as

$G(\mathbf{x})=g_{1}(\mathbf{x})+\overline{g}_{2}(\mathbf{x})\left(1-\frac{x_{k}}{\kappa}\right)^{\alpha}.$
(12)

Set $d_{1}(\mathbf{x})=(\partial/\partial x_{k})g_{1}(\mathbf{x})$ and
$d_{2}(\mathbf{x})=\overline{g}_{2}(\mathbf{x})/(2\kappa)+(\partial/\partial
x_{k})\overline{g}_{2}(\mathbf{x})\left(1-x_{k}/\kappa\right)$. Then taking
the partial derivative of (12) with respect to $x_{k}$ gives

$\displaystyle D(\mathbf{x})=\frac{\partial}{\partial
x_{k}}g_{1}(\mathbf{x})+\frac{\partial}{\partial
x_{k}}\overline{g}_{2}(\mathbf{x})\left(1-\frac{x_{k}}{\kappa}\right)^{\alpha}+\frac{\overline{g}_{2}(\mathbf{x})}{2\kappa}\left(1-\frac{x_{k}}{\kappa}\right)^{\alpha-1}=d_{1}(\mathbf{x})+d_{2}(\mathbf{x})\left(1-\frac{x_{k}}{\kappa}\right)^{\alpha-1}.$

Now, in order to compute the integral of (12) we first compute the Taylor
expansions of the functions $g_{1}(\mathbf{x})$ and
$\overline{g}_{2}(\mathbf{x})$ at $x_{k}\sim\kappa$ and obtain a
representation of the form

$G(\mathbf{x})=\sum_{\ell\geq
0}G_{\ell}(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})\left(1-\frac{x_{k}}{\kappa}\right)^{\alpha\ell}$
(13)

that is certainly convergent for $|x_{k}-\kappa|<\delta^{\prime}$. Next we
split up the integral in (11) into three parts

$\displaystyle I_{1}(x_{1},\dots,x_{k-1},x_{k+1},\dots,x_{t})$
$\displaystyle:=\int_{0}^{(1-\eta)\kappa}G(x_{1},\ldots,x_{k-1},y,x_{k+1},\ldots,x_{t})\,dy,$
$\displaystyle I_{2}(x_{1},\dots,x_{k-1},x_{k+1},\dots,x_{t})$
$\displaystyle:=\int_{(1-\eta)\kappa}^{\kappa}G(x_{1},\ldots,x_{k-1},y,x_{k+1},\ldots,x_{t})\,dy,$
$\displaystyle I_{3}(\mathbf{x})$
$\displaystyle:=\int_{\kappa}^{x_{k}}G(x_{1},\ldots,x_{k-1},y,x_{k+1},\ldots,x_{t})\,dy,$

where $\eta>0$ is chosen in such a way that $\eta<\delta^{\prime}/|\kappa|$.
The first integral is certainly an analytic function in
$x_{1},\ldots,x_{k-1},x_{k},\ldots,x_{t}$, as a definite integral with respect
to $y$ in a range where $G$ is analytic. The second integral can be directly
computed by the series expansion (13)

$\displaystyle I_{2}(x_{1},\dots,x_{k-1},x_{k+1},\dots,x_{t})$
$\displaystyle=\int\limits_{(1-\eta)\kappa}^{\kappa}G(x_{1},\ldots,x_{k-1},y,x_{k+1},\ldots,x_{t})\,dy$
$\displaystyle=\sum_{\ell\geq
0}G_{\ell}(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})\int\limits_{(1-\eta)\kappa}^{\kappa}(1-y/\kappa)^{\alpha\ell}\,dy$
$\displaystyle=\kappa\sum_{\ell\geq
0}\frac{G_{\ell}(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})}{\alpha\ell+1}\eta^{\alpha\ell+1}.$

This series is absolutely convergent and represents an analytic function in
$x_{1},\ldots,x_{k-1}$, $x_{k+1},\ldots,x_{t}$. Finally, for the third
integral we use again the series expansion (13) and obtain

$\displaystyle I_{3}(\mathbf{x})$
$\displaystyle=\int_{\kappa}^{x_{k}}G(x_{1},\ldots,x_{k-1},y,x_{k+1},\ldots,x_{t})\,dy$
$\displaystyle=\sum_{\ell\geq
0}G_{\ell}(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})\int\limits_{\kappa}^{x_{k}}(1-y/\kappa)^{\alpha\ell}\,dy$
$\displaystyle=-\kappa\sum_{\ell\geq
0}\frac{G_{\ell}(x_{1},\ldots,x_{k-1},x_{k+1},\ldots,x_{t})}{\alpha\ell+1}(1-x_{k}/\kappa)^{\alpha\ell+1}.$

This series representation can be rewritten into

$\displaystyle
I_{3}(\mathbf{x})=h_{1}(\mathbf{x})+h_{2}(\mathbf{x})\left(1-\frac{x_{k}}{\kappa}\right)^{\alpha+1}.$

Next, note that since

$\displaystyle\overline{g}_{2}(x_{1},\ldots,x_{k-1},\kappa,x_{k+1},\ldots,x_{t})=-\frac{\alpha+1}{\kappa}h_{2}(x_{1},\ldots,x_{k-1},\kappa,x_{k+1},\ldots,x_{t}),$

then both $\overline{g}_{2}$ and $h_{2}$ are non-zero, even if
$|x_{k}-\kappa|<\delta^{\prime\prime}$ for a sufficiently small
$\delta^{\prime\prime}>0$. Moreover, since the coefficients of $G(\mathbf{x})$
and $H(\mathbf{x})$ are non-negative we have $g_{1}(\mathbf{x})>0$ for
$x_{j}\in\mathbb{R}_{+}$ and
$\overline{h}_{1}(\mathbf{x})=h_{1}(\mathbf{x})+I_{1}(x_{1},\dots,x_{k-1},x_{k+1},\dots,x_{t})+I_{2}(x_{1},\dots,x_{k-1},x_{k+1},\dots,x_{t})>0$.

Finally, by another application of Lemma 3.5, we can rewrite $D(\mathbf{x})$
and $H(\mathbf{x})$ into

$\displaystyle
D(\mathbf{x})=d_{1}(\mathbf{x})+\overline{d}_{2}(\mathbf{x})\left(1-\frac{x_{1}}{\rho(x_{2},\ldots,x_{t})}\right)^{\alpha-1}\text{and
}H(\mathbf{x})=\overline{h}_{1}(\mathbf{x})+\overline{h}_{2}(\mathbf{x})\left(1-\frac{x_{1}}{\rho(x_{2},\ldots,x_{t})}\right)^{\alpha+1}$

with $\overline{d}_{2},\overline{h}_{2}\neq 0$. This completes the proof. ∎

Finally, we generalise [D09, Theorem 2.21]. This theorem states that if
$G(x,u)$ is a univariate function, with parameter $u=(x_{2},\ldots,x_{t})$,
defined implicitely in terms of another function $F(x,u,y)$ (i.e. such that
$F(x,u,G(x,u))=0$) that admits a $1/2$-singular expansion at some $R>0$, then
$G(x,u)$ also admits a $1/2$-singular expansion at some $\rho<R$. The next
result extends this to the case where $F$ has a proper $1/2$-singularity. The
proof follows the same lines and we sketch it next.

######  Lemma 3.7.

Suppose that $F(\mathbf{x},y)$ is a positive function in $t+1$ variables with
a proper $1/2$-singularity and singularity function $R(x_{2},\ldots,x_{t};y)$
that is fully movable with respect to the variables $x_{2},\ldots,x_{k}$ and
$y$ for some $2\leq k\leq t$. Furthermore assume that
$F(x_{1},x_{2},\ldots,x_{t},y)=0$ if one of the variables $x_{1},\ldots,x_{k}$
are zero. Then the functional equation

$G=\exp(F(\mathbf{x},G))$ (14)

has a unique solution $G=G(\mathbf{x})$ with $G({\bf 0})=1$ which is a
positive function with a proper $1/2$-singularity, too. Its singularity
function $\rho(x_{2},\ldots,x_{t})$ is fully movable with respect to the
variables $x_{2},\ldots,x_{k}$ and satisfies

$\displaystyle\rho(x_{2},\ldots,x_{t})<R\big{(}x_{2},\ldots,x_{t};G(\rho(x_{2},\ldots,x_{t}),x_{2},\ldots,x_{t})\big{)}.$

Moreover, if $F(\mathbf{x},y)$ is periodic and analytically continuable with
respect to the variable $x_{1}$ then the same property holds for
$G(\mathbf{x})$.

###### Proof.

First, by iteration (or by the IFT), Equation (14) admits a unique power
series solution with $G({\bf 0})=1$ and non-negative coefficients.

Next we define a singularity function $\rho(x_{2},\ldots,x_{t})$. For this
purpose we fix $x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$ and vary $x_{1}$. We
claim that there exists a unique $\overline{x}_{1}>0$ such that for
$\overline{\mathbf{x}}=(\overline{x}_{1},x_{2},\ldots,x_{t})$ we have
$\overline{x}_{1}<R(x_{2},\ldots,x_{t},G(\overline{\mathbf{x}}))$ and
satisfying

$G(\overline{\mathbf{x}})=\exp(F(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))),$
(15)

and

$1=\exp(F(\overline{\mathbf{x}},G(\overline{\mathbf{x}})))\frac{\partial
F}{\partial y}(\overline{\mathbf{x}},G(\overline{\mathbf{x}})).$ (16)

Since all the coefficients of $G$ are non-negative, the solution function $G$
is strictly increasing in $x_{1}$. Consequently, the factor
$\exp(F(\overline{\mathbf{x}},G(\overline{\mathbf{x}})))$ in (16) is also
strictly increasing in $x_{1}$.

Now we study the factor $(\partial F/\partial
y)(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))$ in (16). By assumption we
have

$\displaystyle\frac{\partial F}{\partial
y}(0,x_{2},\ldots,x_{t},G(0,x_{2},\ldots,x_{t}))=0.$

Moreover, since $F$ is a positive function with a proper $1/2$-singularity, by
Lemma 3.6 $\partial F/\partial y$ is a positive function with a proper
$(-1/2)$-singularity, that is, when $x_{1}\sim R(x_{2},\ldots,x_{t},y)$ it can
be represented as

$\displaystyle\frac{\partial F}{\partial
y}(\mathbf{x},y)=\overline{f}_{1}(\mathbf{x},y)+\overline{f}_{2}(\mathbf{x},y)\left(1-\frac{x_{1}}{R(x_{2},\ldots,x_{t},y)}\right)^{-1/2},$

where $\overline{f}_{1}$ and $\overline{f}_{2}$ are analytic and
$\overline{f}_{2}\neq 0$. Since $G$ is strictly increasing in $x_{1}$ and $R$
is a proper singularity function fully movable in $y$,
$R(x_{2},\ldots,x_{t},G(\mathbf{x}))$ is strictly decreasing in $x_{1}$ and
goes to $0$ as $x_{1}\to\infty$. Therefore,
$\left(1-x_{1}/R(x_{2},\ldots,x_{t},G(\mathbf{x}))\right)^{-1/2}$ is strictly
increasing in $x_{1}$ and unbounded while
$x_{1}<R(x_{2},\ldots,x_{t},G(\mathbf{x}))$. The same is true for $(\partial
F/\partial y)(\mathbf{x},G(\mathbf{x}))$ because
$\overline{f}_{1}(\mathbf{x},G(\mathbf{x}))$ and
$\overline{f}_{2}(\mathbf{x},G(\mathbf{x}))$ are strictly increasing functions
in $x_{1}$ when $x_{1}<R(x_{2},\ldots,x_{t},G(\mathbf{x}))$. Our claim
follows.

From [D09, Theorem 2.19], which amounts to evaluating the parameter $u$ in
$\mathbb{R}_{+}$ in [D09, Theorem 2.21], this implies that for
$x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$ the univariate function $x_{1}\to
G(\mathbf{x})$ has a $1/2$-singularity at $x_{1}=\overline{x}_{1}$. Therefore
we set

$\displaystyle\rho(x_{2},\ldots,x_{t}):=\overline{x}_{1}.$

The system formed by equations (15) and (16) can be used to get more
information on $\rho$. Notice first that, given $x_{2},\ldots,x_{t}$, the
system determines $\overline{x}_{1}=\rho(x_{2},\ldots,x_{t})$ and
$G(\overline{\mathbf{x}})$. Then, since the determinant

$\displaystyle\left|\begin{array}[]{cc}-e^{F}\displaystyle\frac{\partial
F}{\partial x_{1}}&1-e^{F}\displaystyle\frac{\partial F}{\partial y}\\\
-e^{F}\displaystyle\frac{\partial F}{\partial x_{1}}\frac{\partial F}{\partial
y}-e^{F}\displaystyle\frac{\partial^{2}F}{\partial y\partial
x_{1}}&-e^{F}\left(\displaystyle\frac{\partial F}{\partial
y}\right)^{2}-e^{F}\displaystyle\frac{\partial^{2}F}{\partial
y^{2}}\end{array}\right|$
$\displaystyle=e^{2F}\left|\begin{array}[]{cc}\displaystyle\frac{\partial
F}{\partial x_{1}}&0\\\ \displaystyle\frac{\partial F}{\partial
x_{1}}\frac{\partial F}{\partial y}+\frac{\partial^{2}F}{\partial y\partial
x_{1}}&\left(\displaystyle\frac{\partial F}{\partial
y}\right)^{2}+\displaystyle\frac{\partial^{2}F}{\partial
y^{2}}\end{array}\right|$ $\displaystyle=e^{2F}\displaystyle\frac{\partial
F}{\partial x_{1}}\left(\left(\frac{\partial F}{\partial
y}\right)^{2}+\displaystyle\frac{\partial^{2}F}{\partial y^{2}}\right)$

is positive, it follows by the IFT that the function
$\rho(x_{2},\ldots,x_{t})$ can be locally analytically continued. Fix now some
$2\leq j\leq k$. By differentiating (15) with respect to $x_{j}$, one obtains

$\displaystyle 0$
$\displaystyle=\frac{\partial[G(\overline{\mathbf{x}})]}{\partial
x_{j}}-\exp(F(\overline{\mathbf{x}},G(\overline{\mathbf{x}})))\left[\frac{\partial
F}{\partial
x_{1}}(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))\frac{\partial\rho}{\partial
x_{j}}+\frac{\partial F}{\partial
x_{j}}(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))+\frac{\partial
F}{\partial
y}(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))\frac{\partial[G(\overline{\mathbf{x}})]}{\partial
x_{j}}\right]$
$\displaystyle=-\exp(F(\overline{\mathbf{x}},G(\overline{\mathbf{x}})))\left[\frac{\partial
F}{\partial
x_{1}}(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))\frac{\partial\rho}{\partial
x_{j}}+\frac{\partial F}{\partial
x_{j}}(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))\right].$

In other words,

$\displaystyle\displaystyle\frac{\partial\rho}{\partial
x_{j}}=-\frac{\displaystyle\frac{\partial F}{\partial
x_{j}}(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))}{\displaystyle\frac{\partial
F}{\partial x_{1}}(\overline{\mathbf{x}},G(\overline{\mathbf{x}}))}<0.$

This means that $\rho$ is strictly decreasing in all variables, provided they
are real and positive. Let us finally consider the behaviour of $\rho$ as
$x_{j}$ tends to $0$ or $+\infty$. Suppose first that $\overline{x}_{1}=\rho$
is bounded away from 0 when $x_{j}\to\infty$. Then
$G(\overline{\mathbf{x}})\to+\infty$, and $R\to 0$. However, this is
impossible since $\overline{x}_{1}<R$. Thus $\rho\to 0$ as $x_{j}\to\infty$.
On the other hand, suppose that $\overline{x}_{1}=\rho$ stays bounded when
$x_{j}\to 0$. In this case, $G(\overline{\mathbf{x}})$ stays bounded and so by
assumptions on the zeros of $F$, $F(\overline{x},G(\overline{\mathbf{x}})))\to
0$ and $(\partial F/\partial y)(\overline{x},G(\overline{\mathbf{x}})))\to 0$
as $x_{j}\to 0$. However, this is not possible by (16). Summing up, this means
from Definition 3.2 that the function $\rho$ is a proper singularity function
that is fully movable with respect to $x_{2},\ldots,x_{k}$.

Furthermore, it follows from [D09, Theorem 2.21] that we also get an expansion
of the form (7) with $\alpha=1/2$ for $G(\mathbf{x})$. And it remains to check
that for $x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$, the mapping $x_{1}\mapsto
G(\mathbf{x})$ admits an analytic continuation away from $\rho$, in a region
of the form (8). To that end, we now consider (14) as a functional equation
for the function $x_{1}\mapsto G(\mathbf{x})$. Since $G(\mathbf{x})$ can be
written as $G(\mathbf{x})=1+\tilde{G}(\mathbf{x})$, where $\tilde{G}$ is a
power series with non-negative coefficients, we have that

$\displaystyle G(\mathbf{x})=\exp(F(\mathbf{x},G(\mathbf{x})))$
$\displaystyle=\exp(F(\mathbf{x},1+\tilde{G}(\mathbf{x})))$
$\displaystyle=\exp(F(\mathbf{x},1)+\tilde{F}(\mathbf{x},\tilde{G}(\mathbf{x})))$
$\displaystyle=1+F(\mathbf{x},1)+\tilde{F}(\mathbf{x},\tilde{G}(\mathbf{x}))+\sum_{n\geq
2}\frac{(F(\mathbf{x},1)+\tilde{F}(\mathbf{x},\tilde{G}(\mathbf{x})))^{n}}{n!},$

where $\tilde{F}(\mathbf{x},y)$ is a power series with non-negative
coefficients. Now, since $F(\mathbf{x},y)$ is aperiodic in $x_{1}$, it follows
that $G(\mathbf{x})$ has to also be aperiodic with respect to $x_{1}$. This
implies that $\rho(x_{2},\ldots,x_{t})$ is the unique dominant singularity of
the function $x_{1}\mapsto G(\mathbf{x})$ and we conclude by a standard
compactness argument that it can be analytically continued to a region of the
form (8). ∎

###  3.3 Proofs of the main results

Fix $t\geq 1$ and recall that starting with $G_{t+1}$, which is an explicit
monomial, one can recursively obtain the generating functions
$G_{t},G_{t-1},\ldots,G_{1}$, and finally $G_{0}=\exp(G_{1})$. Let us next
discuss the first step of this induction, from $G_{t+1}$ to $G_{t}$, since it
is slightly different from the general step.

######  Proposition 3.8.

Let $t\geq 1$, $x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$. Then there exists two
functions $h_{1}(x)$ and $h_{2}(x)$, that are analytic and non-zero at
$x=1/e$, such that for $x\sim 1/e$ we have

$G_{t}(\mathbf{x})=\frac{\prod_{j=1}^{t}x_{j}^{\binom{t}{j}}}{t!}\left(h_{1}(tX)+h_{2}(tX)(1-etX)^{3/2}\right),\qquad\text{where
}X=\prod_{j=1}^{t}x_{j}^{\binom{t}{j-1}}.$ (17)

###### Proof.

From Equation (2) and by (3) we directly get

$G_{t+1}^{(t)}(\mathbf{x})=\prod_{j=1}^{t}x_{j}^{\binom{t}{j-1}}.$

Consequently, from the relation (4) the function
$G_{t}^{(t)}=G_{t}^{(t)}(\mathbf{x})$ satisfies the equation

$G_{t}^{(t)}=\exp\left(\prod_{j=1}^{t}x_{j}^{\binom{t}{j-1}}[G_{t}^{(t)}]^{t}\right).$

Let $T(z)$ denote the tree function, i.e. that satisfies the equation
$T(z)=z\exp(T(z))$. Then, using the change of variable $z=tX$ with
$X=\prod_{j=1}^{t}x_{j}^{\binom{t}{j-1}}$, we can represent
$G_{t}^{(t)}(\mathbf{x})$ as

$G_{t}^{(t)}(\mathbf{x})=\left(\frac{T(tX)}{tX}\right)^{1/t}=\exp\left(T(tX)/t\right).$

With the help of (6) and the relation $T(x)=x\exp(T(x))$, this also leads to

$\displaystyle G_{t}(\mathbf{x})$
$\displaystyle=\frac{1}{t!}\prod_{j=1}^{t}x_{j}^{\binom{t}{j}}G_{t}^{(t)}(\mathbf{x})-\frac{t}{(t+1)!}\prod_{j=1}^{t}x_{j}^{\binom{t+1}{j}}\left[G_{t}^{(t)}(\mathbf{x})\right]^{t+1}$
$\displaystyle=\frac{\prod_{j=1}^{t}x_{j}^{\binom{t}{j}}}{t!}\exp\left(\frac{T(tX)}{t}\right)\left(1-\frac{T(tX)}{t+1}\right).$
(18)

It is well known (see for instance [FS09]) that $T(z)$ has its dominant
singularity at $z_{0}=1/e$ and a local Puiseux expansion at $z\sim z_{0}$ of
the form

$T(z)=1-\sqrt{2}\sqrt{1-ez}+\frac{2}{3}(1-ez)-\frac{11\sqrt{2}}{36}(1-ez)^{3/2}+O\left((1-ez)^{2}\right).$

Furthermore, $z_{0}=1/e$ is the only singularity on the circle $|z|=1/e$ and
$T(z)$ can be analytically continued to a region of the form
$|z|<1/e+\delta/2$, $|z-1/e|>\delta$ for some $\delta>0$.

Hence we get

$\displaystyle\exp\left(\frac{T(x)}{t}\right)\left(1-\frac{T(x)}{t+1}\right)$
$\displaystyle=\frac{te^{1/t}}{t+1}\left(1-\frac{1}{t^{2}}(1-ex)+\frac{2\sqrt{2}(t+1)}{3t^{3}}(1-ex)^{3/2}+O\left((1-ex)^{2}\right)\right)$
$\displaystyle=h_{1}(x)+h_{2}(x)(1-ex)^{3/2},$

where $h_{1}(x)$ and $h_{2}(x)$ are functions that are analytic and non-zero
at $x\sim 1/e$. This directly leads to the claimed local representation of
$G_{t}(\mathbf{x})$. ∎

Note that the appearance of the dominant singularity $(1-etX)^{3/2}$ is not
unexpected since $G_{t}^{(t)}(\mathbf{x})$ has a dominant singularity of the
form $\sqrt{1-etX}$ and $G_{t}(\mathbf{x})$ and is as per (5) – more or less –
the integral of $G_{t}^{(t)}(\mathbf{x})$.

Furthermore, one can deduce from Proposition 3.8 the case $k=t$ of Theorem 1.1
by a direct application of Proposition 3.1 (setting $u=1$). Similarly, a
central limit theorem for the case $k=t$ of Theorem 1.2 follows immediately
from Proposition 3.8 by an application of [D09, Theorem 2.25].

For $k<t$, Theorems 1.1 and 1.2 can also be deduced from local representations
of a form similar to (17), modulo some technical conditions. Thus the main
step of the proofs is to show that the above representation for
$G_{t}(\mathbf{x})$ implies corresponding representation for
$G_{t-1}(\mathbf{x}),G_{t-2}(\mathbf{x}),\ldots,G_{1}(\mathbf{x})$. This is
the object of the next proposition. Before stating it, let us remark the
following.

######  Remark 3.9.

For $k\in[t+1]$, the function $G_{k}(\mathbf{x})$ admits
$\prod_{j\in[k]}x_{j}^{\binom{k}{j}}$ as a factor. If $k=t+1$, this is
Equation (2). For $k\leq t$, it follows from Equation (5). And by (3) this
implies that the function $G_{k}^{(k-1)}(\mathbf{x})$ has
$\prod_{j\in[k]}x_{j}^{\binom{k-1}{j-1}}$ as a factor. In particular,
$G_{k}^{(k-1)}(\mathbf{x})$ is zero if one of the variables
$x_{1},\ldots,x_{k}$ are zero.

######  Proposition 3.10.

Suppose that $2\leq k\leq t$ and let $G_{k}(\bf x)$ be a positive function
with a proper $3/2$-singularity that is aperiodic and analytically continuable
with respect to $x_{1}$, and with a proper singularity function
$\rho_{k}(x_{2},\ldots,x_{t})$ that is fully movable with respect to
$x_{2},\ldots,x_{k}$.

Then the function $G_{k-1}(\bf x)$ is also a positive function with a proper
$3/2$-singularity that is aperiodic and analytically continuable with respect
to $x_{1}$, where the singularity function $\rho_{k-1}(x_{2},\ldots,x_{t})$ is
again fully movable with respect to $x_{2}\ldots,x_{k}$. Moreover, if
$x_{2},\ldots,x_{t}\in\mathbb{R}_{+}$ then

$\rho_{k-1}(x_{2},\ldots,x_{t})<\rho_{k}(x_{2},\ldots,x_{t}).$ (19)

###### Proof.

In a first step, using Lemma 3.5 we replace $\rho_{k}(x_{2},\ldots,x_{t})$ by
the proper singularity function
$\kappa_{k}=\kappa_{k}(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t})$, that is
fully movable with respect to $x_{1},\ldots,x_{k-2}$, so that we can represent
$G_{k}(\mathbf{x})$ as

$\displaystyle
G_{k}(\mathbf{x})=\overline{g}_{1}(\mathbf{x})+\overline{g}_{2}(\mathbf{x})\left(1-\frac{x_{k-1}}{\kappa_{k}}\right)^{3/2}.$

Next, we deduce from Lemma 3.6 and the relation (3) that
$G_{k}^{(k-1)}(\mathbf{x})$ is a positive function with a proper
$1/2$-singularity and admits the same proper singularity function $\kappa_{k}$
as $G_{k}(\mathbf{x})$, in particular it is fully movable with respect to
$x_{1},\ldots,x_{k-2}$.

From there we apply Lemma 3.7 to the relation (4), noting that

$\displaystyle
F(\mathbf{x},y)=G_{k}^{(k-1)}(x_{1},\ldots,x_{k-2},x_{k-1}y,x_{k},\ldots,x_{t})$

is a positive function with a proper $1/2$-singularity and that by Remark 3.9
$F(\mathbf{x},y)$ has zeros $x_{1},\ldots,x_{k}$. Furthermore, it admits a
proper singularity function given by

$\displaystyle
R(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t},y)=\frac{1}{y}\kappa_{k}(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t}).$

Clearly $R$ is fully movable in $x_{1},\ldots,x_{k-2},x_{k}$ and $y$.
Consequently, using Lemma 3.7 the solution function
$y=G_{k-1}^{(k-1)}(\mathbf{x})$ is a positive function with a proper
$1/2$-singularity, and leading variable $x_{k-1}$, for which the singularity
function $\kappa_{k-1}=\kappa_{k-1}(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t})$
satisfies

$\displaystyle\kappa_{k-1}(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t})<\frac{\kappa_{k}(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t})}{G_{k-1}^{(k-1)}(\mathbf{x})}.$

Note that $G_{k-1}^{(k-1)}({\bf 0})=1$. Hence,
$G_{k-1}^{(k-1)}(\mathbf{x})>1$, and it follows that

$\displaystyle\kappa_{k-1}(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t})<\kappa_{k}(x_{1},\ldots,x_{k-2},x_{k},\ldots,x_{t}).$

Finally, we apply Lemma 3.6 on relation (5) and obtain that
$G_{k-1}(\mathbf{x})$ is a positive function with a proper $3/2$-singularity
and leading variable $x_{k-1}$. By another application of Lemma 3.5 we see
that we can change it back to the leading variable $x_{1}$, such that the
corresponding proper singularity function $\rho_{k-1}(x_{2},\ldots,x_{k})$
satisfies (19). ∎

We are now in a position to prove the two main results of the paper.

#### Proof of Theorem 1.1.

Proposition 3.8 implies that $G_{t}(\mathbf{x})$ is a positive function with a
proper $3/2$-singularity, and is aperiodic and analytically continuable with
respect to $x_{1}$. In particular, compare (7) with (17) and note that $x_{1}$
appears in $X$ only in the first power $x_{1}^{\binom{t}{0}}$. In this case,
the proper singularity function is explicitly given by

$\rho_{t}(x_{2},\ldots,x_{t})=\frac{1}{et}\prod_{j=2}^{t}x_{j}^{-\binom{t}{j-1}}.$

From there, successive applications of Proposition 3.10 imply that the
function $G_{k}(\mathbf{x})$ also has these properties for each $k\in[t]$.
Since the exponential is an entire function this also holds for
$G(\mathbf{x})=G_{0}(\mathbf{x})=\exp(G_{1}(\mathbf{x}))$. And we conclude the
proof by setting $x_{2}=\cdots=x_{t}=1$ then applying Proposition 3.1. ∎

#### Proof of Theorem 1.2.

Suppose that $(x_{2},\ldots,x_{t})$ is in a sufficiently small complex
neighbourhood $U$ of $(1,\ldots,1)$ in $\mathbb{C}^{t-1}$. From Proposition
3.8 then $k-1$ succesive applications of Proposition 3.10, we derive a local
representation of the form (7) holds for $G(\mathbf{x})=G_{k}(\mathbf{x})$,
with $\rho(x_{2},\ldots,x_{k})=\rho_{k}(x_{2},\ldots,x_{k})$ and $\alpha=3/2$,
when $x_{1}$ is close to $\rho_{k}(x_{2},\ldots,x_{k})$. Furthermore, by
continuity there exists $\delta>0$ such that the function $x_{1}\mapsto
G_{k}(\mathbf{x})$ is still analytically continuable to a region of the form
(8), with $\rho=\rho_{k}$. And we deduce from Proposition 3.1 the following
asymptotic estimate for the coefficients of $x_{1}$ in $G_{k}(\mathbf{x})$

$[x_{1}^{n}]\,G_{k}(\mathbf{x})=C_{k}(x_{2},\ldots,x_{k})\,n^{-5/2}\,\rho_{k}(x_{2},\ldots,x_{t})^{-n}\,(1+o(1))\qquad\text{as
}n\to\infty,$

for some non-zero function $C_{k}(x_{2},\ldots,x_{k})$ analytic in $U$. This
leads to a quasi-power situation for the probability generating function

$\mathbb{E}\left[x_{2}^{X_{2}}\cdots
x_{t}^{X_{t}}\right]=\frac{[x_{1}^{n}]\,G_{k}(\mathbf{x})}{[x_{1}^{n}]\,G_{k}(x_{1},1,\ldots,1)}\sim\frac{C_{k}(x_{2},\ldots,x_{k})}{C_{k}(1,\ldots,1)}\left(\frac{\rho_{k}(1,\ldots,1)}{\rho_{k}(x_{2},\ldots,x_{t})}\right)^{n}.$

Finally, setting $x_{j}=e^{u_{j}}$ and $\lambda_{n}=n$ in [D09, Theorem 2.22]
implies the claimed joint central limit theorem. Note that one could
alternatively apply [D09, Theorem 2.25]. Furthermore, the relation
$G_{0}(\mathbf{x})=\exp\left(G_{1}(\mathbf{x})\right)$ implies, as above, that
$G(\mathbf{x})=G_{0}(\mathbf{x})$ has the same singularities and singular
expansion as $G_{1}(\mathbf{x})$, up to a multiplicative constant. This
concludes the proof. ∎

##  4 Concluding remarks

With the help of a computer algebra system, making use of the representation
in Lemma 2.7, we have been able to compute the following table of numerical
values for the singularities $\rho_{t,k}$. We have stopped at $t=7$ since the
size of the system of functional equations needed to determine $\rho_{t,k}$
grows too fast.

| $k=1$ | $k=2$ | $k=3$ | $k=4$ | $k=5$ | $k=6$ | $k=7$
---|---|---|---|---|---|---|---
$t=1$ | 0.36788 |  |  |  |  |  |
$t=2$ | 0.14665 | 0.18394 |  |  |  |  |
$t=3$ | 0.07703 | 0.08421 | 0.12263 |  |  |  |
$t=4$ | 0.04444 | 0.04662 | 0.05664 | 0.09197 |  |  |
$t=5$ | 0.02657 | 0.02732 | 0.03092 | 0.04152 | 0.07358 |  |
$t=6$ | 0.01608 | 0.01635 | 0.01773 | 0.02184 | 0.03214 | 0.06131 |
$t=7$ | 0.00974 | 0.00984 | 0.01038 | 0.01204 | 0.01614 | 0.02583 | 0.05255
Table 1: Approximations of the radii of convergence of the generating
functions counting $k$-connected chordal graphs with tree-width at most $t$
for small values of $t$ and $k$.

Let us mention a recent result giving an estimate $cn^{-5/2}\gamma^{n}n!$ for
the number of labelled _planar_ chordal graphs with $\gamma\approx 11.89$
[CNR23]. Is is easy to see that the class of chordal graphs with tree-width at
most three is exactly the same as the class of chordal graphs not containing
$K_{5}$ as a minor, whose asymptotic growth is, according to Theorem 1.1 and
the table above, of the form $cn^{-5/2}\delta^{n}n!$ with
$\delta=1/\rho_{3,1}\approx 12.98$.

Furthermore, notice that if we denote by $C(x)$ and $B(x)$, respectively, the
generating functions of connected and 2-connected graphs in
$\mathcal{G}_{t,0}$, then Equation 4 reads for $k=1$

$\displaystyle C^{\prime}(x)=\exp(B^{\prime}(xC^{\prime}(x)).$

If $\rho_{C}$ and $\rho_{B}$ are the singularities of $C(x)$ and $B(x)$,
respectively, the condition for being subcritical is that
$\rho_{C}C^{\prime}(\rho_{C})<\rho_{B}$, so that the singularity of $C(x)$
arises as a branch-point in the former equation and is not inherited by that
of $B(x)$; in our case this condition is safistied because of Lemma 3.7.

Since the number of all chordal graphs grows like $2^{n^{2}/4}$, we know that
the singularity $\rho_{t}=\rho_{t,1}$ of chordal graphs with tree-wdith at
most $t$ goes to 0 as $t\to\infty$. The question is at which rate $\rho_{t}\to
0$ as $t\to\infty$. Since the exponential growth of $t$-trees is $(etn)^{n}$,
we have $\rho_{t}=O(1/t)$. And since the growth of all graphs of tree-width at
most $t$ is at most $(2^{t}tn)^{n}$, we also have
$\rho_{t}=\Omega(1/(t2^{t}))$. We leave as an open problem to narrow the gap
between the upper and lower bound. Heuristic arguments suggest that $\rho_{t}$
decreases exponentially in $t$.

As a final question, we consider letting $t=t(n)$ grow with $n$. Recall that a
class of labelled graphs is small when the number of graphs in the class grows
at most like $c^{n}n!$ for some $c>0$, and large otherwise. We know that the
class of all chordal graphs is large, while the class of chordal graphs with
tree-width at most $t$ is small for fixed $t$. Let us see that if
$t=(1+\epsilon)(\log n)$ then the class is large for each $\epsilon>0$. A
graph is split if the vertex set can be partitioned into a clique and an
independent set. It is well-known and easy to prove that split graphs are
chordal. Consider split graphs with a clique of size $t=(1+\epsilon)\log n$
and the complement an independent set, so that he largest clique is of size at
most $t+1$ and the tree-width at most $t$. Every edge between the clique and
the complement can be chosen independently, hence there are at least

$2^{(1+\epsilon)\log n(n-(1+\epsilon)\log n)}$

such graphs, a quantity that grows faster than $c^{n}n!$ for every $c>0$. We
leave as an open problem to determine at which order of magnitude between
$t=O(1)$ and $t=\log n$ the class ceases to be small.

### Acknowledgements

We gratefully acknowledge earlier discussions with Juanjo Rué and Dimitrios
Thilikos on the problem of counting chordal graphs with bounded tree-width.

The authors acknowledge support from the Marie Curie RISE research network
“RandNet” MSCA-RISE-2020-101007705. Moreover, M.D. was supported by the
Special Research Program SFB F50-02 “Algorithmic and Enumerative
Combinatorics”, and by the project P35016 “Infinite Singular Systems and
Random Discrete Objects” of the FWF (Austrian Science Fund). Additionally,
M.N. and C.R. acknowledge the financial support of the Spanish State Research
Agency through projects MTM2017-82166-P and PID2020-113082GB-I00, while M.N.
acknowledges support from the Severo Ochoa and María de Maeztu Program for
Centers and Units of Excellence (CEX2020-001084-M), and C.R. acknowledges
support from the grant Beatriu de Pinós BP2019, funded by the H2020 COFUND
project No 801370 and AGAUR (the Catalan agency for management of university
and research grants).

Jordi Castellví
Departament de Matemàtiques de la Universitat Politècnica de Catalunya (UPC),
Barcelona, Spain.
E-mail<EMAIL_ADDRESS>

Michael Drmota
Institute for Discrete Mathematics and Geometry of the Technische Universität
Wien, Austria.
E-mail<EMAIL_ADDRESS>

Marc Noy
Departament de Matemàtiques and Institut de Matemàtiques (IMTech) de la
Universitat Politècnica de Catalunya (UPC), and Centre de Recerca Matemàtica
(CRM), Barcelona, Spain.
E-mail<EMAIL_ADDRESS>

Clément Requilé
Departament de Matemàtiques and Institut de Matemàtiques (IMTech) de la
Universitat Politècnica de Catalunya (UPC), Barcelona, Spain.
E-mail<EMAIL_ADDRESS>


# Prospects for rare B decays at Belle II

Sam Cunliffe
Pacific Northwest National Laboratory, 902 Battelle Blvd., Richland, WA 99352,
USA.
<EMAIL_ADDRESS>
orcid: 0000-0003-0167-8641

Proceedings of the APS Division of Particles and Fields Meeting (DPF2017).
29 July – 4 August 2017, Fermilab, Batavia, IL, C170731.

Presented on behalf of the Belle II electroweak penguins working group.

BELLE2-CONF-PROC-2017-028; PNNL-SA-128762

## 1\. Introduction

Rare and flavour-changing neutral current (FCNC) decays of the beauty quark
are sensitive to the effects of undiscovered new particles, if they exist,
that are not included in the Standard Model of particle physics (SM). As FCNC
are forbidden at tree-level in the SM, these decays proceed by higher-order
loop-level diagrams (as shown in Figure 1). However any potential new physics
(NP) contribution does not suffer the same restriction and can occur at a
comparable size. As these NP diagrams contain virtual particles that can be
off-mass-shell, the mass scale in the search for NP with these decays is
typically many times larger than searches involving direct production.
Furthermore, several recent measurements of these decay processes [1, 2, 3,
4]111The result of Ref. [4] is also presented at this conference, talk by S.
Sandilya. are in tension with SM predictions, which has generated much
interest [5, 6, 7, 8, 9]222The analysis of Ref. [6] is also presented at this
conference, talk by W. Altmannshofer..

Figure 1:  The leading order Feynman diagrams for the FCNC $b\to s\ell\ell$
(where $\ell$ represents $e$, $\mu$, $\tau$ or $\nu$) and ${b\to(s,d)\gamma}$
in the SM.

The Belle II experiment [10] is a hermetic detector currently being
commissioned at the SuperKEKB accelerator [11] at the KEK laboratory in
Tsukuba, Japan. The first data are expected in early 2018, with a target
dataset of 50 ab-1 of $e^{+}e^{-}$ collisions by 2025. This dataset should
contain approximately $50\times 10^{9}$ $e^{+}e^{-}\to\mathit{\Upsilon}(4S)\to
B\bar{B}$ events. Measurements of rare and FCNC decays are an integral part of
the Belle II physics program.

## 2\. Previous and current $b$ physics experiments

The Belle II experiment is a second-generation B factory. The first generation
of B factories were the Belle and BaBar experiments [12] at the KEKB and PEP-
III accelerators at KEK and the SLAC National Accelerator Laboratory,
respectively. Following the first-generation B factories, the LHCb experiment
[13] at the LHC at CERN has been taking data since 2009. The LHC produces $pp$
collisions at high-energy and cannot exploit the $\mathit{\Upsilon}(4S)$
resonance, however $pp\to b\bar{b}$ quark pair-production is copious in the
forward region and LHCb utilises a single-arm forward spectrometer detector
design [13]. These three experiments have produced many noteworthy results,
several examples that are not discussed elsewhere in this document are
described in Refs [14, 15, 16, 17, 18, 19].

## 3\. The next-generation experiment: Belle II at SuperKEKB

### 3.1. Description

The SuperKEKB accelerator complex [11] is an upgrade of KEKB. The accelerator
beams are asymmetric in energy: 7 GeV for electrons (defining the forward
direction) and 4 GeV for positrons. The accelerator is designed to achieve a
factor 40 increase in instantaneous luminosity with respect to KEKB. This is
due to a more focused beam crossing and higher beam current, achieved by: new
superconducting magnets [20] at the interaction point, a new positron
dampening ring, and upgraded beam optics.

The Belle II detector [10] has been upgraded from Belle to cope with the much
higher luminosity and higher expected beam backgrounds. Around the collision
point, the silicon vertex detector has one more layer than Belle, with the
addition of two inner layers of depleted field-effect transistor pixel
detectors. The vertexing detectors are surrounded by the Belle II wire drift
chamber that is larger than in Belle. Two new particle identification systems
have been installed utilising Cherenkov radiation: in aerogel blocks in the
forward endcap and totally internally reflected inside quartz bars in the
barrel. The thallium-doped caesium iodide electromagnetic calorimeter has been
reused from Belle although the readout and electronics have been totally
replaced. The superconducting coil magnet is reused and will provide a 1.5 T
magnetic field for charge assignment and to measure tracking momentum of
charged particles. The inner barrel layers and the endcap of $K_{L}^{0}$ and
muon detector have been replaced with plastic scintillator, the outer barrel
layers reuse the original resistive plate chambers from Belle.

### 3.2. Status as of August 2017

The design data schedule is shown in Figure 2. In early 2018 the accelerator
is scheduled to provide $e^{+}e^{-}$ collisions at reduced luminosity for
detector commissioning333Operationally, and in Belle II literature, this is
referred to as “Phase 2” for historic reasons.. The vertexing pixel detector
and silicon vertex detector components will not be installed for this phase.
In 2019 the full vertexing detector will be installed and the accelerator will
provide physics collisions444Referred to as “Phase 3”. Should be thought of as
physics run 1..

Figure 2:  The scheduled integrated and peak luminosities of SuperKEKB.
Approximately ${10^{9}}$ ${B\bar{B}}$ pairs per ab-1 of data at the
$\mathit{\Upsilon}(4S)$ resonance will be collected. Adapted from [21].

## 4\. Theoretical framework and motivation

Figure 1 shows the leading order SM contributions to $b\to s$ processes.
However, in order to interpret results in a model-independent way, the theory
community typically works in a general expansion of an effective Hamiltonian,

$\mathcal{H}_{\rm
eff}\propto\sum_{i=1,..10,S,P}(C_{i}\mathcal{O}_{i}+C_{i}^{\prime}\mathcal{O}_{i}^{\prime}),$

in terms of effective operators, $\mathcal{O}_{i}^{(\prime)}$, containing the
non-pertubative low-energy effects and so-called “Wilson coefficients”,
$C_{i}$. The primes denote the chiral partner operator that is suppressed in
the SM. The Wilson coefficients may be expressed as:

$C_{i}=C_{i}^{\rm SM}+C_{i}^{\textrm{NP}},$

the sum of the SM (calculable with pertubative techniques) and NP (to be
determined) contributions.

Figure 3:  A diagrammatic representation of the effective (axial) vector
operators $\mathcal{O}_{9}$ ($\mathcal{O}_{10}$) and radiative photon operator
$\mathcal{O}_{7}$ (upper and lower respectively).

There are 24 operators and coefficients in the full expansion555More detail is
available in many references, for example Ref. [22].. However, there are three
which are most relevant for $b\to s$:

$\displaystyle\mathcal{O}_{9}$
$\displaystyle\propto(\bar{s}\gamma_{\mu}P_{L}b)(\overline{\ell}\gamma^{\mu}\ell);$
$\displaystyle\mathcal{O}_{10}$
$\displaystyle\propto(\bar{s}\gamma_{\mu}P_{L}b)(\overline{\ell}\gamma^{\mu}\gamma_{5}\ell);$
$\displaystyle\mathcal{O}_{7}$ $\displaystyle\propto
m_{b}(\bar{s}\sigma_{\mu\nu}P_{R}b)F^{\mu\nu}.$

These are the vector, axial vector, and radiative photon operators
respectively, and are shown schematically in Figure 3. This theoretical
procedure is appealing as it allows model-independent global fits to the
$C_{i}^{\textrm{NP}}$, searching for generic NP based on the form of the
interaction with SM fermions.

Furthermore, many observables are then constructed in such a way as to divide
out or otherwise remove the hadronic uncertainties. Such observables are
called “theoretically clean” or “form-factor independent”. Finally, it is also
possible to separate this whole framework by lepton flavour such that

$C_{i}\longrightarrow C_{i}^{\mu}\textrm{ and }C_{i}^{e}$

allowing for a lepton-flavour-dependent determination of any NP. This final
step is relevant given recent results [1, 2, 4], analyses may be found in Refs
[6, 7, 8].

## 5\. Inclusive measurements and full event interpretation

Inclusive decays, where the hadronic part of the decay is not specified, are
denoted ${B\to X(\gamma,\ell\ell)}$ with $X$ representing all hadrons. Their
measurements should be contrasted with measurements of exclusive decays to a
specific hadronic final state (such as ${B\to K^{*}\gamma}$, for example).

In terms of theory, SM predictions of inclusive decays are complementary to
exclusive as they typically suffer less, or orthogonal, uncertainty due to
hadronic form-factors. Predictions for the branching fractions of ${B\to
X_{s}\gamma}$ and ${B\to X_{s}\ell^{+}\ell^{-}}$ in the SM are calculated to a
precision of around $7\%$ [23, 24, 25] which should be compared to the SM
prediction for the branching fractions of ${B\to K^{*}\gamma}$ and ${B\to
K^{*}\mu^{+}\mu^{-}}$ at $20-23\%$ [26, 25].

Experimentally, there are two approaches for inclusive analyses: fully
inclusive and the so-called “sum-of-exclusive” methods. These are described in
the following subsections.

In addition, decays with neutrinos in the final state are often reconstructed
in the B factories as part of the full $e^{+}e^{-}\to\mathit{\Upsilon}(4S)\to
B\bar{B}$ event such that the missing energy is precisely known.

### 5.1. Sum-of-exclusive approach

The sum-of-exclusive reconstruction method is where the $X$ is specifically
reconstructed to several final states. This method is the only way to specify
the transition as $b\to s$ (or $b\to d$) since $X_{s}$ ($X_{d}$) can be
specified by the presence (absence) of a kaon in the final state. For example,
$X_{s}$ can be reconstructed as $Kn\pi$ and $3Km\pi$ where $n\geq 1$ and
$m\geq 0$. Furthermore, the flavour and momentum of the parent $B$ is known
without the need to perform full event interpretation (discussed in the
following section). The sum-of-exclusive analyses therefore have relatively
high efficiency to select signal events.

### 5.2. Full event interpretation

Fully inclusive measurements, and processes with neutrinos or other missing
energy often rely on “tagging” the other $B$ decay (the $B_{\rm tag}$) from
the $\mathit{\Upsilon}(4S)$. This is shown schematically in Figure 4. Such
analyses are challenging for LHCb due to the detector geometry and the
production mechanism $pp\to b\bar{b}$. Hermetic detectors, such as BaBar,
Belle, and Belle II are able to precisely reconstruct
$\mathit{\Upsilon}(4S)\to B\bar{B}$ decays and therefore better suited to
performing such measurements. This is illustrated qualitatively in Figure 5.

Figure 4:  A schematic of a hadronically tagged decay where full event
reconstruction is possible. In this example the tag decay is $B\to D^{0}(\to
K\pi)\pi$, however several decay chains with high branching fractions or
efficiencies are included [27]. The signal is able to be constructed from
missing energy (i.e. neutrinos) or as an inclusive decay if only a photon or
(pair of) leptons are reconstructed.

Figure 5:  Examples of event displays from Belle II simulation (left) and LHCb
data (right). Belle II is hermetic and can exploit the clean
$e^{+}e^{-}\to\mathit{\Upsilon}(4S)\to B\bar{B}$ production. LHCb does not
have full coverage and the production mechanism $p^{+}p^{-}\to b\bar{b}$ is
less well known. Belle II is therefore better suited to perform fully
inclusive measurements and measure processes with neutrinos in the final
state. Right-hand figure from [28].

There are two further approaches to reconstruct the full event, dependent on
the final state of the $B_{\rm tag}$ decay. The $B_{\rm tag}$ decay may be
reconstructed in a fully hadronic final state, in which case the momentum of
the signal $B$ is known precisely, independent of the signal decay. However,
fully reconstructed hadronic decays suffer from low branching fractions with
respect to semi-leptonic decays. Thus semi-leptonic tagging has a somewhat
higher efficiency at the expense of losing the full momentum (and parent
charge) information in most signal decays. Newer full event interpretation
(FEI) algorithms have been developed for Belle II [27] which include several
final states and utilise advances in machine learning. The efficiencies of FEI
are shown in Table 1.

Parent | Tagging | Belle II FEI | Belle MC Belle II FEI | Belle
---|---|---|---|---
$B^{\pm}$ | Hadronic | 0.61% | 0.49% | 0.28%
Semi-leptonic | 1.45% | 1.42% | 0.67%
$B^{0}$ | Hadronic | 0.34% | 0.33% | 0.18%
Semi-leptonic | 1.25% | 1.33% | 0.63%
Table 1:  Tagging efficiencies for Belle II FEI algorithms determined with
simulation of the Belle II and Belle detectors and the original Belle
efficiency evaluated on data. Taken from [27, 29].

## 6\. Prospects at Belle II

### 6.1. Inclusive ${b\to(s,d)\gamma}$

The inclusive radiative penguin measurements provide important constraints on
many possible NP scenarios such as models with extended Higgs sectors and
supersymmetry [25, 30]. Measurements of the branching fraction of ${B\to
X_{s}\gamma}$ (${B\to X_{d}\gamma}$) from the first generation of B factories
have been combined [31] to give a precision of about 4% (30%). These averages
are in very good agreement with the SM predictions which are calculated to
around 7% precision [24]. With Belle II, the single experiment precision for
${B\to X_{s}\gamma}$ measured with a semi-leptonic tag is expected to quickly
overtake the the combination, and should be known to less than 3% uncertainty.
The full precision is expected to reach percent-level. For ${B\to
X_{d}\gamma}$, the precision will be improved to around 15% with 50 ab-1. In
the case of $X_{d}$ this improvement is due both to a larger data sample, and
to the upgraded particle identification system which will aid discrimination
against the large background from ${B\to X_{s}\gamma}$ processes (namely where
a kaon track is misidentified as a pion).

It is also possible to construct the CP-asymmetry, defined in general as:

$A_{\rm CP}\equiv\frac{\Gamma\left[\bar{B}\to\bar{f}\right]-\Gamma\left[B\to
f\right]}{\Gamma\left[\bar{B}\to\bar{f}\right]+\Gamma\left[B\to f\right]},$

where $\Gamma$ is the partial width for any decay of a $B$ meson to a final
state $f$, as well as the isospin asymmetry, defined as:

$\Delta_{0+}\equiv\frac{\Gamma\left[{B^{0}}\to{f^{0}}\right]-\Gamma\left[B^{\pm}\to
f^{\pm}\right]}{\Gamma\left[{B^{0}}\to{f^{0}}\right]+\Gamma\left[B^{\pm}\to
f^{\pm}\right]}.$

Another related observable is the difference of CP-violation between the
charged and neutral $B$ meson decays:

$\Delta A_{\rm CP}\equiv A_{\rm CP}\left[B^{\pm}\to f^{\pm}\right]-A_{\rm
CP}\left[B^{0}\to f^{0}\right].$

These observables can be defined for an inclusive decay, such as ${B\to
X_{s}\gamma}$ as,

$\displaystyle A_{\rm CP}$ $\displaystyle=\frac{\Gamma\left[\bar{B}\to
X_{s}\gamma\right]-\Gamma\left[B\to
X_{\bar{s}}\gamma\right]}{\Gamma\left[\bar{B}\to
X_{s}\gamma\right]+\Gamma\left[B\to X_{\bar{s}}\gamma\right]},$
$\displaystyle\Delta_{0+}$
$\displaystyle=\frac{\Gamma\left[{B^{0}}\to{X_{s}}\gamma\right]-\Gamma\left[B^{\pm}\to
X_{s}\gamma\right]}{\Gamma\left[{B^{0}}\to{X_{s}}\gamma\right]+\Gamma\left[B^{\pm}\to
X_{s}\gamma\right]},$ $\displaystyle\Delta A_{\rm CP}$ $\displaystyle=A_{\rm
CP}\left[B^{\pm}\to X_{s}^{\pm}\gamma\right]-A_{\rm CP}\left[B^{0}\to
X_{s}^{0}\gamma\right].$

In all cases, the flavour and CP state of the parent $B$ is determined from
the tag.

Such observables have reduced experimental systematic effects, as well as
reduced theoretical uncertainty from hadronic form-factors. Experimental
measurements are therefore more precise than the branching fractions, for
example $A_{\rm CP}$ and $\Delta_{0+}$ for ${B\to X_{s}\gamma}$ are both
around 2% [32, 33], for ${B\to X_{d}\gamma}$ they are around 30%. With 50 ab-1
at Belle II, measurements are expected to reach sub-percent-level precision
for $A_{\rm CP}$ and $\Delta_{0+}$ in ${B\to X_{s}\gamma}$, and around percent
level precision for ${B\to X_{d}\gamma}$. Figure 6 shows the precision on
$A_{\rm CP}$ and $\Delta A_{\rm CP}$ as a function of integrated luminosity
collected at the $\mathit{\Upsilon}(4S)$ resonance.

Figure 6:  Sensitivity to $A_{\rm CP}$ and $\Delta A_{\rm CP}$ in ${B\to
X_{(s,\,d)}\gamma}$ decays. To appear in [29].

### 6.2. Lepton (non) universality and inclusive ${b\to
s(e^{+}e^{-},\,\mu^{+}\mu^{-})}$

Recent experimental tests of lepton universality in ${b\to s\ell^{+}\ell^{-}}$
decays have shown deviation from the SM predictions [1, 2]. Deviations are not
too far from statistical significance and are therefore the source of much
discussion within the community [5, 6, 7, 8]. In addition to these
measurements a somewhat longstanding discrepancy in the angular analysis of
${B^{0}\to K^{*0}\mu^{+}\mu^{-}}$ [3] has been explored for both ${B\to
K^{*}e^{+}e^{-}}$ and ${B\to K^{*}\mu^{+}\mu^{-}}$ by Belle [4].

In global fits to the Wilson coefficients [6, 7, 8], these discrepancies
prefer a non-zero $C_{9}^{\textrm{NP}}$. In terms of NP interpretations,
models with an extended electroweak sector, such as a new vector boson
$Z^{\prime}$, have been suggested. There has been some debate in the theory
community about possible non-NP explanations for these deviations, such as
underestimated hadronic uncertainty, or an underestimated contribution from
high-order diagrams involving charm quarks in the ${b\to s\mu^{+}\mu^{-}}$
transition [34].

References [1, 2] present the measurement of lepton universality ratios
conventionally defined,

$R_{K^{(*)}}\equiv\frac{\acs{BF}\left[B\to
K^{(*)}\mu^{+}\mu^{-}\right]}{\acs{BF}\left[B\to K^{(*)}e^{+}e^{-}\right]},$

where $\mathcal{B}$ is the branching fraction. In the SM these ratios are
predicted to be very close to unity within the region of the squared invariant
mass of the lepton pair, ${1<q^{2}<6\leavevmode\nobreak\
\mathrm{GeV}^{2}/c^{4}}$ [35]. Belle II will not overtake the precision of
these measurements but will perform an independent verification. With
approximately 10 ab-1 (3 ab-1) Belle II will reach the current precision of
$R_{K}$ ($R_{K^{*}}$). However an analogous definition in terms of the
inclusive decays,

$R_{X_{s}}\equiv\frac{\acs{BF}\left[B\to
X_{s}\mu^{+}\mu^{-}\right]}{\acs{BF}\left[B\to X_{s}e^{+}e^{-}\right]},$ (1)

can be made. Such an observable would be challenging for LHCb, but could be
measured with percent-level precision at Belle II as shown in Figure 7.

Figure 7:  Sensitivity to an inclusive lepton universality ratio defined in
Equation 1, for two regions of squared invariant mass of the lepton pair. To
appear in [29].

It is also possible to measure the differential branching fraction
($\text{d}\mathcal{B}/\text{d}q^{2}$), $A_{\rm CP}$, and perform an angular
analysis for these inclusive ${B\to Xe^{+}e^{-}}$ and ${B\to X\mu^{+}\mu^{-}}$
decays. In contrast to the angular analysis of the exclusive ${B\to
K^{*}\mu^{+}\mu^{-}}$ decay with many observables, in an inclusive angular
analysis it is only possible to measure the forward-backward asymmetry of the
leptons ($A_{\rm FB}$). Current precision [36, 37, 38] is around 30% for
$\text{d}\mathcal{B}/\text{d}q^{2}$, and 20% for $A_{\rm FB}$ and $A_{\rm
CP}$. Belle II will reach a precision of around 7% for
$\text{d}\mathcal{B}/\text{d}q^{2}$ and $2-3\%$ for $A_{\rm FB}$ and $A_{\rm
CP}$. Figures 8 and 9 show the sensitivity for the former two of these
observables.

Figure 8:  Sensitivity to the differential branching fraction
($\text{d}\mathcal{B}/\text{d}q^{2}$) in ${B\to X_{s}\ell^{+}\ell^{-}}$
decays, for three regions of squared invariant mass of the lepton
($\ell=e,\,\mu$) pair. To appear in [29].  Figure 9:  Sensitivity to the
forward-backward asymmetry of the leptons ($A_{\rm FB}$) in ${B\to
X_{s}\ell^{+}\ell^{-}}$ decays, for three regions of squared invariant mass of
the lepton ($\ell=e,\,\mu$) pair. To appear in [29].

### 6.3. ${b\to s\nu\bar{\nu}}$

Assuming that the ${B\to K^{*}\nu\bar{\nu}}$ decay occurs at the rates
predicted by the SM [39, 40],

$\displaystyle\acs{BF}\left[B^{+}\to K^{+}\nu\bar{\nu}\right]$
$\displaystyle=(4.7\pm 0.6)\times 10^{−6};$
$\displaystyle\acs{BF}\left[B^{0}\to K^{*0}\nu\bar{\nu}\right]$
$\displaystyle=(9.5\pm 1.1)\times 10^{−6},$

Belle II will observe the process and measure the branching fraction with
$10-11\%$ uncertainty in 50 ab-1. This decay mode is of similar interest to
${B^{0}\to K^{*0}\mu^{+}\mu^{-}}$ in terms of sensitivity to
$C_{9,10}^{\textrm{NP}}$, however probing ${B\to K^{*}\nu\bar{\nu}}$ decays
also provides orthogonal information. For ${B\to K^{*}\nu\bar{\nu}}$, the
factorisation of hadronic effects is exact (since neutrinos are electrically
neutral) and could be used to extract $B\to K$ hadronic form-factors to high
accuracy [29]. It is also possible that ${B\to K^{*}\nu\bar{\nu}}$ can provide
model-dependent information to disentangle possible NP effects behind the
current anomalies [39].

Experimentally, it is possible to use full event reconstruction and construct
the sum of the missing energy and missing momentum in the $e^{+}e^{-}$ centre-
of-momentum frame. The distribution of this variable is shown in Figure 10.
Such a variable is promising for separating signal from background, either for
a counting analysis or as the independent variable in a maximum likelihood
fit. Assuming observation at Belle II, it should also be possible to measure
fraction of longitudinal polarisation of the $K^{*}$ in $B\to
K^{*}\nu\bar{\nu}$ to around 20% precision.

Figure 10:  The distribution of the missing energy and missing momentum in the
centre-of-momentum frame for ${B\to K^{*}\nu\bar{\nu}}$ signal decays (red)
and various background categories (solid colour stack by cross-section). To
appear in [29].

### 6.4. ${b\to(s,d)\tau^{+}\tau^{-}}$

Decays with the ${b\to(s,d)\tau^{+}\tau^{-}}$ transition are thus-far
unobserved. Current experimental limits [41, 42] are of the order of $10^{-3}$
which is rather far from the SM predictions [43, 44] of,

$\displaystyle\acs{BF}\left[B_{s}^{0}\to\tau^{+}\tau^{-}\right]$
$\displaystyle=(7.73\pm 0.49)\times 10^{-7};$
$\displaystyle\acs{BF}\left[B^{0}\to\tau^{+}\tau^{-}\right]$
$\displaystyle=(2.22\pm 0.19)\times 10^{-8};$
$\displaystyle\acs{BF}\left[B^{+}\to K^{+}\tau^{+}\tau^{-}\right]$
$\displaystyle=(1.22\pm 0.10)\times 10^{-7}.$

Assuming these SM branching fractions, Belle II will be able to set limits of
around $10^{-6}$ and $10^{-5}$ for ${B^{0}\to\tau^{+}\tau^{-}}$ and ${B^{+}\to
K^{+}\tau^{+}\tau^{-}}$ respectively. The sensitivity to
${B_{s}\to\tau^{+}\tau^{-}}$ decays is highly dependent on SuperKEKB running
at the $\mathit{\Upsilon}(5S)$ resonance, which has not yet been finalised.

## 7\. Conclusions

The Belle II experiment at SuperKEKB will collect first collisions
commissioning data in 2018. Full-detector physics data are expected in 2019.
At time of writing, the Belle II detector has been rolled into the collision
point at SuperKEKB and is taking cosmic ray commissioning data.

Rare radiative and electroweak penguin processes have recently shown
deviations from SM predictions, and form an integral part of the Belle II
physics program. Belle II will have access to several decay modes that are
challenging at the LHCb experiment, such as ${B\to K^{*}\nu\bar{\nu}}$ and
inclusive decays. Belle II will provide independent verification of the
deviations observed by LHCb, such as lepton universality in ${B\to
K^{*}(e^{+}e^{-},\,\mu^{+}\mu^{-})}$ decays.

### Acknowledgements

The author would like to thank Akimasa Ishikawa, Elisa Manoni, and Phillip
Urquijo for working group collaboration and for their contributions to Ref.
[29] from which these proceedings draw upon. The author is supported by US DOE
grant FWP61210.

SM

    Standard Model of particle physics
NP

    new physics (particles, and theories not included in the SM)
FCNC

    flavour-changing neutral current
FEI

    full event interpretation
$\mathcal{B}$

    branching fraction
$\text{d}\mathcal{B}/\text{d}q^{2}$

    differential branching fraction
$A_{\rm FB}$

    the forward-backward asymmetry of the leptons
$\Delta_{0+}$

    isospin asymmetry
$A_{\rm CP}$

    CP-asymmetry
$\Delta A_{\rm CP}$

    difference in CP-asymmetries between the charged and neutral modes

## References

  * [1] R. Aaij et al., LHCb, Test of lepton universality using $B^{+}\rightarrow K^{+}\ell^{+}\ell^{-}$ decays, Phys. Rev. Lett. 113 (2014) 151601, arXiv:1406.6482.
  * [2] R. Aaij et al., LHCb, Test of lepton universality with $B^{0}\rightarrow K^{*0}\ell^{+}\ell^{-}$ decays, arXiv:1705.05802.
  * [3] R. Aaij et al., LHCb, Angular analysis of the $B^{0}\to K^{*0}\mu^{+}\mu^{-}$ decay using 3 fb-1 of integrated luminosity, JHEP 02 (2016) 104, arXiv:1512.04442.
  * [4] S. Wehle et al., Belle, Lepton-Flavor-Dependent Angular Analysis of $B\to K^{\ast}\ell^{+}\ell^{-}$, Phys. Rev. Lett. 118 (2017) 11, 111801, arXiv:1612.05014.
  * [5] S. L. Glashow et al., Lepton Flavor Violation in $B$ Decays?, Phys. Rev. Lett. 114 (2015) 091801, arXiv:1411.0565.
  * [6] W. Altmannshofer et al., Interpreting Hints for Lepton Flavor Universality Violation, arXiv:1704.05435.
  * [7] B. Capdevila et al., Patterns of New Physics in $b\to s\ell^{+}\ell^{-}$ transitions in the light of recent data, arXiv:1704.05340.
  * [8] G. Hiller and I. Nisandzic, $R_{K}$ and $R_{K^{\ast}}$ beyond the standard model, Phys. Rev. D96 (2017) 3, 035003, arXiv:1704.05444.
  * [9] F. Sala and D. M. Straub, A New Light Particle in B Decays?, arXiv:1704.06188.
  * [10] T. Abe et al., Belle II, Belle II Technical Design Report, arXiv:1011.0352.
  * [11] Y. Ohnishi et al., Accelerator design at SuperKEKB, Prog. Theo. Exp. Phys. 2013 (2013) 03A011.
  * [12] A. J. Bevan et al., Belle, BaBar, The Physics of the B Factories, Eur. Phys. J. C74 (2014) 3026, arXiv:1406.6311.
  * [13] A. A. Alves, Jr. et al., LHCb, The LHCb Detector at the LHC, JINST 3 (2008) S08005.
  * [14] K. Abe et al., Belle, Observation of large CP violation in the neutral $B$ meson system, Phys. Rev. Lett. 87 (2001) 091802, arXiv:hep-ex/0107061.
  * [15] B. Aubert et al., BaBar, Observation of CP violation in the $B^{0}$ meson system, Phys. Rev. Lett. 87 (2001) 091801, arXiv:hep-ex/0107013.
  * [16] S. K. Choi et al., Belle, Observation of a narrow charmonium-like state in exclusive $B^{\pm}\to K^{\pm}\pi^{+}\pi^{-}J/\psi$ decays, Phys. Rev. Lett. 91 (2003) 262001, arXiv:hep-ex/0309032.
  * [17] J. P. Lees et al., BaBar, Evidence for an excess of $\bar{B}\to D^{(*)}\tau^{-}\bar{\nu}_{\tau}$ decays, Phys. Rev. Lett. 109 (2012) 101802, arXiv:1205.5442.
  * [18] V. Khachatryan et al., LHCb, CMS, Observation of the rare $B^{0}_{s}\to\mu^{+}\mu^{-}$ decay from the combined analysis of CMS and LHCb data, Nature 522 (2015) 68–72, arXiv:1411.4413.
  * [19] R. Aaij et al., LHCb, Observation of $J/\psi p$ Resonances Consistent with Pentaquark States in $\mathit{\Lambda}_{b}^{0}\to J/\psi K^{-}p$ Decays, Phys. Rev. Lett. 115 (2015) 072001, arXiv:1507.03414.
  * [20] N. Ohuchi et al., Design and Construction of the SuperKEKB QC1 Final Focus Superconducting Magnets, IEEE Trans. Appl. Supercond. 25 (2015) 3, 4001204.
  * [21] http://www-superkekb.kek.jp/.
  * [22] T. Mannel, Effective Field Theories in Flavor Physics, Springer Tracts Mod. Phys. 203 (2004) .
  * [23] T. Huber et al., Logarithmically Enhanced Corrections to the Decay Rate and Forward Backward Asymmetry in $\bar{B}\to X_{s}\ell^{+}\ell^{-}$, Nucl. Phys. B802 (2008) 40–62, arXiv:0712.3009.
  * [24] M. Misiak et al., Updated NNLO QCD predictions for the weak radiative B-meson decays, Phys. Rev. Lett. 114 (2015) 22, 221801, arXiv:1503.01789.
  * [25] A. Paul and D. M. Straub, Constraints on new physics from radiative $B$ decays, JHEP 04 (2017) 027, arXiv:1608.02556.
  * [26] A. Bharucha et al., $B\to V\ell^{+}\ell^{-}$ in the Standard Model from light-cone sum rules, JHEP 08 (2016) 098, arXiv:1503.05534.
  * [27] T. Keck, The Full Event Interpretation for Belle II, masters thesis, Karlsruher Institut für Technologie, 2014.  EKP-2015-00001.
  * [28] https://lbevent.cern.ch/EventDisplay/index.html.
  * [29] E. Kou, P. Urquijo, et al., Belle II, The Belle II Physics Book, Under preparation, to be submitted to Prog. Theor. Exp. Phys. (2017).
  * [30] M. Misiak and M. Steinhauser, Weak radiative decays of the B meson and bounds on $M_{H^{\pm}}$ in the Two-Higgs-Doublet Model, Eur. Phys. J. C77 (2017) 3, 201, arXiv:1702.04571.
  * [31] Y. Amhis et al., HFLAV, Averages of $b$-hadron, $c$-hadron, and $\tau$-lepton properties as of summer 2016, arXiv:1612.07233. Latest values available online at http://www.slac.stanford.edu/xorg/hflav.
  * [32] S. Nishida et al., Belle, Measurement of the CP asymmetry in $B\to X_{s}\gamma$, Phys. Rev. Lett. 93 (2004) 031803, arXiv:hep-ex/0308038.
  * [33] J. P. Lees et al., BaBar, Measurements of direct CP asymmetries in $B\to X_{s}\gamma$ decays using sum of exclusive decays, Phys. Rev. D90 (2014) 9, 092001, arXiv:1406.0534.
  * [34] J. Lyon and R. Zwicky, Resonances gone topsy turvy - the charm of QCD or new physics in $b\to s\ell^{+}\ell^{-}$?, arXiv:1406.0566.
  * [35] G. Hiller and F. Kruger, More model-independent analysis of $b\to s$ processes, Phys. Rev. D69 (2004) 074020, arXiv:hep-ph/0310219.
  * [36] M. Iwasaki et al., Belle, Improved measurement of the electroweak penguin process $B\to X_{s}\ell^{+}\ell^{-}$, Phys. Rev. D72 (2005) 092005, arXiv:hep-ex/0503044.
  * [37] J. P. Lees et al., BaBar, Measurement of the $B\to X_{s}\ell^{+}\ell^{-}$ branching fraction and search for direct CP violation from a sum of exclusive final states, Phys. Rev. Lett. 112 (2014) 211802, arXiv:1312.5364.
  * [38] Y. Sato et al., Belle, Measurement of the lepton forward-backward asymmetry in $B\rightarrow X_{s}\ell^{+}\ell^{-}$ decays with a sum of exclusive modes, Phys. Rev. D93 (2016) 3, 032008, arXiv:1402.7134. Phys. Rev. D93 (2016), 5, 059901.
  * [39] A. J. Buras et al., $B\to{K}^{\left(\ast\right)}\nu\bar{\nu}$ decays in the Standard Model and beyond, JHEP 02 (2015) 184, arXiv:1409.4557.
  * [40] D. M. Straub, $B\to{K}^{\left(\ast\right)}\nu\bar{\nu}$ SM predictions, 2015, BELLE2-MEMO-2016-007.
  * [41] J. P. Lees et al., BaBar, Search for $B^{+}\rightarrow K^{+}\tau^{+}\tau^{-}$ at the BaBar experiment, Phys. Rev. Lett. 118 (2017) 3, 031802, arXiv:1605.09637.
  * [42] K. De Bruyn, LHCb, Search for the rare decays $B^{0}_{(s)}\to\tau^{+}\tau^{-}$, 2016, LHCb-CONF-2016-011.
  * [43] C. Bobeth et al., $B_{s,d}\to\ell^{+}\ell^{-}$ in the Standard Model with Reduced Theoretical Uncertainty, Phys. Rev. Lett. 112 (2014) 101801, arXiv:1311.0903.
  * [44] D. Du et al., Phenomenology of semileptonic B-meson decays with form factors from lattice QCD, Phys. Rev. D93 (2016) 3, 034005, arXiv:1510.02349.

  *[FCNC]: flavour-changing neutral current
  *[SM]: Standard Model of particle physics
  *[NP]: new physics (particles, and theories not included in the )
  *[FEI]: full event interpretation
  *[$\mathcal{B}$]: branching fraction
  *[$\text{d}\mathcal{B}/\text{d}q^{2}$]: differential branching fraction
  *[$A_{\rm FB}$]: the forward-backward asymmetry of the leptons