text:
# Asymmetric evolving random networks

## 1 Introduction

Evolving graphs arise naturally in the modelization of communication networks, but also of social organizations and biological phenomena : brain formation, genetic regulations, etc. Until recently, quantitative data were scarce, but the situation is changing very quickly . In many important cases the laws governing the evolution of the network are unknown but non deterministic, and the final number of nodes is rather large. This explains why physicists (see the reviews  and references therein) have been developping recently random graph techniques in the thermodynamic limit to understand some peculiar features, the most salient being large degree distributions, that seem to occur in an unexpected variety of situations.

Many cases of interest lead to oriented graph models, for which the in- and out-degree distributions can be governed by different laws. This was one of the basic observations in the study of the yeast genetic regulatory network presented in : a single gene may participate to the regulation of many other genes – the law for out-degrees seems to be large –, but each gene is only regulated by a few other genes – the law for in-degrees seems to have finite moments. A biological interpretation for the asymmetry is that the few promoter-repressor sites for each gene bind only to specific proteins, but that along the genome many promoter-repressor sites are homologous. One of our aims is to work with a model that incorporates such an asymmetry.

We shall follow quite closely the philosophy of , and in particular pay attention not only to global quantities, but also to local-in-time profiles. We feel that for evolving networks this is a crucial condition to extract relevant information, because as we shall see, global quantities (averaged over time) give a distorded view of the network. On the other hand, it is hard experimentally to access local quantities, either because the ages are not known, or because their consideration would reduce the statistics down to an unacceptable level. But the amount of available information is growing very rapidly, and one can hope that local quantities will become accessible in a near future.

The model we study is the natural evolving cousin of the static maximal entropy model with given in-degree distribution . Starting from a single vertex at time $`1`$, a new vertex is created at each time step – so that at time $`t`$, the size of the system, i.e. the number of vertices, is $`t`$ – and new oriented edges are created with specified probabilistic rules. An arbitrary probability generating function $`T`$ encodes the parameters of the model in the thermodynamic (large $`t`$) limit. Precise definitions are given in the next section.

Our main results are the following :

The global and local in-degree distributions are given by $`T`$, see eq.(3), whereas the global out-degree distribution is geometric with average $`T^{}(1)`$, see eq.(5). The local out-degree distribution is poissonian but age dependant, eq.(4). In the case of a static maximal entropy random graph with the same in-degree distribution (), the distribution of out-degrees would be poissonian.

The global structure of connected components is studied via a generating function which satisfies a differential equation, leading to recursion relations for the distribution of component sizes, see eq.(12). This is illustrated by analytical computations in the case when $`T(z)`$ is a polynomial of degree $`1`$.

The general criterion for the absence of a component containing a finite fraction of the sites in the thermodynamic limit is that the average $`\alpha T^{}(1)`$ be $`1/2`$ and the variance $`\gamma T^{}(1)+T^{\prime \prime }(1)T^{}(1)^2`$ be $`1/4`$. In that case the system contains components whose sizes scale like a power of the total size of the graph, see eq.(19); equivalently, the probability distribution for component sizes has an algebraic queue, see eq.(18). Above the threshold (when $`T^{}(1)>1/2`$ or $`\gamma >1/4`$) this probability distribution is defective but decreases exponentially see eq.(21). The boundary separating the percolating and non percolating phases is $`\gamma =1/4`$ and $`\alpha <1/2`$. In the percolating phase, but close to this boundary, $`\gamma 1/4`$ is $`>0`$ but small and the giant component is exponentially small, see eq.(20). This situation, somehow reminiscent of the Kosterlitz-Thouless transition, had already been observed in a variety of models .

We compare the percolation criterion with the one that emerges from the study of a static maximal entropy random graph with the same in- and out-degree distributions as our evolving graph (). In the static case, the growth of the giant component is generically linear close to the threshold. But we show that if $`T(z)`$ leads to a percolating static graph, it is automatically percolating for the evolving graph model. The intuitive explanation lies in the inhomogeneities of the evolving graph : the environment of an old vertex is denser than what a static model produces. And indeed, the giant component profile close to threshold is very asymmetric, see eqs.(28,29).

In the thermodynamic limit, the finite components are trees, and we derive a direct enumeration formula to count for their abundance eq.(16). This can be used to describe all local in time profiles of finite components, a result we also recover for one time quantities via a generating function aproach eq.(13). In the appendix, we give a proof of the equivalence of the generating function approach and tree enumeration, a question that was left opened in .

We have confronted our analytical results with numerical simulations whenever possible, our preferred example being when $`T`$ is a geometric distribution.

Aknowledgement : we thank Denis Bernard for a careful reading of the manuscript and for his kind permission to include the results of section. 5.2, that where obtained with him some time ago.

## 2 The model

The random graphs we consider are constructed according to the following rules :

1. For $`t=1,2,\mathrm{}`$, we denote by $`𝒢_t`$ the set of simple graphs with vertex set $`V_t=[1,\mathrm{},t]`$, i.e. the set of pairs $`(V_t,E_t)`$ where $`E_t`$, the set of edges of the graph, is a subset of $`\{(i,j),1i<jt\}`$. We orient the graph $`(V_t,E_t)`$ by saying that $`(i,j)E_t`$ is an edge from $`i`$ to $`j`$ : an edge always goes from an older to a younger vertex. Note that $`𝒢_1=\{(\{1\},\mathrm{})\}`$ contains a single graph, made of one vertex but no edge.
2. An evolving graph is a sequence $`G=\left(G_t\right)_{t1}=\left((V_t,E_t)\right)_{t1}`$, where $`G_t𝒢_t`$ for $`t1`$, and for $`t2`$, $`G_{t1}`$ is the induced subgraph of $`G_t`$ obtained by removing vertex $`t`$ and all edges adjacent to it. Stated differently, $`G_t`$ for $`t2`$ is obtained from $`G_{t1}`$ by adding vertex $`t`$ and some edges of the form $`(i,t)`$, $`i<t`$. This model of evolution implies that knowing $`G_t`$ is equivalent to knowing $`G_1,\mathrm{},G_{t1},G_t`$. We write $`𝒢`$ for the set of evolving graphs.
3. In addition to these rules of construction, we put a probability measure $`p`$ on the set of evolving graphs. If $`G`$ is an evolving graph, we denote by $`\widehat{G}_t`$ the number of edges arriving at vertex $`t`$ in $`G_t`$ (which is the same as the number of edges arriving at $`t`$ in $`G_t^{}`$ for any $`t^{}t`$). We want to fix the probability distributions for the number of edges arriving at vertices $`1,2,\mathrm{}`$, i.e. we impose $`p(\{G𝒢,\widehat{G}_t=k\})=\tau _{t,k}`$ for a given sequence of probability distributions $`\{\tau _{t,k},t1,0kt1\}`$,$`\tau _{t,k}0`$, $`_k\tau _{t,k}=1`$. Since this criterion is far from fixing unambiguously the probability law, we shall only be interested in the one which doesn’t introduce any other bias, i.e. the one which maximizes entropy. Then a simple computation shows that for $`H_t`$ in $`𝒢_t`$,

$$p(\{G𝒢,G_t=H_t\})=\underset{1st}{}\frac{\tau _{s,\widehat{H}_s}}{\left(\genfrac{}{}{0pt}{}{s1}{\widehat{H}_s}\right)}.$$

Note that we did not worry about the size of the sequence defining an evolving graph. In fact, we shall as often as possible suppose it is infinite.

## 3 Notations and basic results

### 3.1 Generating functions

For any vertex $`v1`$, let $`T_v`$ be the generating function for the incoming degree distribution :

$$T_v(z)\underset{k=0}{\overset{v1}{}}\tau _{v,k}z^k$$

We shall be mostly interested in the thermodynamic limit, i.e. in $`t`$ independant features of the large $`t`$ behavior of $`G_t`$ when $`G`$ is a random element in $`(𝒢,p)`$. A typical example is the behavior of $`lim_t\mathrm{}|E_t|/|V_t|`$ 111Here and in the sequel, $`|S|`$ denote the number of elements of the finite set $`S`$.. Obviously, this limit does not exist for any a priori choice of the $`\tau _{v,k}`$’s. The study of thermodynamic convergence for this quantity and others would be of independent interest, but we shall see that a simple assumption ensures that many quantities of interest have a thermodynamic limit : we impose that the sequence of functions $`T_v(z)`$ converges to a probability generating function

$$T(z)\underset{k0}{}\frac{\tau _k}{k!}z^k$$
(1)
in such a way that the sequence of averages and variances converges to that of $`T(z)`$.

This property implies in particular that, for any $`k`$, $`\tau _{v,k}`$ tends to $`\frac{\tau _k}{k!}`$ for large $`v`$. Moreover, we will often use the fact that $`T(1)=1`$. We use the notations $`\alpha T^{}(1)`$ and $`\gamma T^{\prime \prime }(1)+T^{}(1)T^{}(1)^2`$ for the average and variance of $`T`$.

As a technical hypothesis, to avoid several pathologies, we shall always implicitely assume that $`\tau _0=T(0)>0`$.

### 3.2 A preliminary formula

We shall sometimes be lead to consider situations in which a new vertex $`t+1`$ appears and connects to the rest of the graph avoiding $`m`$ forbidden vertices. This will happen, for instance, if one is interested in the distribution of connected components in the graph. In this section we would like to give a general formula for such situations. Hence, let $`\alpha _{t+1,m}`$ be the probability for a new vertex $`t+1`$ not to connect to $`m`$ given vertices. This probability is given by the formula :

$$\alpha _{t+1,m}\underset{n0}{}\tau _{t+1,n}\frac{\left(\genfrac{}{}{0pt}{}{tm}{n}\right)}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}$$

