Combinatorial algebra and random graphs

V. E. Stepanov

Teoriâ veroâtnostej i ee primeneniâ, Tome 14 (1969) no. 3, pp. 393-420

Résumé

Let $A$ be a finite set of vertices and $\lambda_a>0$ be the intensity of the vertex $a\in A$. A random time-dependent graph $\mathscr G_L(A\mid t)$ is defined as follows: at time $t=0$ all the vertices are isolated; the probability that at time $t>0$ vertices $a$ and $b$ are connected equals $1-e^{-\lambda}a^\lambda b^t$, and the connections appear independently for different pairs, let $\mathbf P_L(A\mid t)$ be the probability that the random graph $\mathscr G_L(A\mid t)$ is connected. In the paper, an explicit expression for $\mathbf P_L(A\mid t)$ is found, a number of combinatorial relations including the probabilities $\mathbf P_L(A\mid t)$ is obtained, and it is proved that if the set of vertices $A$, intensities of vertices $\lambda_a$, and time $t$ are changed in a certain way, then, under some conditions, $\mathbf P_L(A\mid t)e^{\mu(A\mid t)}\to1$, where $$ \mu(A\mid t)=\sum_{a\in A}\exp\{-t\lambda_aL(A)\}\quad\text{and}\quad L(A)=\sum_{a\in A}\lambda_a. $$