On Asymptotic Properties of Bell Polynomials and Concentration of Vertex Degree of Large Random Graphs
- PDF / 464,096 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 194 Views
On Asymptotic Properties of Bell Polynomials and Concentration of Vertex Degree of Large Random Graphs O. Khorunzhiy1 Received: 9 July 2019 / Revised: 5 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study concentration properties of vertex degrees of n-dimensional Erd˝os–Rényi random graphs with edge probability ρ/n by means of high moments of these random variables in the limit when n and ρ tend to infinity. These moments are asymptotically close to one-variable Bell polynomials Bk (ρ), k ∈ N, that represent moments of the Poisson probability distribution P(ρ). We study asymptotic behavior of the Bell polynomials and modified Bell polynomials for large values of k and ρ with the help of the local limit theorem for auxiliary random variables. Using the results obtained, we get upper bounds for the deviation probabilities of the normalized maximal vertex degree of the Erd˝os–Rényi random graphs in the limit n, ρ → ∞ such that the ratio ρ/ log n remains finite or infinitely increases. Keywords Random graphs · Vertex degree · Bell polynomials Mathematics Subject Classification (2010) 05A16 · 05C80 · 60B20
1 Introduction This paper is motivated by studies of the spectral properties of random matrices associated with random graphs of the Erd˝os–Rényi type [6]. In these graphs, the edges can be represented by a family of independent Bernoulli random variables, and we consider the case when the average value of these variables is given by ρ/n, where n (ρ) is the number of vertices in the graph n . (ρ) More precisely, we assume that the edges of n are non-oriented and there are (ρ) (ρ) no loops in n . In this case, the random graph n is associated with its adjacency (ρ) matrix that is an n-dimensional real symmetric matrix An , whose elements above the
B 1
O. Khorunzhiy [email protected] Université de Versailles - Saint-Quentin, 45, Avenue des Etats-Unis, 78035 Versailles, France
123
Journal of Theoretical Probability
diagonal are given by an ensemble of jointly independent Bernoulli random variables (n,ρ) {ai j }1≤i< j≤n
A(ρ) n
ij
=
(n,ρ) ai j
=
1, with probability ρ/n, , 1 ≤ i < j ≤ n, 0 < ρ < n 0, with probability 1 − ρ/n (1.1)
(n,ρ)
and aii = 0, 1 ≤ i ≤ n. In the majority of aspects, the random graphs ensemble (ρ) {n } is very similar to the random graphs introduced and studied by P. Erd˝os and A. (ρ) Rényi [13], and we refer to {n } as to the Erd˝os–Rényi ensemble of random graphs [6,20]. (ρ) Asymptotic properties of random graphs n in the limit of infinite n are extensively studied (see monographs [11,20,32]), as well as the spectral properties of their (ρ) adjacency matrices An [16,21,27,29]. The spectral properties of the second differ(ρ) ential form on the vertices of n given by (ρ) = Bn(ρ) − A(ρ) n , n
(ρ) (n,ρ) = δi j bi , 1 ≤ i ≤ j ≤ n, where Bn ij
(n,ρ)
bi
=
n
(n,ρ)
ail
(1.2)
l=1
and δi j is the Kronecker delta-symbol equal to one if i = j and to zero otherwise have been also extensively studied [9,25]. Usual
Data Loading...