With $`\alpha _{t+1,m}(z)_{n0}\tau _{t+1,n}z^n\frac{\left(\genfrac{}{}{0pt}{}{tm}{n}\right)}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}`$, we notice that $`\alpha _{t+1,m+1}(z)=\alpha _{t+1,m}(z)\frac{z}{tm}\alpha _{t+1,m}^{}(z)`$. Since $`\alpha _{t+1,0}(z)=T_{t+1}(z)`$, we have :

$`\alpha _{t+1,m}(z)`$ $`=`$ $`T_{t+1}(z){\displaystyle \frac{\left(\genfrac{}{}{0pt}{}{m}{1}\right)z}{t}}T_{t+1}^{}(z)`$
$`+{\displaystyle \frac{\left(\genfrac{}{}{0pt}{}{m}{2}\right)z^2}{t(t1)}}T_{t+1}^{\prime \prime }(z)\mathrm{}()^m{\displaystyle \frac{\left(\genfrac{}{}{0pt}{}{m}{m}\right)z^m}{t\mathrm{}(tm+1)}}T_{t+1}^{(m)}(1)`$
$`\alpha _{t+1,m}`$ $`=`$ $`1{\displaystyle \frac{\left(\genfrac{}{}{0pt}{}{m}{1}\right)}{t}}T_{t+1}^{}(1)`$
$`+{\displaystyle \frac{\left(\genfrac{}{}{0pt}{}{m}{2}\right)}{t(t1)}}T_{t+1}^{\prime \prime }(1)\mathrm{}()^m{\displaystyle \frac{\left(\genfrac{}{}{0pt}{}{m}{m}\right)}{t(t1)\mathrm{}(tm+1)}}T_{t+1}^{(m)}(1)`$
In the thermodynamic limit, we shall only need the large $`t`$ finite $`m`$ approximation

$$\alpha _{t+1,m}1\frac{\alpha m}{t}.$$
(2)
These simple formulæ may now be used to calculate a few quantities. We’ll first describe the degree distributions of incoming and outgoing edges, whereas the two following sections will present the main relations governing the distributions of connected components of the graphs.

## 4 Degree distribution

### 4.1 Notations

Let

1. $`l_j^{}(t)`$ (resp. $`l_j^+(t)`$) be the number of incoming (resp. outgoing) edges at a vertex $`j`$ at time $`t`$
2. $`v_k^{}(t)`$ (resp. $`v_k^+(t)`$) be the number of vertices with $`k`$ incoming (resp. outgoing) edges at time $`t`$.

With these notations, the edge distributions are described by the generating functions :

$$\nu _t^\pm (z)\frac{1}{t}\underset{0k<t}{}v_k^\pm (t)z^k=\frac{1}{t}\underset{1jt}{}z^{l_j^\pm (t)}$$

In the thermodynamic limit, it is possible to give an expression for these generating functions.

### 4.2 In-degree distribution

Up to a normalisation factor, the probability for vertex $`j`$ to have $`k`$ incoming edges is $`\tau _{j,k}`$.This shows that

$$z^{l_j^{}(t)}=\underset{k0}{}\tau _{j,k}z^k$$

In the thermodynamic limit, this becomes

$$z^{l_j^{}(t)}=T(z)$$
(3)
Hence, in the thermodynamic limit, the probability for any vertex to have $`k`$ incoming edges is given by $`\frac{\tau _k}{k!}`$, which is correctly normalized.
This implies in particular that, in the thermodynamic limit, the average number of edges coming to a vertex is precisely $`\alpha `$.

### 4.3 Out-degree distribution

Any edge emerging from a vertex $`j`$ can be seen as an edge arriving at a vertex younger than $`j`$. Let $`t>j`$ be the time at which one observes the number of edges emerging from $`j`$. We define $`\sigma j/t`$. The quantity $`z^{l_{\sigma t}^+(t)}`$ is given by the formula :

$$\underset{k}{}z^k\underset{\sigma t<j_1<\mathrm{}<j_kt}{}\underset{1ik}{}\left(\underset{0k^{}j_i2}{}\tau _{j_i,k^{}+1}\frac{\left(\genfrac{}{}{0pt}{}{j_i2}{k^{}}\right)}{\left(\genfrac{}{}{0pt}{}{j_i1}{k^{}+1}\right)}\right)\underset{j<j^{}t;j^{}j_i}{}\left(\underset{0k^{}j^{}2}{}\tau _{j^{},k^{}}\frac{\left(\genfrac{}{}{0pt}{}{j^{}2}{k^{}}\right)}{\left(\genfrac{}{}{0pt}{}{j^{}1}{k^{}}\right)}\right)$$

Indeed, the probability for $`j`$ to have $`k`$ outgoing edges is obtained by summing over $`j_1,\mathrm{},j_k>j`$ the probabilities for $`j`$ to be linked to these $`k`$ vertices and to no other vertex. Each of this probabilities can easily be calculated from the following relations :

$`{\displaystyle \underset{0k^{}j_i2}{}}{\displaystyle \frac{\tau _{j_i,k^{}+1}}{\left(\genfrac{}{}{0pt}{}{j_i1}{k^{}+1}\right)}}\left({\displaystyle \genfrac{}{}{0pt}{}{j_i2}{k^{}}}\right)`$ $`=`$ $`{\displaystyle \frac{T_{j_i}^{}(1)}{j_i1}}`$
$`{\displaystyle \underset{0k^{}j^{}2}{}}{\displaystyle \frac{\tau _{j^{},k^{}}}{\left(\genfrac{}{}{0pt}{}{j^{}1}{k^{}}\right)}}\left({\displaystyle \genfrac{}{}{0pt}{}{j^{}2}{k^{}}}\right)`$ $`=`$ $`1{\displaystyle \frac{T_j^{}^{}(1)}{j^{}1}}`$
For fixed $`\sigma `$ and large $`t`$, the second product simplifies to $`\sigma ^\alpha `$ and the average we look for becomes :

$`z^{l_{\sigma t}^+(t)}`$ $``$ $`\sigma ^\alpha {\displaystyle \underset{k}{}}z^k{\displaystyle \underset{\sigma t<j_1<\mathrm{}<j_kt}{}}{\displaystyle \frac{\alpha ^k}{j_1\mathrm{}j_k}}`$
$``$ $`\sigma ^\alpha {\displaystyle \underset{k}{}}z^k{\displaystyle \frac{1}{k!}}\left[\mathrm{ln}t\mathrm{ln}\sigma t\right]^k\alpha ^k`$
Hence, for fixed $`\sigma `$,

$$z^{l_{\sigma t}^+(t)}e^{(z1)\alpha \mathrm{ln}\sigma }$$
(4)
for large $`t`$, so the local out-degree distribution is Poissonian with $`\sigma `$-dependent parameter $`\alpha \mathrm{ln}\sigma `$. Integrating $`\sigma `$ between $`0`$ and $`1`$ yields the asymptotic value for the generating function $`\nu _t^+(z)`$ :

$$\nu _t^+(z)\frac{1}{1+\alpha (1z)}$$
(5)
at large $`t`$.

Identifying the term of degree $`k`$ in $`z`$ in the development of this function finally yields the probability for a vertex to have $`k`$ outgoing edges :

$$p^+(k)=\frac{\alpha ^k}{\left(1+\alpha \right)^{k+1}}$$

We see that the distribution of outgoing edges is geometric and depends on the probability distribution $`T`$ only through the average number of incoming edges $`\alpha `$.

### 4.4 Mixed distribution

In our model, the number of in and out edges $`l_j^+(t)`$ and $`l_j^{}(t)`$ at a given vertex are independent by construction. The generating function for the mixed degree distribution is

$$\nu _t(z_+,z_{})\frac{1}{t}\underset{k_+,k_{}}{}v_{k_+,k_{}}(t)z_+^{k_+}z_{}^k_{}=\frac{1}{t}\underset{1jt}{}z_+^{l_j^+(t)}z_{}^{l_j^{}(t)}$$

which is easily obtained from eqs.(3,5) :

$$\nu (z_+,z_{})=\frac{T(z_{})}{1+\alpha (1z_+)}.$$
(6)
The local counterpart would easily follow from eqs.(3,4).

## 5 Connected components

In this section we give formulæ for the number of components of size $`k`$ in the thermodynamic limit (paragraph 5.1), and for the time distribution of these components (paragraph 5.3). This derivation makes some natural assumptions of self averaging. In paragraph 5.4, we evaluate without such assumptions the contribution of individual graphs to the weights of random graphs, and show that trees dominate the thermodynamic limit. We use this result in the appendix to compute directly the generating function for the number of components of size $`k`$, and show that it coincides with the one given in paragraph (5.1).

### 5.1 Global-time results

Let $`N_k(t)`$ be the number of connected components of size $`k`$ at time $`t`$ for a given graph, and $`N_t(z)`$ the corresponding generating function :

$$N_t(z)\underset{k1}{}N_k(t)z^k$$

To evaluate this function, we shall investigate its evolution between times $`t`$ and $`t+1`$. When, at time $`t+1`$, the new vertex is added and randomly connected to some of the older vertices, the components to which these vertices belonged are destructed and collapsed into a new, bigger, component. More precisely, let us put $`n_k(t)`$ for the number of components of size $`k`$ connected to vertex $`t+1`$ when it is added to the graph. For all $`k`$, $`n_k(t)`$ components of size $`k`$ are thus destroyed between times $`t`$ and $`t+1`$, while a component of size $`1+_kkn_k(t)`$ is created. To summarize this :

$$N_{t+1}(z)N_t(z)=\underset{k}{}n_k(t)z^k+z^{1+_kkn_k(t)}$$
(7)
Now, the point is to average this equality over all graphs of size $`k`$ and all possible connections of vertex $`t+1`$ with these graphs.

First of all, we shall propose a compact expression for $`z^{n_k(t)}`$ valid for all $`t`$. We will deduce from it an expression of $`n_k(t)`$ before calculating the average of $`z^{1+_kkn_k(t)}`$. Finally we will give an evolution equation valid in the thermodynamic limit.

#### Exact derivation of $`z^{n_k(t)}`$

This average is given by

$$\underset{G_t}{}\underset{j0}{}z^jw_{t+1}(k,j),$$

where $`w_{t+1}(k,j)`$ is the total weight of graphs of size $`t+1`$ obtained from a graph $`G_t`$ of size $`t`$ in such a way that, when it was added, vertex $`t+1`$ connected to $`j`$ components of size $`k`$. Hence, $`w_{t+1}(k,j)`$ is the term of degree $`0`$ in $`\omega `$ of the Laurent serie :

$$w_{G_t}\underset{n0}{}\frac{\tau _{t+1,n}}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\omega ^n\left(\genfrac{}{}{0pt}{}{N_k(t)}{j}\right)\left(\underset{i=1}{\overset{k}{}}\omega ^i\left(\genfrac{}{}{0pt}{}{k}{i}\right)\right)^j\underset{p0}{}\omega ^p\left(\genfrac{}{}{0pt}{}{tkN_k(t)}{p}\right)$$

In this expression,

* $`n`$ is the number of edges connecting vertex $`t+1`$ to $`G_t`$ ;
* $`i`$ is the number of edges connecting vertex $`t+1`$ to a given component of size $`k`$ ;
* $`p`$ is the number of edges connecting vertex $`t+1`$ to vertices of $`G_t`$ which don’t belong to a component of size $`k`$.

The sums over $`i`$, $`j`$ and $`p`$ simplify, so that $`z^{n_k(t)}`$ is the term of degree $`0`$ in $`\omega `$ of

$$\underset{G_t,n0}{}w_{G_t}\frac{\tau _{t+1,n}}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\omega ^n\left(z(1+\omega )^k+1z\right)^{N_k(t)}(1+\omega )^{tkN_k(t)}$$

If we rewrite the sum over the $`G_t`$’s as an average over graphs of size $`t`$ and expand the two parenthesis, we get

$$z^{n_k(t)}=\underset{n,m0}{}\frac{\tau _{t+1,n}}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\left(\genfrac{}{}{0pt}{}{N_k(t)}{m}\right)\left(1z\right)^mz^{N_k(t)m}\left(\genfrac{}{}{0pt}{}{tkm}{n}\right)$$

In this formula, we recognize $`\alpha _{t+1,m}_{n0}\frac{\tau _{t+1,n}}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\left(\genfrac{}{}{0pt}{}{tm}{n}\right)`$, which is the probability that vertex $`t+1`$ doesn’t connect to $`m`$ given vertices. The average we need becomes :

$$z^{n_k(t)}=\underset{m0}{}\alpha _{km}\left(\genfrac{}{}{0pt}{}{N_k(t)}{m}\right)z^{N_k(t)m}\left(1z\right)^m$$
(8)
This formula gives in particular the average number of components of size $`k`$ connected to the new vertex :

$$n_k(t)=N_k(t)\left(1\alpha _{t+1,k}\right)$$
(9)
#### Exact derivation of $`z^{_kn_k(t)}`$

The only difference with the computation we’ve just described is that the sum over $`j`$ is replaced by sums over all possible $`j_k`$’s, while $`z^j`$ becomes $`z^{_kkj_k}`$. Omitting the details, we just give the result, which has the same form as formula (8) :

$$z^{_kkn_k}=\underset{\{m\}}{}\alpha _{t+1,_kkm_k}\underset{k}{}\left(\left(\genfrac{}{}{0pt}{}{N_k(t)}{m_k}\right)z^{k\left(N_k(t)m_k\right)}\left(1z^k\right)^{m_k}\right)$$

In this equation, the sum is performed over all sequences $`m_1,m_2,\mathrm{}`$.
This expression can be simplified if we note that $`\alpha _{t+1,m}`$ is a weighted sum of Newton coefficients, so that

$$\alpha _{t+1,m}=\underset{n0}{}\frac{dx}{x^{n+1}}\frac{\tau _{t+1,n}}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\left(1+x\right)^{tm},$$

where the symbol $``$ denotes the contour integral $`\frac{1}{2i\pi }`$ along a small contour surrounding the origin.
Evaluating the sum over the $`m_k`$’s now yields

$$z^{_kkn_k}=\underset{n}{}\frac{\tau _{t+1,n}}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\frac{dx}{x^{n+1}}\underset{k}{}\left(z^k\left(1+x\right)^k+1z^k\right)^{N_k(t)}$$
(10)
#### Evolution equation for connected components

Formula (7) can now be written in a simpler form using equalities (9) and (10). With $`T_t(1)=1`$, this leads to :

$`N_{t+1}(z)N_t(z)`$ $`=`$ $`{\displaystyle \underset{k}{}}N_k(t)\left(\alpha _{t+1,k}1\right)z^k`$
$`+`$ $`z{\displaystyle \underset{n}{}}{\displaystyle \frac{\tau _{t+1,n}}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}}{\displaystyle \frac{dx}{x^{n+1}}\underset{k}{}\left(z^k\left(1+x\right)^k+1z^k\right)^{N_k(t)}}`$
This equation is exact for finite $`t`$. To get the equation governing the large $`t`$ behavior, we make a thermodynamic assumption : because $`T_t(z)`$ converges to $`T(z)`$ in such a way that the averages and variances converge as well, we expect that $`N_k(t+1)N_k(t)`$ converges to some deterministic quantity $`C_k`$, so that $`N_k(t+1)N_k(t)C_k`$ may fluctuate but is $`o(1)`$ at large $`t`$. Then, by Cesaro convergence, the same is true of $`N_k(t)/tC_k`$.

Then the left-hand side of eq.(5.1) is $`_kC_kz^k`$. Using $`\alpha _{t+1,k}1\frac{\alpha k}{t}`$ for large $`t`$, the first sum on the right-hand side is $`\alpha _kkC_kz^k`$. In the second sum, we replace $`x`$ by $`x/t`$, leading to

$$\underset{n}{}\frac{\tau _{t+1,n}t^n}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\frac{dx}{x^{n+1}}\underset{k}{}\left(z^k\left(1+x/t\right)^k+1z^k\right)^{N_k}.$$

For large $`t`$, $`\frac{\tau _{t+1,n}t^n}{\left(\genfrac{}{}{0pt}{}{t}{n}\right)}\tau _n`$ and $`\left(z^k\left(1+x/t\right)^k+1z^k\right)^{N_k(t)}\left(1+xkz^k/t\right)^{N_k(t)}e^{xkz^kN_k(t)/t}`$. The averages are now trivial to take. The second sum is seen to be

$$\underset{n}{}\tau _n\frac{dx}{x^{n+1}}e^{x_kkz^kC_k}.$$

Putting this together, we get

$$\underset{k}{}C_kz^k=\alpha \underset{k}{}kC_kz^k+z\underset{n}{}\tau _n\frac{dx}{x^{n+1}}e^{x_kkz^kC_k}.$$

Defining $`C(z)_kC_kz^k`$ and evaluating the contour integral, we obtain the compact formula

$$C(z)=z\alpha _zC(z)+zT\left(z_zC(z)\right)$$
(12)
which describes the number of components of size $`k`$ at large $`t`$.

This equation has a simple interpretation in terms of destruction and creation of components. Indeed, $`C(z)=N_{t+1}(z)N_t(z)`$ gives for each $`k`$ the variation of $`N_k`$ between $`t`$ and $`t+1`$. This variation is the sum of two terms :

* $`z\alpha _zC(z)`$ gives the product of the average number, $`\alpha `$, of incoming edges in a given vertex by the mean proportion of vertices in components of size $`k`$ ($`kC_k`$). Stating that in the thermodynamic limit, two edges arriving at a vertex have vanishing probability of coming from the same finite component, this term can be seen as the average number of destroyed components.
* $`zT\left(z_zC(z)\right)`$ involves a sum of terms of the form $`\frac{\tau _nz^{1+k_1+\mathrm{}+k_n}}{n!}k_1C_{k_1}\mathrm{}k_nC_{k_n}`$. It counts the average size of the component created when a new vertex is added.

Equation (12) allows a recursive calculation of the $`C_k`$’s. Unfortunately, we were not able to find an explicit formula valid for all $`k`$ and we only give here the values of the first few of them :

$`C_1`$ $`=`$ $`{\displaystyle \frac{\tau _0}{1+\alpha }}`$
$`C_2`$ $`=`$ $`{\displaystyle \frac{\tau _0\tau _1}{(1+\alpha )(1+2\alpha )}}`$
$`C_3`$ $`=`$ $`{\displaystyle \frac{4\tau _0\tau _1^2(\alpha +1)+\tau _0^2\tau _2(2\alpha +1)}{2(\alpha +1)^2(2\alpha +1)(3\alpha +1)}}`$
### 5.2 A simple example

The case when $`T(z)=(1p)+pz`$ leads to tractable equations even at finite $`t`$. As we shall see later, this example is pathological from the point of view of the percolation transition. This is another reason to give a separate treatment.

Though it is likely that this toy model has been solved more than once before, we have found no reference. So we give a sketch of the solution with apologies to the original contributions. In particular, we compute the scaling function governing the statistics of large components.

When vertex $`t+1`$ is added, it remains isolated with probability $`1p`$ in which case $`N_k(t+1)N_k(t)=\delta _{k,1}`$, or is attached to a component of size $`l`$ to build a component of size $`l+1`$ with probability $`plN_l(t)/t`$, in which case $`N_k(t+1)N_k(t)=\delta _{k,l+1}\delta _{k,l}`$. We infer

$`N_{t+1}(z)N_t(z)`$ $`=`$ $`(1p)z+{\displaystyle \underset{k,l}{}}plN_l(t)/t(\delta _{k,l+1}\delta _{k,l})z^k`$
$`=`$ $`(1p)z+p{\displaystyle \underset{l}{}}lN_l(t)/t(z^{l+1}z^l)`$
$`=`$ $`(1p)z+p/t(z^2z)_zN_t(z).`$
The initial condition is $`N_1(z)=N_1(z)=z`$ We can simplify this equation by the change of variable $`z=w/(1+w)`$. Setting $`Q_t(w)N_t(z)`$, the equation for $`Q_t`$ is

$$Q_{t+1}Q_t=(1p)\frac{w}{1+w}p\frac{w}{t}_wQ_t.$$

$`N_t(z)`$ is a polynomial in $`z`$, so $`Q_{t+1}`$ has a regular series expansion in $`w`$, $`Q_t_{k1}q_k(t)w^k`$ which leads to $`q_k(t+1)=\frac{tpk}{t}q_k(t)+(1p)(1)^{k+1}`$. Direct substitution shows that $`q_k(t)=t\frac{1p}{1+pk}(1)^{k+1}`$ is a particular solution. The general solution $`r_k(t)`$ of the associated homogeneous equation $`r_k(t+1)=\frac{tpk}{t}r_k(t)`$ is $`r_k(t)=\frac{\mathrm{\Gamma }(tpk)}{\mathrm{\Gamma }(t)\mathrm{\Gamma }(1pk)}r_k(1)`$. Taking into account the initial condition $`Q_1=w/(1+w)`$ leads to

$$q_k(t)=(1)^{k+1}\left(t\frac{1p}{1+pk}+\frac{p(k+1)}{1+pk}\frac{\mathrm{\Gamma }(tpk)}{\mathrm{\Gamma }(t)\mathrm{\Gamma }(1pk)}\right).$$

We can now go back to the $`z`$ variable :

$$N_k(t)=\underset{l=1}{\overset{k}{}}(1)^{l+1}\left(t\frac{1p}{1+pl}+\frac{p(l+1)}{1+pl}\frac{\mathrm{\Gamma }(tpl)}{\mathrm{\Gamma }(t)\mathrm{\Gamma }(1pl)}\right)\frac{\mathrm{\Gamma }(k)}{\mathrm{\Gamma }(l)(kl)!}.$$

The contribution corresponding to the first term inside the parenthesis, the one which is linear in $`t`$, can be resummed. Indeed, if $`C(z)`$ is a solution of $`C=(1p)z+p(z^2z)_zC`$, $`tC(z)`$ solves the original equation for $`N_t(z)`$ even at finite $`t`$. The solution which is regular at $`z=0`$ is

$$C(z)=\underset{k1}{}\frac{1p}{p}\frac{\mathrm{\Gamma }(k)\mathrm{\Gamma }(1+1/p)}{\mathrm{\Gamma }(k+1+1/p)}z^k.$$

One can check that, for any $`p[0,1[`$, $`C^{}(z=1)=1`$. As we shall explain later, that means there is no percolation.

To summarize,

$$N_k(t)=t\frac{1p}{p}\frac{\mathrm{\Gamma }(k)\mathrm{\Gamma }(1+1/p)}{\mathrm{\Gamma }(k+1+1/p)}+\underset{l=1}{\overset{k}{}}(1)^{l+1}\frac{p(l+1)}{1+pl}\frac{\mathrm{\Gamma }(tpl)}{\mathrm{\Gamma }(t)\mathrm{\Gamma }(1pl)}\frac{\mathrm{\Gamma }(k)}{\mathrm{\Gamma }(l)(kl)!}.$$

It is now possible to get the exact scaling function governing the size distribution of large components. When both $`t`$ and $`k`$ are large, the thermodynamic contribution scales like $`\frac{1p}{p}\mathrm{\Gamma }(1+1/p)tk^{11/p}`$ while in the other contribution, for fixed $`l`$, one finds $`(1)^{l+1}\frac{p(l+1)}{1+pl}\frac{1}{\mathrm{\Gamma }(1pl)\mathrm{\Gamma }(l)}t^{pl}k^{l1}`$. This decreases very fast with $`l`$ so for large $`k`$ one can extend the range of $`l`$ to $`\mathrm{}`$. The balance between the thermodynamic and finite size contributions shows that the scaling variable is $`s=kt^p`$. In the scaling limit

$$kN_k(t)\frac{1p}{p}\mathrm{\Gamma }(1+1/p)s^{1/p}+\underset{l1}{}(1)^{l+1}\frac{p(l+1)}{1+pl}\frac{1}{\mathrm{\Gamma }(1pl)\mathrm{\Gamma }(l)}s^l.$$

Let $`S(s)`$ denote the scaling function on the right hand side.

Defining $`sA(s)_{l1}(1)^{l+1}\frac{1}{\mathrm{\Gamma }(1pl)\mathrm{\Gamma }(l)}s^l`$, one can rewrite

$$S(s)/s=\frac{1p}{p}\mathrm{\Gamma }(1+1/p)s^{11/p}+A(s)\frac{1p}{p}_0^1𝑑\lambda A(\lambda s)\lambda ^{1/p}.$$

This expression of $`S`$ exhibits clearly its small $`s`$ behavior. To get control on the large $`s`$ behavior, one can use the familiar representation $`\frac{1}{\mathrm{\Gamma }(z)}=\frac{1}{2i\pi }_𝒞𝑑we^ww^z`$ for $`z=1pl`$ and sum over $`l`$ to obtain

$$A(s)=\frac{1}{2i\pi }_𝒞𝑑we^{wsw^p}w^{p1}.$$

Observing that $`\mathrm{\Gamma }(1+1/p)s^{11/p}=_0^{\mathrm{}}𝑑\lambda A(\lambda s)\lambda ^{1/p}`$, one gets a compact expression

$$S(s)/s=A(s)+\frac{1p}{p}_1^{\mathrm{}}𝑑\lambda A(\lambda s)\lambda ^{1/p}.$$

The large $`s`$ expansion can then be obtained by standard methods (saddle point for A(s) and then analysis at $`\lambda =1`$ for the second term). The formulæ are rather cumbersome and we simply quote the leading exponential behavior

$$\mathrm{log}S(s)\frac{1p}{p}p^{\frac{1}{1p}}s^{\frac{1}{1p}}s+\mathrm{},$$

showing that $`S(s)`$ decreases very fast at large $`s`$.

As a simple example, take $`p=1/2`$. Then $`A(s)=\frac{1}{\sqrt{\pi }}e^{s^2/4}`$ and

$$S(s)=\frac{1}{\sqrt{\pi }}\left(se^{s^2/4}+\frac{1}{s^2}_s^{\mathrm{}}𝑑\lambda \lambda ^2e^{\lambda ^2/4}\right).$$

Returning to arbitrary $`p`$, the relation $`kN_k(t)S(k/t^p)`$ implies that the average number of components of size $`kst^p`$ is $`_{kst^p}N_k(t)_s^{\mathrm{}}𝑑uS(u)/u<\mathrm{}`$. So the large components have a size of order $`t^p`$.

### 5.3 Local-in-time results

Knowing the global-in-time distribution of connected components, it is natural to wonder whether this distribution is homogeneous in time or not. More precisely, if $`j=\sigma t`$ with fixed $`\sigma `$ and $`t\mathrm{}`$, what can we say about the probability for vertex $`j`$ to be in a component of size k ?
For $`k1`$ let $`\rho _k(\sigma )`$ be the probability that, in the thermodynamic limit, vertex $`\sigma t`$ belongs to a connected component of size $`k`$. The purpose of this section is to give an equation governing the $`\rho _k`$’s.

#### Local-in-time equation

The systematic to derive this equation relies on the same ideas as those used in paragraph 5.1 to get the global formula, and involves heavy formulæ. Consequently we use directly the thermodynamic assumption and give a more intuitive argument.
Let $`\mathrm{\Delta }t`$ be an interval of time such that $`\mathrm{\Delta }t1`$ but $`\frac{\mathrm{\Delta }t}{t}1`$. Between times $`t`$ and $`t+\mathrm{\Delta }t`$, the number of vertices added to the graph is large but much smaller than the size of the graph.
Following the interpretation of eq. (12), the number of new components of size $`k`$ is

$$\mathrm{\Delta }t\underset{m}{}\frac{\tau _m}{m!}\underset{k_1,\mathrm{},k_m}{}k_1C_{k_1}\mathrm{}k_mC_{k_m}\delta _{1+_ik_i,k}$$

Each of the $`m`$ old components has average time distribution $`\frac{\rho _{k_i}(\sigma )}{C_{k_i}}`$ so that, on average, the contribution of the $`\mathrm{\Delta }t`$ new components to the time distribution of components on $`k`$ vertices is

$$\mathrm{\Delta }t\underset{m}{}\frac{\tau _m}{m!}\underset{k_1,\mathrm{},k_m}{}k_1C_{k_1}\mathrm{}k_mC_{k_m}\left(\frac{\rho _{k_1}(\sigma )d\sigma }{C_{k_1}}+\mathrm{}+\frac{\rho _{k_m}(\sigma )d\sigma }{C_{k_m}}\right)\delta _{1+_ik_i,k}$$

Let us put $`\rho (\sigma ,z)_k\rho _k(\sigma )z^k`$. Multiplying the expression above by $`z^k`$ and summing over $`k`$ yields the term $`\mathrm{\Delta }tz^2_z\rho (\sigma ,z)T^{}(z_zC)d\sigma `$.

Following again the interpretation of eq. (12), $`\alpha \mathrm{\Delta }tkC_k`$ components of size $`k`$ are destructed between $`t`$ and $`t+\mathrm{\Delta }t`$. According to the definition of $`\rho _k(\sigma )`$, the number of vertices of relative age contained between $`\sigma `$ and $`\sigma +d\sigma `$, which belonged to one of these components is $`\alpha \mathrm{\Delta }tk\rho _k(\sigma )`$.

After summation over $`k`$, the destruction term is $`\alpha \mathrm{\Delta }tz_z\rho (\sigma ,z)d\sigma `$.
Moreover, a vertex of relative age $`\sigma `$ at time $`t`$ has relative age $`\frac{\sigma t}{t+\mathrm{\Delta }t}`$ at time $`t+\mathrm{\Delta }t`$. Hence, the local-in-time profile verifies, to first order in $`\mathrm{\Delta }t/t`$, the following relation

$$td\sigma \left(\rho (\frac{\sigma t}{t+\mathrm{\Delta }t},z)\rho (\sigma ,z)\right)=\alpha \mathrm{\Delta }tz_z\rho (\sigma ,z)d\sigma +\mathrm{\Delta }tz^2_z\rho (\sigma ,z)T^{}(z_zC)d\sigma .$$

This leads to the differential equation

$$\sigma _\sigma \rho =\left(\alpha zT^{}\left(z_zC\right)\right)z_z\rho $$
(13)
As in the case of a Poisson law, this equation leads to recursion relations for the $`\rho _k(\sigma )`$’s. Differentiating eq. (13) $`k`$ times with respect to $`z`$ and taking $`z=0`$ leads to a first order linear differential equation for $`\rho _k`$, in which $`\rho _1,\mathrm{},\rho _{k1}`$ appear. Putting $`x=\sigma ^\alpha `$, the first few distributions are :

$`\rho _1`$ $`=`$ $`\tau _0x`$
$`\rho _2`$ $`=`$ $`{\displaystyle \frac{\tau _0\tau _1}{\alpha }}\left[x{\displaystyle \frac{x^2}{1+\alpha }}\right]`$
$`\rho _3`$ $`=`$ $`x\left[{\displaystyle \frac{\tau _0^2\tau _2}{2\alpha (1+\alpha )}}+{\displaystyle \frac{\tau _1^2\tau _0}{\alpha ^2}}\right]`$
$`x^2{\displaystyle \frac{2\tau _0\tau _1^2}{\alpha ^2(1+\alpha )}}`$
$`+x^3\left[{\displaystyle \frac{\tau _0\tau _1^2}{\alpha ^2(1+2\alpha )}}{\displaystyle \frac{\tau _0^2\tau _2}{2\alpha (1+\alpha )^2}}\right]`$
#### Component distribution at $`\sigma =1`$

To conclude this paragraph, we shall compute the probability for the oldest vertex to belong to a component of size $`k`$. This is not difficult to do because, unlike all the other vertices in the graph, the youngest one does not have any outgoing edge. Hence, following once again the interpretation of eq. (12), it belongs to a component of size $`k`$ with probability $`_m\frac{\tau _m}{m!}_{k_1,\mathrm{},k_m}k_1C_{k_1}\mathrm{}k_mC_{k_m}\delta _{1+_ik_i,k}`$. More compactly :

$$\rho (\sigma =1,z)=zT(z_zC).$$
(14)
Note that eqs.(13,14) can be used to recover the global equation (12).

### 5.4 Tree distributions

Given a connected graph $`G`$, one may wonder how many connected components of the random evolving graph are isomorphic to $`G`$. In other words, if $`k`$ is the number of vertices of $`G`$, we look for the average number of increasing maps $`v:[1,\mathrm{},k][1,\mathrm{},t]`$ such that the vertices $`v_1,\mathrm{},v_k`$ span a connected component of the random graph isomorphic to $`G`$.
Let $`m_i`$ be the number of edges incoming to vertex $`i`$ in $`G`$. The probability that vertices $`v_1,\mathrm{},v_k`$ span a connected component of the random graph isomorphic to $`G`$ is evaluated using the following two rules :

* Vertex $`v_i`$ has $`m_i`$ incoming edges coming from the given vertices ;
* The vertices $`w`$ of the random graph which are not in the image of $`v`$ must not be connected to any of the $`v_i`$’s.

Hence, putting $`v_{k+1}=t+1`$, the probability we look for is

$$\underset{i=1}{\overset{k}{}}\left[\frac{\tau _{v_i,m_i}}{\left(\genfrac{}{}{0pt}{}{v_i1}{m_i}\right)}\underset{v_i<w_i<v_{i+1}}{}\underset{j0}{}\frac{\tau _{w_i,j}}{\left(\genfrac{}{}{0pt}{}{w_i1}{j}\right)}\left(\genfrac{}{}{0pt}{}{w_ii1}{j}\right)\right]$$

The average number of components is then obtained by summing this expression over all increasing maps $`v`$

$$n_G=\underset{1v_1<\mathrm{}<v_kt}{}\underset{i=1}{\overset{k}{}}\left[\frac{\tau _{v_i,m_i}}{\left(\genfrac{}{}{0pt}{}{v_i1}{m_i}\right)}\underset{v_i<w_i<v_{i+1}}{}\underset{j0}{}\frac{\tau _{w_i,j}}{\left(\genfrac{}{}{0pt}{}{w_i1}{j}\right)}\left(\genfrac{}{}{0pt}{}{w_ii1}{j}\right)\right]$$

In the thermodynamic limit, the sum over $`j`$ is given by formula (2), and its product over $`w_i`$ tends to $`e^{i\alpha \mathrm{ln}\frac{v_{i+1}}{v_i}}`$ provided only large $`w_i`$’s contribute significantly. Hence, approximating the sum over $`v_1,\mathrm{},v_k`$ by an integral yields a contribution of $`G`$ equal to

$$C_{m_1,\mathrm{},m_k}=t^{km}\left(\underset{i=1}{\overset{k}{}}\tau _{m_i}\right)_{0\sigma _1\mathrm{}\sigma _k1}𝑑\sigma _1\sigma _1^{\alpha m_1}\mathrm{}𝑑\sigma _k\sigma _k^{\alpha m_k}$$
(15)
This formula looks pretty much like the one proposed in the poissonnian case in . In particular, it shows exactly in the same way that only connected graphs with $`k=m+1`$ (i.e. trees by Euler’s formula) give a contribution that scales like $`t`$ in the thermodynamic limit. Moreover, the contribution of a tree with degree distribution $`m_i`$ is

$$\underset{i=1}{\overset{k}{}}\frac{\tau _{m_i}}{i(\alpha +1)(m_1+\mathrm{}+m_i)}$$
(16)
This formula was obtained by integration over all relative ages $`\sigma _0,\mathrm{},\sigma _{k1}`$. However, if we only integrate over some of these variables while fixing the others, say $`\sigma _{k_1}<\sigma _{k_2}<\mathrm{}<\sigma _{k_p}`$, we expect to get the contribution of a given tree with $`k`$ vertices amongst which $`p`$ vertices have imposed age. For instance, taking $`k=2`$ and integrating over $`\sigma _1`$ while imposing $`\sigma _2=\sigma `$ gives the contribution of trees of size 2 with younger vertex of age $`\sigma `$. Explicit integration yields a contribution $`\tau _0\tau _1\sigma ^{2\alpha }/(\alpha +1)`$ . On the other hand, if we integrate over $`\sigma _2`$ and fix $`\sigma _1=\sigma `$, we get $`\tau _0\tau _1(\sigma ^\alpha /\alpha \sigma ^{2\alpha }/\alpha )`$ for the contribution of trees of size 2 with older vertex of age $`\sigma `$. The sum of these two quantities, which is expected to be the probability that a site of relative age $`\sigma `$ belongs to a tree with two vertices is, indeed, equal to $`\rho _2(\sigma )`$ as calculated from equation (13).
In fact, this result is not really surprising, since the derivation of eq.(12) relies on the fact that, in the thermodynamic limit, a new vertex connects with vanishing probability to several vertices in the same component. In other words, this equation of evolution takes only trees into account so eq.(16) should imply it. The full proof is instructive but tedious, and we relegate it to the appendix.

## 6 The percolation transition

Formula (12) gives a relation between the $`C_k`$’s, which represent the asymptotic number of connected components of size $`k`$. This equation involves in particular the function $`z_zC(z)=_kkC_kz^k`$.
Note that $`kC_k`$ is the fraction of sites belonging to components of size $`k`$. This means that, if $`_kkC_k=1`$, no single component in the graph can have size $`O(t)`$. On the other hand, if $`_kkC_k<1`$, the possibility exists that a giant component contains a finite fraction of the sites. The possibility that several very large components coexist is usually ruled out because under a rearrangment of a number $`o(t)`$ of edges these components would merge with finite probability. Though we have not tried to build a formal argument in the case of evolving graphs, the intuition remains the same and is confirmed by numerical simulations. So we take for granted that if $`_kkC_k<1`$ a single giant component contains a fraction $`1_kkC_k`$ of the sites.

### 6.1 Main results.

The arguments that lead to the main qualitative and quantitative features of the percolation transition are of technical nature. So we postpone them to the next section.

#### Percolation criterion.

Unless $`T(z)`$ is a polynomial of degree 1, the system contains a giant component if either the variance $`\gamma `$ of $`T`$ is $`>1/4`$ or the average $`\alpha `$ of $`T`$ is $`>1/2`$. The boundary separating the non percolating phase from the percolating phase is given by the two conditions $`\gamma =1/4`$ and $`\alpha <1/2`$. The emergence of a giant componant is purely due to an increase of the variance of $`T`$ above the threshold $`1/4`$.

#### Behaviour below threshold.

If $`\gamma 1/4`$ and $`\alpha 1/2`$, the distribution of component sizes in the system is critical, caracterized by the following three equivalent properties.

The dominant singularity of $`C(z)`$ at $`z=1`$ is

$$C^{sing}(z)(1z)^{\frac{2}{1\sqrt{14\gamma }}}.$$
(17)
For large $`k`$, the fraction of sites belonging to components of size $`k`$ decreases like

$$kC_kk^{\frac{2}{1\sqrt{14\gamma }}}.$$
(18)
For a finite system of size $`t\mathrm{}`$, the large components have a size of order

$$k(t)t^{\frac{1\sqrt{14\gamma }}{2}}.$$
(19)
#### Behaviour above but close to threshold.

The percolation transition is of infinite order when $`\gamma `$ crosses the value $`1/4`$ while keeping $`\alpha <1/2`$. If we denote by $`P_{\mathrm{}}`$ the fraction of sites occupied by the giant component, then when $`\gamma 1/40^+`$, $`P_{\mathrm{}}`$ is exponentially small :

$$\mathrm{log}P_{\mathrm{}}\pi /\sqrt{4\gamma 1}\text{for }\gamma 1/4^+.$$
(20)
For large $`k`$, the fraction of sites belonging to components of size $`k`$ decreases like

$$kC_kk^{\frac{3}{2}}e^{kP_{\mathrm{}}}.$$
(21)
### 6.2 Discussion.

We start our discussion by analysing the behavior of $`C(z)`$ close to $`z=1`$. As before, we assume that $`T(z)`$ is not a polynomial of degree $`1`$, i.e. that $`T^{\prime \prime }(1)0`$.

We start from equation (12) and apply the operator $`z_z`$ to get

$$(z_zC)+\alpha z_z(z_zC)=zT(z_zC)+zT^{}(z_zC)z_z(z_zC)$$
(22)
which involves only $`z_zC`$.

Set $`z=e^\tau `$ and $`Y(\tau )1z_zC`$ . Equation (22) can be rewritten for $`Y`$ :

$$0=Y(\tau )1+\alpha \dot{Y}(\tau )+e^\tau \left(T(1Y(\tau ))T^{}(1Y(\tau ))\dot{Y}(\tau )\right).$$

We know make two assumptions.

i) there is no giant component : $`_kkC_k=1`$ or equivalently $`Y(0)=0`$,

ii) the size distribution of clusters has a first moment : $`\mu _1=_kk^2C_k`$ is finite.
Note that ii) implies that $`\dot{Y}(0^{})`$ exists and has value $`\mu _1`$.

We differentiate the equation for $`Y`$ with respect to $`\tau `$ and put $`\tau =0`$, yielding :

$$\mu _1^2T^{\prime \prime }(1)+\mu _1(2\alpha 1)+1=0.$$

The discriminant of this equation for $`\mu _1`$ is $`14\gamma `$ where $`\gamma =T^{\prime \prime }(1)+\alpha \alpha ^2`$ is the variance of the distribution $`T`$.
The case when $`T^{\prime \prime }(1)=0`$, i.e. when $`T(z)`$ is affine, has some pathologies, but it has already been treated in detail.

If $`T^{\prime \prime }(1)>0`$, the quadratic equation has two roots,

a) both real and positive if $`12\alpha `$ and $`14\gamma `$ are positive,

b) both real and negative if $`12\alpha `$ is negative but $`14\gamma `$ is positive,

c) both complex if $`14\gamma `$ is negative.
Clearly, only case a) is compatible with our two assumptions i) and ii). In the sequel we shall take for granted that in this case, the assumptions i) and ii) are indeed true.

In cases b) and c), at least one of the assumptions must fail. We show that it is i), the absence of giant component. To do that we need a more precise analysis.

Let us first give some properties of $`Y(\tau )`$ for $`\tau 0`$. By construction, $`Y(\tau )`$ has a convergent expansion in powers of $`e^\tau `$ with negative coefficients (except the first) and is bounded by $`0`$. So $`Y`$ is continuous decreasing on $`]\mathrm{},0]`$.

To obtain the large order behavior of $`C_k`$ we simplify eq.(22) assuming that $`\tau `$ and $`Y(\tau )`$ are small222Note that we do not assume that they are of the same order of magnitude.. This is certainly a good approximation to describe the small $`\tau `$ behavior of $`Y(\tau )`$ when there is no percolation cluster because in that case $`Y(\tau )`$ is continuous and vanishes at $`\tau =0`$. It is also true close to a continuous phase transition because $`Y(0)`$ is small.

Keeping only the dominant contributions yields

$$\dot{Y}\left(T^{\prime \prime }(1)Y\alpha \tau \right)+(1\alpha )Y+\tau 0.$$

Setting $`\gamma F=T^{\prime \prime }(1)Y\alpha \tau `$, we derive the limit equation

$$\gamma F\dot{F}+F+\tau =0.$$
(23)
This equation is the same as the one found and studied in . As the presentation in  is closer in spirit to this one, this is the one we refer to in the sequel for details. In the poissonian case, the authors showed carefully that eq.(23) indeed contains the quantitative universal features of the exact cluster generating function. We take for granted that this remains true for general $`T`$.

When $`\gamma <1/4`$, we write $`\beta =\sqrt{14\gamma }`$. The general integral of eq.(23) is

$$\left(1+\frac{1\beta }{2}\frac{F}{\tau }\right)^{\frac{1+\beta }{2\beta }}\left(1+\frac{1+\beta }{2}\frac{F}{\tau }\right)^{\frac{\beta 1}{2\beta }}=\frac{\mathrm{C}^{st}}{\tau }.$$
(24)
Suppose $`F(0)=0`$, but $`F(\tau )/\tau `$ is not bounded close to $`\tau =0^{}`$. Then at a point where $`F(\tau )/\tau `$ is large, eq.(24) implies that $`F(\tau )`$ is of order one, a contradiction. For analogous reasons, if $`F(0)=0`$ and $`F(\tau )/\tau `$ is bounded, $`lim_{\tau 0^{}}1+\frac{1+\beta }{2}\frac{F}{\tau }=0`$ and then

$$F(\tau )+\frac{2}{1+\beta }\tau \tau ^{\frac{1+\beta }{1\beta }}\tau .$$
(25)
To summarize, if $`\gamma <1/4`$ and $`F(0)=0`$, $`F^{}(0)`$ exists (and then $`\mu _1=_kk^2C_k`$ is finite) so that i) implies ii): this means that if $`\gamma <1/4`$ but $`\alpha >1/2`$, i) has to be wrong, and $`_kkC_k<1`$.

A word of caution is needed here. To get the limiting equation (23), we have neglected terms of order $`\tau ^2`$ in (22). So strictly speaking, eq.(25) is correct only if $`\frac{1+\beta }{1\beta }<2`$, i.e. $`2/9<\gamma <1/4`$. A more careful analysis, analogous to that sketched in , would show that in general, in the absence of a giant component, the small $`\tau `$ expansion of $`F(\tau )`$ starts with a standard taylor series in $`\tau `$ up to order $`\frac{1+\beta }{1\beta }`$ and then a leading singularity proportional to $`\tau ^{\frac{1+\beta }{1\beta }}`$.

When $`\gamma <1/4`$, we write $`\beta =\sqrt{4\gamma 1}`$. Eq.(23) implies that

$$\frac{1}{2}\mathrm{log}(\gamma F^2+\tau F+\tau ^2)\frac{1}{\beta }\mathrm{arctan}\left(\frac{\beta F}{F+2\tau }\right).$$
(26)
is locally constant. As $`F`$ is continuous, the above quantity jumps by $`\pm \pi `$ when $`F+2\tau `$ changes sign. To fix conventions, we specify the function $`\mathrm{arctan}`$ by demanding that it is continuous and takes value in $`]\pi /2,\pi /2[`$. We argue by contradiction that $`F`$ cannot vanish at $`\tau =0`$ : if $`F`$ and $`\tau `$ are small, the argument of the log is a small positive number so the first term gets large and negative, while the term involving $`\mathrm{arctan}`$ remains bounded. So again i) fails.

We have established the percolation criterion announced in the previous section.

Furthermore, the relation $`\gamma 1/4=T^{\prime \prime }(1)(2\alpha 1)^2/4`$ shows that the region separating the percolating phase from the non percolating phase is $`\gamma =1/4`$ and $`2\alpha 10`$ : the emergence of a giant component is purely due to an increase of the variance of $`T`$ above the threshold $`1/4`$. This is a bit counterintuitive, because it implies that there are cases with arbitrary small $`\alpha `$ and a giant component.

To illustrate that point, we present the case when $`T`$ is a quadratic polynomial.

The properties that describe the system when there is no giant component or close to the threshold (when the giant component is small) only rely on equation eq.(23), and we refer to  for the detailed analysis that leads to eqs.(17,18,19,20,21).

### 6.3 Comparison with static graphs.

Maximum entropy static graphs with fixed in- and/or out-degree distributions have been studied in . If only the in-degree is fixed, the out-degree is always Poissonian, in contrast with the global geometric out-degree distribution of the evolving cousin model. Let us compare briefly the percolation criteria of the evolving case with two static maximum entropy situations. If $`T_{}(z)=T(z)`$ is the in-degree and $`T_+(z)`$ the out-degree distribution of the static model, we read from  that the condition for percolation is $`T^{\prime \prime }(1)T_+^{\prime \prime }(1)(T^{}(1)T^{}(1)^2)^2>0`$ 333This is, as should be the case for a static graph, symmetric in $`T`$ and $`T_+`$ because $`T^{}(1)=T_+^{}(1)`$ is automatic : any edge is $`in`$ at one end and $`out`$ at the other. When only the in-degree is fixed in the static case, $`T_+`$ is Poissonian, one finds $`\gamma +\alpha >1`$. When moreover the out-degree is fixed to be independent of the in-degree and follow a geometric law, so that the static graph has the same (global) degree distribution as the evolving graph, one finds $`2\gamma +\alpha ^2>1`$. The thresholds are different in the static and evolving cases. Moreover, the percolating region of the evolving case always contains strictly the static percolating region, because when $`\gamma <1/4`$ and $`\alpha <1/2`$ both $`\gamma +\alpha `$ and $`2\gamma +\alpha ^2`$ are less than $`3/4`$ : the inhomogeneities of the evolving graph, in which old vertices have an effective high coordinacy, favor the emergence of a giant component. However, this giant component starts with a very tiny size, in contrast with the static case, when its growth is generically linear.

### 6.4 Comments on the profile of the infinite cluster in the percolating phase.

For a Poissonian in-degree distribution, the authors of  obtained a closed equation which fitted perfectly with numerical simulations. The naive adaptation of their argument to the general case is straightforward, but gives an incorrect result.

Though we have not been able to derive a closed equation for the profile of the infinite component in the case of an arbitrary degree distribution, the successive derivatives of this profile at $`\sigma =1`$ can be computed in a systematic way as follows.

Defining $`Dz_zC`$, we can derive from the previous results that

$`\sigma _\sigma \rho `$ $`=`$ $`\left(\alpha zT^{}\left(D\right)\right)z_z\rho `$
$`zT(D)D`$ $`=`$ $`(\alpha zT^{}(D))z_zD`$
$`\rho (\sigma =1,z)`$ $`=`$ $`zT(D).`$
The first equation is just a rewriting of eq.(13), and the second one was obtained by applying the operator $`z_z`$ to eq.(12).The last equation gives the density at $`\sigma =1`$. Then the first equation can be used to get the derivative of the density at $`\sigma =1`$ :

$`\sigma _\sigma \rho (\sigma =1,z)`$ $`=`$ $`\left(\alpha zT^{}\left(D\right)\right)z_z\rho (\sigma =1,z)`$
$`=`$ $`\left(\alpha zT^{}\left(D\right)\right)z_z(zT(D))`$
$`=`$ $`\left(\alpha zT^{}\left(D\right)\right)(zT(D)+zT^{}(D)z_zD)`$
$`=`$ $`\left(\alpha zT^{}\left(D\right)\right)zT(D)+zT^{}(D)(zT(D)D)`$
$`=`$ $`\alpha zT(D)zDT^{}(D).`$
If $`D(z=1)=1`$, $`\rho (\sigma =1,z=1)=1`$, but $`\sigma _\sigma \rho (\sigma =1,z=1)=0`$. The same kind of algebra can be used to compute the successive derivatives $`\left((\sigma _\sigma )^n\rho \right)(\sigma =1,z)`$ for $`n=2,\mathrm{}`$. Again, one can check that this vanishes if $`D(z=1)=1`$. This is of course natural in the non percolating phase.

However, in the percolating phase, $`D(z=1)=1P_{\mathrm{}}`$ and one finds

$`\rho (\sigma =1,z=1)`$ $`=`$ $`T(1P_{\mathrm{}})`$
$`\sigma _\sigma \rho (\sigma =1,z=1)`$ $`=`$ $`\alpha T(1P_{\mathrm{}})(1P_{\mathrm{}})T^{}(1P_{\mathrm{}}).`$
Formally, we can write

$$\rho (\sigma ,z)=e^{\mathrm{log}\sigma [(\alpha zT^{}(D))z_z+(zT(D)D)_D]}zT(D),$$
(27)
where now $`z`$ and $`D`$ are independant variables, which is true order by order in an expansion in powers of $`\mathrm{log}\sigma `$. Writing $`\rho _{\mathrm{}}(\sigma )=1\rho (\sigma ,z=1)`$ for the profile of the giant component, eq.(27) can be used to obtain systematically, for small values of $`n`$, a (rather complicated) formula for $`\left((\sigma _\sigma )^n\rho _{\mathrm{}}\right)(\sigma =1)`$ as a polynomial in $`P_{\mathrm{}},T(1P_{\mathrm{}}),T^{}(1P_{\mathrm{}})\mathrm{},T^{(n)}(1P_{\mathrm{}})`$.
In particular, as a trivial example,

$$\rho _{\mathrm{}}(\sigma =1)=1T(1P_{\mathrm{}})\alpha P_{\mathrm{}}.$$
(28)
On the other hand, for $`\sigma `$ close to $`0`$,

$$1\rho _{\mathrm{}}(\sigma )\sigma ^\alpha ,$$
(29)
so the giant component contains all the old vertices, but only a fraction (which is exponentially small close the threshold) of the young vertices. That means the percolation transition is very inhomogeneous and takes mainly place in the part of the graph where it is denser than average.

## 7 Conclusions.

In this study, we have solved a model of evolving random graph which, albeit simple, involves an arbitrary in-degree distribution.

We have described the degree distributions and their local-in-time profiles. By construction, in-degree and out-degree at each vertex are independent. The local out-degree distribution follows an age dependant Poisson law, which after integration over ages leads to a geometric global out-degree distribution.

We have also made a detailed analysis of the distribution of component sizes, again at the global and the local-in-time level. We have shown the validity of the self averaging hypothesis by proving the equivalence with a direct exact tree enumeration.

The parameter controlling the percolation transition has been found, quite surprisingly, to be simply the variance of the in-degree distribution, in contrast with the analogous static models.

Below the transition, the large components have a size which scales like a power of the total size of the graph. The size of the giant component close to the threshold has been computed. It is exponentially small. The unusual fluctuation induced percolation mechanism might be the reason why the critical behavior of this models is so different from what is observed in the case of static graphs (see ). There, the generic behavior close to the transition is a linearly growing giant component.

We have shown how all these differences could be used to discriminate in certain cases between a static and an evolving random graph even when the in and out degree distributions are the same for both.

Among the unanswered questions is a direct description of the profile of the giant component. For a Poissonian in-degree distribution, the authors of  obtained a closed equation which fitted perfectly with numerical simulations. The naive adaptation of their argument to the general case is straightforward, but gives an incorrect result. It would be desirable to find a valid argument for general $`T`$, or more modestly to understand why the argument in fact works for the Poissonian case.

## Appendix A A combinatorial identity.

We show that the tree distribution, eqs.(15,16), leads to the generating function formula, eq.(12).
If $`V`$ is a finite (nonempty) set, we denote by $`𝒯_V`$ the set of trees with vertex set $`V`$.

If moreover $`V`$ is totally ordered , we denote its supremum by $`s_V`$. If moreover $`|V|2`$, we define $`𝒯_V^n`$ for $`n=1,2,\mathrm{},|V|1`$ as the set of trees with vertex set $`V`$ such that vertex $`s_V`$ has $`n`$ neighbors. Note that $`𝒯_V^n`$ is non empty.

If $`V=[1,\mathrm{},k]`$ (with the usual order) we denote $`𝒯_V`$ by $`𝒯_k`$ and if $`k2`$ we denote $`𝒯_V^n`$ by $`𝒯_k^n`$ for $`n=1,\mathrm{},k1`$. We shall sometimes use the shorthand notation $`𝒯_{k_1,\mathrm{},k_n}𝒯_{k_1}\times \mathrm{}\times 𝒯_{k_n}`$.

If $`V`$ is a totally ordered finite (nonempty) set, there is a unique order preserving map from $`V`$ to $`[1,\mathrm{},|V|]`$, so that there is a canonical bijection between $`𝒯_V`$ and $`𝒯_{|V|}`$. For the same reason, if moreover $`|V|2`$ there is a canonical bijection between $`𝒯_V^n`$ and $`𝒯_{|V|}^n`$ for any $`n=1,2,\mathrm{},|V|1`$.

Let $`V`$ be a totally ordered finite (nonempty) set $`V`$ with $`|V|2`$ and let $`n[1,\mathrm{},|V|1]`$. Take a tree $`\mathrm{{\rm Y}}𝒯_V^n`$.

To $`\mathrm{{\rm Y}}`$ we associate the following data

$`[i]`$ An $`n`$-tuple of positive integers $`(k_1,\mathrm{},k_n)`$ such that

$$k_1+\mathrm{}+k_n=|V|1.$$

$`[ii]`$ A sequence $`(\mathrm{{\rm Y}}_1,\mathrm{},\mathrm{{\rm Y}}_n)𝒯_{k_1,\mathrm{},k_n}`$.

$`[iii]`$ A sequence $`(V_1,\mathrm{},V_n)`$ of disjoint subsets of $`V`$, each endowed with the order induced from that of $`V`$, such that

$`[a`$\] $`(|V_1|,\mathrm{},|V_n|)=(k_1,\mathrm{},k_n)`$,

$`[b]`$ $`V_1\mathrm{}V_n=V\backslash \{s_V\}`$,

$`[c]`$ $`s_{V_1}<\mathrm{}<s_{V_n}`$ for the order in $`V`$.

$`[iv]`$ A sequence $`(v_1,\mathrm{},v_n)[1,\mathrm{},k_1]\times \mathrm{}\times [1,\mathrm{},k_n]`$,

as follows :

Remove from $`\mathrm{{\rm Y}}`$ the vertex $`s_V`$ and the edges incident to it. What remains is a forest made of $`n`$ components. There is a single way to label the corresponding $`n`$ vertex sets $`V_1,\mathrm{},V_n`$ so as to satisfy $`[c]`$, and then we define $`(k_1,\mathrm{},k_n)`$ by $`[a]`$ so we have obtained $`[i]`$ and $`[iii]`$. For $`l[1,\mathrm{},n]`$ the connected component with vertex set $`V_l`$ is a tree. We define $`\mathrm{{\rm Y}}_l`$ as its canonical representative in $`𝒯_{k_l}`$ and by $`v_l`$ the vertex of $`\mathrm{{\rm Y}}_l`$ whose preimage in $`V_l`$ is connected to $`s_V`$ in $`\mathrm{{\rm Y}}`$; this gives $`[ii]`$ and $`[iv]`$.

Conversely, one can recover $`\mathrm{{\rm Y}}`$ from the data by reversing the procedure.

We let $`𝒫_{k_1,\mathrm{},k_n}^V`$ be the set of sequences $`(V_1,\mathrm{},V_n)`$ of disjoint subsets of $`V`$, each endowed with the order induced from that of $`V`$, satisfying conditions $`[a]`$ and $`[b]`$ above. The set obtained when moreover $`[c]`$ is taken into account is denoted by $`𝒫_{k_1,\mathrm{},k_n}^{restrV}`$. There is a $`1`$ to $`n!`$ corespondence between $`𝒫_{k_1,\mathrm{},k_n}^{restrV}`$ and $`𝒫_{k_1,\mathrm{},k_n}^V`$

To summarize what we have found, we have put $`𝒯_V^n`$ in

$`1`$ to $`1`$ correspondence with the disjoint union

$$𝒯_{k_1,\mathrm{},k_n}\times 𝒫_{k_1,\mathrm{},k_n}^{restrV}\times [1,\mathrm{},k_1]\times \mathrm{}\times [1,\mathrm{},k_n],$$

$`1`$ to $`n!`$ correspondence with the disjoint union

$$𝒯_{k_1,\mathrm{},k_n}\times 𝒫_{k_1,\mathrm{},k_n}^V\times [1,\mathrm{},k_1]\times \mathrm{}\times [1,\mathrm{},k_n],$$

where in both cases the union is taken over $`n`$-tuples of positive integers $`(k_1,\mathrm{},k_n)`$ such that $`k_1+\mathrm{}+k_n=|V|1`$.

From now on, we fix $`V=[1,\mathrm{},k]`$ for some integer $`k2`$. We assign to each tree $`\mathrm{{\rm Y}}𝒯_k`$ a weight as follows. Write $`m_i`$ for be the number of edges of $`\mathrm{{\rm Y}}`$ connecting $`i`$ to $`[1,\mathrm{},i1]`$. Then

$$𝒲_\mathrm{{\rm Y}}=\tau _{m_1}\mathrm{}\tau _{m_k}_{0\sigma _1\mathrm{}\sigma _k1}𝑑\sigma _1\mathrm{}𝑑\sigma _k\sigma _1^{\alpha m_1}\mathrm{}\sigma _k^{\alpha m_k}.$$

Write $`_\mathrm{{\rm Y}}`$ for the first factor and $`_\mathrm{{\rm Y}}`$ for the integral, so that $`𝒲_\mathrm{{\rm Y}}=_\mathrm{{\rm Y}}_\mathrm{{\rm Y}}`$. We change variables and set $`\sigma _k=\stackrel{~}{\sigma _k}`$ and $`\sigma _i=\stackrel{~}{\sigma }_i\stackrel{~}{\sigma }_k`$ for $`i=1,\mathrm{},k1`$. The power of $`\stackrel{~}{\sigma }_k`$ in the new integrand is $`k1+k\alpha m_1\mathrm{}m_k=k\alpha `$ so integration over $`\stackrel{~}{\sigma }_k`$ leads to $`_\mathrm{{\rm Y}}=\frac{1}{1+k\alpha }\stackrel{~}{}_\mathrm{{\rm Y}}`$ with

$$\stackrel{~}{}_\mathrm{{\rm Y}}=_{0\sigma _1\mathrm{}\sigma _{k1}1}𝑑\sigma _1\mathrm{}𝑑\sigma _{k1}\sigma _1^{\alpha m_1}\mathrm{}\sigma _{k1}^{\alpha m_{k1}}.$$

To avoid ambiguities when several trees are used at the same time, we shall sometimes write $`m_i^\mathrm{{\rm Y}}`$ instead of $`m_i`$.

Suppose that $`\mathrm{{\rm Y}}𝒯_k^n`$, which amounts to set $`n=m_k`$. We want to express $`𝒲_\mathrm{{\rm Y}}`$ in terms of its decomposition, in fact in term of the $`n`$ trees $`(\mathrm{{\rm Y}}_1,\mathrm{},\mathrm{{\rm Y}}_n)𝒯_{k_1}\times \mathrm{}\times 𝒯_{k_n}`$ with $`k_1+\mathrm{}+k_n=|V|1`$, and of the partition $`V_1\mathrm{}V_n`$ (it turns out that $`𝒲_\mathrm{{\rm Y}}`$ does not depend on the choice of one vertex in each $`V_i`$).

The decomposition procedure associates to each $`i[1,\mathrm{},k1]`$ one of the trees $`\mathrm{{\rm Y}}_1,\mathrm{},\mathrm{{\rm Y}}_n`$, say $`\mathrm{{\rm Y}}_l`$ and a vertex $`i^{}[1,\mathrm{},k_l]`$ in $`\mathrm{{\rm Y}}_l`$. By construction of the decomposition, if $`j[1,\mathrm{},i1]`$ is such that $`(i,j)`$ is an edge of $`\mathrm{{\rm Y}}`$ then $`i`$ and $`j`$ have the same $`\mathrm{{\rm Y}}_l`$, $`j^{}[1,\mathrm{},i^{}1]`$ and $`(i^{},j^{})`$ is an edge of $`\mathrm{{\rm Y}}_l`$. Hence $`m_i^\mathrm{{\rm Y}}=m_i^{}^{\mathrm{{\rm Y}}_l}`$ and $`_\mathrm{{\rm Y}}=\tau _n_{\mathrm{{\rm Y}}_1}\mathrm{}_{\mathrm{{\rm Y}}_n}`$ has a simple multiplicative behavior.

Our aim is now to show that when $`(\mathrm{{\rm Y}}_1,\mathrm{},\mathrm{{\rm Y}}_n)`$ (and then automatically $`(k_1,\mathrm{},k_n)`$) are fixed $`_{𝒫_{k_1,\mathrm{},k_n}^{[1,\mathrm{},k]}}\stackrel{~}{}_\mathrm{{\rm Y}}=_{\mathrm{{\rm Y}}_1}\mathrm{}_{\mathrm{{\rm Y}}_n}`$.

We introduce another tree, $`\dot{\mathrm{{\rm Y}}}`$, whose decomposition is made of the same trees $`(\mathrm{{\rm Y}}_1,\mathrm{},\mathrm{{\rm Y}}_n)`$ as $`\mathrm{{\rm Y}}`$, but with $`\dot{V}_1=[1,\mathrm{},k_1],\dot{V}_2=[k_1+1,\mathrm{},k_1+k_2],\mathrm{}`$ and $`\dot{v}_1=k_1,\dot{v}_2=k_1+k_2,\mathrm{}`$. Write $`\dot{m}_i`$ for the number of edges of $`\dot{\mathrm{{\rm Y}}}`$ connecting $`i`$ to $`[1,\mathrm{},i1]`$.

There is a unique permutation, say $`\lambda `$, of $`[1,\mathrm{},k1]`$ which maps $`V_1`$ into $`\dot{V}_1`$, $`V_2`$ into $`\dot{V}_2`$, $`\mathrm{}`$, and is strictly increasing in each. Then $`m_i=\dot{m}_{\lambda (i)}`$ for each $`i[1,\mathrm{},k1]`$. If we set $`\sigma _i=\dot{\sigma }_{\lambda (i)}`$ we obtain

$$\stackrel{~}{}_\mathrm{{\rm Y}}=_{0\dot{\sigma }_{\lambda (1)}\mathrm{}\dot{\sigma }_{\lambda (k1)}1}𝑑\dot{\sigma }_1\mathrm{}𝑑\dot{\sigma }_{k1}\dot{\sigma }_1^{\alpha m_1}\mathrm{}\dot{\sigma }_{k1}^{\alpha m_{k1}}.$$

Write $`R_\lambda `$ for the region of integration $`0\dot{\sigma }_{\lambda (1)}\mathrm{}\dot{\sigma }_{\lambda (k1)}1`$.

Conversely, $`(k_1,\mathrm{},k_n)`$ being kept fixed, if $`(V_1,\mathrm{},V_n)`$ describes $`𝒫_{k_1,\mathrm{},k_n}^{[1,\mathrm{},k]}`$ each permutation $`\lambda `$ of $`[1,\mathrm{},k1]`$ such that $`\lambda ^1`$ is strictly increasing when restricted to $`\dot{V}_1,\mathrm{},\dot{V}_n`$ appears exactly once. If $`R`$ be the union of all such $`R_\lambda `$’s (the intersection of different $`R_\lambda `$’s is of measure 0), one checks that $`(\dot{\sigma }_1,\mathrm{},\dot{\sigma }_{k1})`$ is in $`R`$ if and only if $`0\dot{\sigma }_1\mathrm{}\dot{\sigma }_{k_1}1`$, $`0\dot{\sigma }_{k_1+1}\mathrm{}\dot{\sigma }_{k_1+k_2}1`$, $`\mathrm{}`$.

This shows that when $`(\mathrm{{\rm Y}}_1,\mathrm{},\mathrm{{\rm Y}}_n)`$ are fixed $`_{𝒫_{k_1,\mathrm{},k_n}^{[1,\mathrm{},k]}}\stackrel{~}{}_\mathrm{{\rm Y}}=_{\mathrm{{\rm Y}}_1}\mathrm{}_{\mathrm{{\rm Y}}_n}`$.

If we recall moreover that $`_\mathrm{{\rm Y}}=\tau _n_{\mathrm{{\rm Y}}_1}\mathrm{}_{\mathrm{{\rm Y}}_n}`$ and that $`𝒯_V^n`$ is in $`1`$ to $`n!`$ correspondence with the disjoint union

$$_{(k_1,\mathrm{},k_n)}𝒯_{k_1,\mathrm{},k_n}\times 𝒫_{k_1,\mathrm{},k_n}^V\times [1,\mathrm{},k_1]\times \mathrm{}\times [1,\mathrm{},k_n],$$

we obtain as an immediate consequence that

$$(1+k\alpha )\underset{\mathrm{{\rm Y}}𝒯_k^n}{}𝒲_\mathrm{{\rm Y}}=\underset{(k_1,\mathrm{},k_n)}{}\underset{(\mathrm{{\rm Y}}_1,\mathrm{},\mathrm{{\rm Y}}_n)𝒯_{k_1,\mathrm{},k_n}}{}\frac{\mathrm{{\rm Y}}_n}{n!}k_1𝒲_{\mathrm{{\rm Y}}_1}\mathrm{}k_n𝒲_{\mathrm{{\rm Y}}_n}.$$

If we define $`𝒲^{(k)}_{\mathrm{{\rm Y}}𝒯_k}𝒲_\mathrm{{\rm Y}}=_n_{\mathrm{{\rm Y}}𝒯_k^n}𝒲_\mathrm{{\rm Y}}`$, it is plain that $`_k𝒲^{(k)}z^k`$ satisfies eq.(12), which has only one formal power series solution vanishing at $`z=0`$. QED.