Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
We study an eigenvalue distribution of the adjacency matrix A^(N,p,a) of the weighted random bipartite graph Г = ГN,p. We assume that the graph has N vertices, the ratio of parts is α(1-α), and the average number of the edges attached to one vertex is ap or (1-a)p. To every edge of the graph eij, w...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України
2014
|
| Schriftenreihe: | Журнал математической физики, анализа, геометрии |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/106794 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Eigenvalue Distribution of a Large Weighted Bipartite Random Graph / V. Vengerovsky // Журнал математической физики, анализа, геометрии. — 2014. — Т. 10, № 2. — С. 240-255. — Бібліогр.: 19 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-106794 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1067942016-10-06T03:02:19Z Eigenvalue Distribution of a Large Weighted Bipartite Random Graph Vengerovsky, V. We study an eigenvalue distribution of the adjacency matrix A^(N,p,a) of the weighted random bipartite graph Г = ГN,p. We assume that the graph has N vertices, the ratio of parts is α(1-α), and the average number of the edges attached to one vertex is ap or (1-a)p. To every edge of the graph eij, we assign the weight given by a random variable aij with all moments finite. We consider the moments of the normalized eigenvalue counting measure sN,p,a of A^(N,p,a). The weak convergence in probability of the normalized eigenvalue counting measures is proved. Исследуется распределение собственных значений матрицы смежности A^(N,p,a) взвешенного случайного двудольного графа Г = ГN,p. Предполагается, что этот граф имеет N вершин, соотношение размера его частей равно α(1-α) и средняя степень вершины равна ap и (1-a)p. К каждому ребру графа eij приписывается в качестве веса случайная величина aij, у которой все моменты конечны. Рассмотрены моменты нормированной считающей меры sN,p,a матрицы A^(N,p,a). Доказана слабая сходимость по вероятности нормированных считающих мер. 2014 Article Eigenvalue Distribution of a Large Weighted Bipartite Random Graph / V. Vengerovsky // Журнал математической физики, анализа, геометрии. — 2014. — Т. 10, № 2. — С. 240-255. — Бібліогр.: 19 назв. — англ. 1812-9471 http://dspace.nbuv.gov.ua/handle/123456789/106794 en Журнал математической физики, анализа, геометрии Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We study an eigenvalue distribution of the adjacency matrix A^(N,p,a) of the weighted random bipartite graph Г = ГN,p. We assume that the graph has N vertices, the ratio of parts is α(1-α), and the average number of the edges attached to one vertex is ap or (1-a)p. To every edge of the graph eij, we assign the weight given by a random variable aij with all moments finite. We consider the moments of the normalized eigenvalue counting measure sN,p,a of A^(N,p,a). The weak convergence in probability of the normalized eigenvalue counting measures is proved. |
| format |
Article |
| author |
Vengerovsky, V. |
| spellingShingle |
Vengerovsky, V. Eigenvalue Distribution of a Large Weighted Bipartite Random Graph Журнал математической физики, анализа, геометрии |
| author_facet |
Vengerovsky, V. |
| author_sort |
Vengerovsky, V. |
| title |
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph |
| title_short |
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph |
| title_full |
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph |
| title_fullStr |
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph |
| title_full_unstemmed |
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph |
| title_sort |
eigenvalue distribution of a large weighted bipartite random graph |
| publisher |
Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/106794 |
| citation_txt |
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph / V. Vengerovsky // Журнал математической физики, анализа, геометрии. — 2014. — Т. 10, № 2. — С. 240-255. — Бібліогр.: 19 назв. — англ. |
| series |
Журнал математической физики, анализа, геометрии |
| work_keys_str_mv |
AT vengerovskyv eigenvaluedistributionofalargeweightedbipartiterandomgraph |
| first_indexed |
2025-07-07T19:01:32Z |
| last_indexed |
2025-07-07T19:01:32Z |
| _version_ |
1837015914951737344 |
| fulltext |
Journal of Mathematical Physics, Analysis, Geometry
2014, vol. 10, No. 2, pp. 240–255
Eigenvalue Distribution of a Large Weighted Bipartite
Random Graph
V. Vengerovsky
B. Verkin Institute for Low Temperature Physics and Engineering
National Academy of Sciences of Ukraine
47 Lenin Ave., Kharkiv 61103, Ukraine
E-mail: vengerovsky@ilt.kharkov.ua
Received December 20, 2012, revised January 28, 2014
We study an eigenvalue distribution of the adjacency matrix A(N,p,α) of
the weighted random bipartite graph Γ = ΓN,p. We assume that the graph
has N vertices, the ratio of parts is
α
1− α
, and the average number of the
edges attached to one vertex is αp or (1− α)p. To every edge of the graph
eij , we assign the weight given by a random variable aij with all moments
finite.
We consider the moments of the normalized eigenvalue counting measure
σN,p,α of A(N,p,α). The weak convergence in probability of the normalized
eigenvalue counting measures is proved.
Key words: random bipartite graph, eigenvalue distribution, counting
measure.
Mathematics Subject Classification 2010: 15B52.
1. Introduction
The spectral theory of graphs is an actively developing field of mathematics
involving a variety of methods and deep results (see the monographs [4, 5, 10]).
Given a graph with N vertices, one can associate with it many different matrices,
but the most studied are the adjacency matrix and the Laplacian matrix of the
graph. Commonly, the set of N eigenvalues of the adjacency matrix is referred
to as the spectrum of the graph. In these studies, the dimension of the matrix
N is usually regarded as a fixed parameter. The spectra of infinite graphs are
considered in certain particular cases of graphs having one or another regular
structure (see, for example, [12]).
Another large class of graphs, where the limiting transition N →∞ provides
a natural approximation, is represented by random graphs [2, 11]. In this branch,
c© V. Vengerovsky, 2014
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
geometrical and topological properties of graphs (e.g., the number of connected
components, the size of a maximal connected component) are studied for the
immense number of random graph ensembles. One of the classes of the prime
reference is the binomial random graph (see, e.g., [11]). Given a number pN ∈
(0, 1), the family of graphs G(N, pN ) is defined by taking as Ω the set of all
graphs on N vertices with the probability
P (G) = p
e(G)
N (1− pN )(
N
2 )−e(G), (1.1)
where e(G) is the number of the edges of G. Most of the random graphs studies
are devoted to the cases where pN → 0 as N →∞.
Intersection of these two branches of the theory of graphs includes the spectral
theory of random graphs which is not properly studied. However, a number of
powerful tools can be employed here, because the ensemble of random symmetric
N×N adjacency matrices AN is a particular representative of the random matrix
theory, where the limiting transition N → ∞ has been intensively studied since
the pioneering work by E. Wigner [19] was published. Initiated by theoretical
physics applications, the spectral theory of random matrices has revealed deep
nontrivial links with many fields of mathematics.
The spectral properties of random matrices corresponding to (1.1) were stu-
died in the limit N →∞ both in numerical and theoretical physics [6–8, 16–18].
There are two major asymptotic regimes: pN À 1/N and pN = O(1/N) and the
corresponding models are called the dilute random matrices and sparse random
matrices, respectively. The first studies of spectral properties of sparse and dilute
random matrices in the physical literature are related with the works [16–18],
where equations for the limiting density of states of sparse random matrices were
derived. In [16] and [9], a number of important results on the universality of the
correlation functions and the Anderson localization transition were obtained. But
all these results were obtained by using non-rigorous replica and supersymmetry
methods.
At the mathematical level of rigour, the eigenvalue distribution of dilute ran-
dom matrices was studied in [14]. It was shown that the normalized eigenvalue
counting function of
1√
NpN
AN,pN
(1.2)
converges in the limit N, pN → ∞ to the distribution of explicit form known
as the semicircle, or Wigner law [19]. The moments of this distribution verify
the well-known recurrent relation for the Catalan numbers and can be found
explicitly. Therefore one can say that the dilute random matrices represent an
explicitly solvable model (see also [17, 18]).
In the series of papers [1–3] and in [13], the adjacency matrix and the Laplace
matrix of random graphs (1.1) with pN = pN were studied. It was shown that
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 241
V. Vengerovsky
the sparse random matrix ensemble can also be viewed as the explicitly solvable
model.
In the present paper we consider a bipartite analogue of the large sparse
random graph. The paper is a modification of one part of [13] for this case.
2. Main Results
We consider the randomly weighted adjacency matrix of random bipartite
graphs. Let Ξ = {aij , i≤j, i, j∈N} be the set of jointly independent identically
distributed (i.i.d.) random variables determined on the same probability space
and possessing the moments
Eak
ij =Xk <∞, ∀ i, j, k ∈ N, (2.1)
where E denotes the mathematical expectation corresponding to Ξ. We set aji =
aij for i≤j .
Given 0< p≤N , let us define the family D
(p)
N ={d(N,p)
ij , i≤ j, i, j ∈ 1, N} of
jointly independent random variables
d
(N,p)
ij =
{
1, with probability p/N,
0, with probability 1− p/N.
(2.2)
We determine dji = dij and assume that D
(p)
N is independent from Ξ.
Let α ∈ (0, 1), define Iα,N = 1, [α N ], where [·] is a floor function. Now one
can consider the real symmetric N ×N matrix A(N,p,α)(ω):
[
A(N,p,α)
]
ij
=
{
aij d
(N,p)
ij , if (i ∈ Iα,N ∧ j /∈ Iα,N ) ∨ (i /∈ Iα,N ∧ j ∈ Iα,N ),
0, otherwise
(2.3)
that has N real eigenvalues λ
(N,p,α)
1 ≤λ
(N,p,α)
2 ≤ . . .≤ λ
(N,p,α)
N .
The normalized eigenvalue counting function (or integrated density of states
(IDS)) of A(N,p,α) is determined by the formula
σ
(
λ;A(N,p,α)
)
=
]{j : λ
(N,p,α)
j <λ}
N
.
Theorem 1. Under the condition
X2m ≤ (Cm)2m , m ∈ N, (2.4)
the measure σ
(
λ; A(N,p,α)
)
converges weakly in probability to the nonrandom mea-
sure σp,α
σ
(
· ; A(N,p,α)
)
→ σp,α , N →∞, (2.5)
242 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
which can be uniquely determined by its moments
∫
λsdσp,α =
m
(p,α)
k =
k∑
i=0
(
S(1)(k, i) + S(2)(k, i)
)
, if s = 2k,
0, if s = 2k − 1,
(2.6)
where the numbers S(1)(k, i), S(2)(k, i) can be found from the system of recurrent
relations
S(1)(l, r) = p
r∑
f=1
(
r − 1
f − 1
)
X2f
l−r∑
u=0
S(1)(l− u− f, r− f)
u∑
v=0
(
f + v − 1
f − 1
)
S(2)(u, v),
(2.7)
S(2)(l, r) = p
r∑
f=1
(
r − 1
f − 1
)
X2f
l−r∑
u=0
S(2)(l − u− f, r − f)
u∑
v=0
(
f + v − 1
f − 1
)
S(1)(u, v)
(2.8)
with the initial conditions
S(1)(l, 0) = αδl,0, S(2)(l, 0) = (1− α)δl,0. (2.9)
The following denotations are used:
M(N,p,α)
k =
∫
λkdσ
(
λ; A(N,p,α)
)
, M
(N,p,α)
k = EM(N,p,α)
k ,
C
(N,p,α)
k,m = E
{
M(N,p,α)
k M(N,p,α)
m
}
− E
{
M(N,p,α)
k
}
E
{
M(N,p,α)
m
}
.
Theorem 1 is a corollary of Theorem 2
Theorem 2. Assuming conditions (2.4),
(i) The correlators C
(N,p,α)
k,m vanish in the limit N →∞:
C
(N,p,α)
k,m ≤ C(k,m, p, α)
N
, ∀ k,m ∈ N. (2.10)
(ii) The limit of the s-th moment exists for all s ∈ N:
lim
N→∞
M (N,p,α)
s =
k∑
i=0
(
S(1)(k, i) + S(2)(k, i)
)
, if s = 2k,
0, if s = 2k − 1,
(2.11)
where the numbers S(1)(k, i), S(2)(k, i) are determined by (2.7)–(2.9).
(iii) The limiting moments
{
m
(p,α)
k
}∞
k=1
satisfy Carleman’s condition
∞∑
k=1
1
2k
√
m
(p,α)
k
= ∞. (2.12)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 243
V. Vengerovsky
3. Proof of Theorem 1
3.1. Walks and contributions
Using the independence of families Ξ and D
(p)
N , we have
M
(N,p)
k =
∫
E{λkdσA(N,p,α)}=E
(
1
N
N∑
i=1
[λ(N,p,α)
i ]k
)
=
1
N
E
(
Tr[A(N,p,α)]k
)
=
1
N
N∑
j1=1
N∑
j2=1
. . .
N∑
jk=1
E
(
A
(N,p,α)
j1,j2
A
(N,p,α)
j2,j3
. . . A
(N,p,α)
jk,j1
)
=
1
N
N∑
j1=1
N∑
j2=1
. . .
N∑
jk=1
E (aj1,j2aj2,j3 . . . ajk,j1)
×E
(
d
(N,p)
j1,j2
d
(N,p)
j2,j3
. . . d
(N,p)
jk,j1
)
ξ
(N,α)
j1,j2
ξ
(N,α)
j2,j3
. . . ξ
(N,α)
jk,j1
, (3.1)
where
ξ
(N,α)
ij =
{
1, if (i ∈ Iα,N ∧ j /∈ Iα,N ) ∨ (i /∈ Iα,N ∧ j ∈ Iα,N ),
0, otherwise.
Let W
(N)
k be a set of closed walks of k steps over the set 1, N :
W
(N)
k ={w=(w1, w2, · · · , wk, wk+1 = w1) : ∀i∈1, k + 1 wi∈1, N}.
For w∈W
(N)
k , let us denote a(w) =
∏k
i=1 awi,wi+1 , d(N,p)(w) =
∏k
i=1 d
(N,p)
wi,wi+1 and
ξ(N,α)(w)=
∏k
i=1 ξ
(N,α)
wi,wi+1 . Then we have
M
(N,p)
k =
1
N
∑
w∈W
(N)
k
Ea(w)Ed(N,p)(w) ξ(N,α)(w). (3.2)
Let w ∈W
(N)
k and f, g ∈ 1, N . Denote by nw(f, g) the number of steps f → g
and g → f ,
nw(f, g) = #{i∈1, k : (wi =f ∧ wi+1 =g) ∨ (wi =g ∧ wi+1 =f)}.
Then
Ea(w)=
N∏
f=1
N∏
g=f
Xnw(f,g).
Given w∈W
(N)
k , let us define the sets Vw = ∪k
i=1{wi} and Ew = ∪k
i=1{(wi, wi+1)},
where (wi, wi+1) is a non-ordered pair. It is easy to see that Gw =(Vw, Ew) is a
simple non-oriented graph and the walk w covers the graph Gw. Let us call Gw
244 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
the skeleton of walk w. We denote by nw(e) the number of passages of the edge
e by the walk w in direct and inverse directions. For (wj , wj+1) = ej ∈ Ew, we
denote aej =awj ,wj+1 =awj+1,wj . Then we obtain
Ea(w)=
∏
e∈Ew
Eanw(e)
e =
∏
e∈Ew
Xnw(e).
Similarly, we can write
Ed(N,p)(w)=
∏
e∈Ew
E
(
[d(N,p)
e ]nw(e)
)
=
∏
e∈Ew
p
N
.
Then we can write (3.2) in the form
M
(N,p)
k =
1
N
∑
w∈W
(N)
k
ξ(N,α)(w)
∏
e∈Ew
pXnw(e)
N
=
∑
w∈W
(N)
k
ξ(N,α)(w)
(
p|Ew|
N |Ew|+1
∏
e∈Ew
Xnw(e)
)
=
∑
w∈W
(N)
k
θ(w), (3.3)
where θ(w) is the contribution of the walk w to the mathematical expectation
of the corresponding moment. To perform the limiting transition N → ∞, it is
natural to divide W
(N)
k into the classes of equivalence. The walks w(1) and w(2)
are equivalent w(1) ∼ w(2) if and only if there exists a bijection φ between the
sets of vertices Vw(1) and Vw(2) such that for i = 1, 2, . . . , k, w
(2)
i =φ(w(1)
i ),
w(1) ∼ w(2) ⇐⇒ ∃φ : Vw(1)
bij→ Vw(2) : ∀ i∈1, k + 1 ,
w
(2)
i =φ(w(1)
i ) ∧ 1Iα,N
(w(2)
i ) = 1Iα,N
(φ(w(1)
i )).
The last condition requires that every vertex and its image be in the same compo-
nent. It is essential for further computations because the contribution of a walk
equals zero when the origin and the end of the step are in the same component.
Let us denote by [w] the class of equivalence of walk w, and by C
(N)
k the set of
these classes. It is obvious that if two walks w(1) and w(2) are equivalent, then
their contributions are equal:
w(1) ∼ w(2) =⇒ θ(w(1))=θ(w(2)).
The cardinality of the class of equivalence [w] is equal to the number of all map-
pings φ : Vw → 1, N such that φ(V1,w) ⊂ Iα,N and φ(V2,w) ⊂ 1, N \ Iα,N (where
V1,w = Vw ∩ Iα,N and V2,w = Vw \ Iα,N ) is equal to the number [α N ]([α N ]− 1)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 245
V. Vengerovsky
. . . ([α N ]−|V1,w|+1)(N− [α N ])(N− [α N ]−1) . . . (N− [α N ]−|V2,w|+1). Then
(3.3) can be written in the form
M
(N,p)
k =
∑
w∈W
(N)
k
ξ(N,α)(w)
(
p|Ew|
N |Ew|+1
∏
e∈Ew
Xnw(e)
)
=
∑
[w]∈C(N)
k
ξ(N,α)(w)
∏
e∈Ew
Xnw(e)
(
[α N ]([α N ]− 1) . . . ([α N ]− |V1,w|+ 1)
N |Ew|+1 p−|Ew|
×(N − [α N ])(N − [α N ]− 1) . . . (N − [α N ]− |V2,w|+1)
)
=
∑
[w]∈C(N)
k
θ̂([w]). (3.4)
In the second line of (3.4), for every class [w] we choose an arbitrary walk w
corresponding to this class of equivalence.
3.2. Minimal and Essential Walks
The class of walks [w] of C(N)
k has at most k vertices. Hence, C(1)
k ⊂ C(2)
k ⊂
. . . ⊂ C(i)
k ⊂ . . . C(k min(α,1−α)−1)
k = C(k min(α,1−α)−1+1)
k = . . .. It is natural to
denote Ck = C(min(α,1−α)−1)
k . Then (3.4) can be written as
m
(p)
k = lim
N→∞
∑
[w]∈Ck
ξ(N,α)(w)α|V1,w|(1− α)|Vw|−|V1,w|
(
N |Vw|−|Ew|−1
∏
e∈Ew
Xnw(e)
p−1
)
.
(3.5)
The set Ck is finite. Regarding this and (3.5), we conclude that the class [w] has
non-vanishing contribution if |Vw| − |Ew| − 1≥0 and w is a bipartite walk on the
complete bipartite graph KIα,N ,1,N\Iα,N
. But for each simple connected graph
G = (V,E) |Vw|≤ |Ew|+ 1, and the equality takes place if and only if the graph
G is a tree.
It is convenient to use the notion of a minimal walk.
Definition 1. The walk w is a minimal walk if w1 (the root of walk) has the
number 1 and the number of every new vertex is equal to the number of all already
passed vertices plus 1.
Let us denote the set of all minimal walks of W
(N)
k by I(N)
k .
E x a m p l e 1. The sequences (1,2,1,2,3,1,4,2,1,4,3,1) and (1,2,3,2,4,2,3,2,1,2,
4,1,5,1) represent the minimal walks.
246 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
Definition 2. The minimal walk w that has a tree as a skeleton is an essential
walk.
Let us denote the set of all essential walks of W
(N)
k by E(N)
k . Therefore we
can rewrite (3.5) in the form
m
(p)
k =
∑
w∈Ek
(θ1(w) + θ2(w)) , (3.6)
where
θ1(w) = αβ(w)(1− α)|Vw|−β(w)
( ∏
e∈Ew
(
pXnw(e)
)
)
,
θ2(w) = (1− α)β(w)α|Vw|−β(w)
( ∏
e∈Ew
(
pXnw(e)
)
)
,
where β(w) is the number of vertices v such that the distance between v and
the first vertex w1 is even. The number of passages of each edge e belonging to
the essential walk w is even. Hence, the limiting mathematical expectation m
(p)
k
depends only on the even moments of the random variable a. It is clear that the
limiting mathematical expectation lim
N→∞
M
(N,p,α)
2s+1 is equal to zero.
3.3. First Edge Decomposition of Essential Walks
Let us start with necessary definitions. The first vertex w1 = 1 of the essential
walk w is called the root of the walk. We denote it by ρ. Let us denote the second
vertex w2 = 2 of the essential walk w by ν. We denote by l the half of walk’s
length, and by r the number of steps of w starting from the root ρ. In this
subsection, we derive the recurrent relations by splitting the walk (or the tree)
into two parts. To describe this procedure, it is convenient to consider the set of
essential walks of length 2l such that they have r steps starting from the root ρ.
We denote this set by Λ(l, r). One can see that this description is exact in the
sense that it is minimal and gives a complete description of the walks we need.
Denote by S(1)(l, r), S(2)(l, r) the sum of contributions of the walk of Λ(l, r) with
the weights θ1 and θ2, respectively. Let us remove the edge (ρ, ν) = (1, 2) from
Gw and denote the obtained graph by Ĝw. The graph Ĝw has two components.
Denote the component that contains the vertex ν by G2, and the component
containing the root ρ by G1. Add the edge (ρ, ν) to the edge set of the tree
G2. Denote the result by Ĝ2. Denote by u the half of the walk’s length over the
tree G2, and by f the number of steps (ρ, ν) in the walk w. It is clear that the
following inequalities hold for all essential walks (except the walk of length zero):
1 ≤ f ≤ r, r + u ≤ l. Let us denote by Λ1(l, r, u, f) the set of essential walks
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 247
V. Vengerovsky
with the fixed parameters l, r, u, f , and by S
(1)
1 (l, r, u, f) (S(2)
1 (l, r, u, f)), the
sum of contributions of the walks of Λ1(l, r, u, f) with the weight θ1 (θ2). Denote
by Λ2(l, r) the set of essential walks of Λ(l, r) such that their skeleton has only
one edge attached to the root ρ. We also denote by S
(1)
2 (l, r) and S
(2)
2 (l, r) the
sum of the weights θ1 and θ2 of the walk of Λ2(l, r), respectively. Now we can
formulate the first lemma of decomposition. It allows us to express S(1), S(2) as
the functions of S(1), S(2), S
(1)
2 , S
(2)
2 .
Lemma 1 (First decomposition lemma). The following relations hold:
S(1)(l, r)=
r∑
f=1
l−r∑
u=0
S
(1)
1 (l, r, u, f), (3.7)
S(2)(l, r)=
r∑
f=1
l−r∑
u=0
S
(2)
1 (l, r, u, f), (3.8)
where
S
(1)
1 (l, r, u, f)=α−1
(
r − 1
f − 1
)
S
(1)
2 (f + u, f) S(1)(l − u− f, r − f), (3.9)
S
(2)
1 (l, r, u, f)=(1− α)−1
(
r − 1
f − 1
)
S
(2)
2 (f + u, f) S(2)(l − u− f, r − f). (3.10)
P r o o f. The first two equalities are obvious. The last two equalities follow
from the bijection F ,
Λ1(l, r, u, f)
bij→ Λ2(f + u, f)× Λ(l − u− f, r − f)×Θ1(r, f), (3.11)
where Θ1(r, f) is the set of sequences of 0 and 1 of the length r such that there
are exactly f symbols 1 in the sequence, and the first symbol is 1.
Let us construct the mapping F . Regarding one particular essential walk
w of Λ1(l, r, u, f), we consider the first edge e1 of the graph Gw and divide w
into two parts, the left and the right ones with respect to the edge e1. Then we
add a special code that determines the transitions from the left part to the right
one and back through the root ρ. Obviously these two parts are walks, but not
necessary minimal walks. Then we minimize these walks. This decomposition
is constructed by the following algorithm. We run over w and simultaneously
draw the left part, the right part, and the code. If the current step belongs to
Gl, we add it to the first part, otherwise we add this step to the second part.
The code is constructed as follows. Each time the walk leaves the root, the
sequence is enlarged by one symbol. If the current step is ρ → ν, then this
248 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
symbol is ”0”, otherwise this symbol is ”1”. It is clear that the first element of
the sequence is ”1”, the number of signs ”1” is equal to f , and the full length of
the sequence is r. Now we minimize the left and the right parts. Thus, we have
constructed the decomposition of the essential walk w and the mapping F . The
weight θ1(w)(θ2(w)) of the essential walk is multiplicative with respect to the
edges and vertices. In the factors S
(1)
2 (f + u, f), S(1)(l − u− f, r − f), we twice
count the multiplier corresponding to the root, so we need to add the factor α−1
to (3.9).
E x a m p l e 2. For w = (1, 2, 1, 2, 3, 2, 1, 4, 1, 2, 5, 2, 1, 4, 6, 4, 1, 2, 5, 2, 3, 2, 3,
2, 1, 4, 1) the left part, the right one, and the code are (1, 2, 1, 2, 3, 2, 1, 2, 4, 2, 1, 2, 4,
2, 3, 2, 3, 2, 1), (1, 2, 1, 2, 3, 2, 1, 2, 1), (1, 1, 0, 1, 0, 1, 0), respectively.
Let us denote the left part by (w(f)) and the right part by (w(s)). These parts
are walks with the root ρ. For each edge e in the tree Ĝ2 the number of passages
of e of the essential walk w is equal to the corresponding number of passages
of e of the left part (w(f)). Also, for each edge e belonging to the tree G1 the
number of passages of e of the essential walk w is equal to the corresponding
number of passages of e of the right part (w(s)). The weight of the essential walk
is multiplicative with respect to the edges. Then the weight of the essential walk
w is equal to the product of the weights of left and right parts. The walk of zero
length has a unit weight. Combining this with (3.11), we obtain
S
(1)
1 (l, r, u, f) = α−1 |Θ1(r, f)|S(1)
2 (f + u, f)S(1)(l − u− f, r − f), (3.12)
S
(2)
1 (l, r, u, f) = (1− α)−1 |Θ1(r, f)|S(2)
2 (f + u, f)S(2)(l − u− f, r − f). (3.13)
Taking into account that |Θ1(r, f)| =
(
r−1
f−1
)
, we derive (3.9), (3.10) from
(3.12), (3.13).
Now let us prove that for any given elements w(f) of Λ2(f + u, f), w(s) of
Λ(l − u − f, r − f), and the sequence θ ∈ Θ1(r, f), one can construct one and
only one element w of Λ1(l, r, u, f). To do this, we use the following gathering
algorithm. We go along either w(f) or w(s) and simultaneously draw the walk
w. The switch from w(f) to w(s) and back is governed by the code sequence
θ. In fact, this procedure is inverse to the decomposition procedure described
above up to the fact that w(s) is minimal. This difficulty can be easily resolved,
for example, by coloring the vertices of w(f) and w(s) in red and blue colors,
respectively. Certainly, the common root of w(f) and w(s) has only one color. To
illustrate the gathering procedures we give the following example.
E x a m p l e 3. For w(f) = (1, 2, 1, 2, 3, 2, 1, 2, 4, 2, 1, 2, 4, 2, 3, 2, 3, 2, 1),
w(s) = (1, 2, 1, 2, 3, 2, 1, 2, 1), θ = (1, 1, 0, 1, 0, 1, 0) the gathering procedure gives
w = (1, 2, 1, 2, 3, 2, 1, 4, 1, 2, 5, 2, 1, 4, 6, 4, 1, 2, 5, 2, 3, 2, 3, 2, 1, 4, 1).
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 249
V. Vengerovsky
It is clear that the decomposition and gathering are injective mappings. Their
domains are finite sets, and therefore the corresponding mapping (3.11) is bijec-
tive. This completes the proof of Lemma 1.
To formulate Lemma 2, let us give necessary definitions. We denote by v the
number of steps starting from the vertex ν excepting the steps ν → ρ, and by
Λ3(u + f, f, v) the set of essential walks of Λ2(u + f, f) with the fixed parameter
v. We also denote by S
(1)
3 (u + f, f, v) (S(2)
3 (u + f, f, v)) the sum of the weights
θ1 (θ2) of the walks of Λ3(u+ f, f, v). Let us denote by G1,2 the graph consisting
of only one edge (ρ, ν), and by Λ4(f) the set of essential walks of length 2f such
that their skeleton coincides with the graph G1,2. It is clear that Λ4(f) consists of
only one walk (1,2,1,2,. . . ,2,1) of the weight X2f
p−1 . Lemma 1 allows us to express
S(1), S(2) as the functions of S(1)
2 , S
(2)
2 , S(1), S(2). By the next lemma, S
(1)
2 , S
(2)
2
can be expressed as the functions of S(1), S(2). Thus, two lemmas allow us to
express S(1), S(2) as the functions of S(1), S(2).
Lemma 2 (Second decomposition lemma). We have:
S
(1)
2 (f + u, f) =
u∑
v=0
S
(1)
3 (f + u, f, v), (3.14)
S
(2)
2 (f + u, f) =
u∑
v=0
S
(2)
3 (f + u, f, v), (3.15)
S
(1)
3 (f + u, f, v)=α
(
f + v − 1
f − 1
)
X2f
p−1
S(2)(u, v), (3.16)
S
(2)
3 (f + u, f, v)=(1− α)
(
f + v − 1
f − 1
)
X2f
p−1
S(1)(u, v). (3.17)
The first two equalities are trivial, the second two follow from the bijection
Λ3(f + u, f, v)
bij→ Λ(u, v)× Λ4(f)×Θ2(f + v, f), (3.18)
where Θ2(f + v, f) is the set of sequences of 0 and 1 of the length f +v such that
there are exactly f symbols 1 in the sequence and its last symbol is 1. The proof
is analogous to that of the first decomposition lemma. The factor α in (3.16) is
a contribution of the root in the weight.
Combining these two decomposition lemmas and changing the order of sum-
mation, we get recurrent relations (2.7), (2.8) with initial conditions (2.9).
Let us denote the set of double closed walks of k and m steps over 1, N
by D(N)
k,m
def≡ W
(N)
k × W
(N)
m . For dw = (w(1), w(2)) ∈ D(N)
k,m, we denote a(dw) =
250 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
a(w(1))a(w(2)), d(N,p)(dw) = d(N,p)(w(1))d(N,p)(w(2)), ξ(N,α)(dw) = ξ(N,α)(w(1))
×ξ(N,α)(w(2)).
Then we obtain
C
(N,p,α)
k,m =
1
N2
∑
dw=(w(1),w(2))∈W
(N)
k,m
ξ(N,α)(dw)
{
Ea(dw) Ed(N,p)(dw)
−Ea(w(1)) Ed(N,p)(w(1)) Ea(w(2)) Ed(N,p)(w(2))
}
. (3.19)
For the closed double walks dw = (w(1), w(2))∈D(N)
k,m, we denote ndw(f, g) =
nw(1)(f, g)+nw(2)(f, g). Introduce a simple non-oriented graph Gdw =Gw(1)∪Gw(2)
for the double walk dw = (w(1), w(2))∈D(N)
k,m, i.e., Vdw = Vw(1)∪Vw(2) and Edw =
Ew(1)∪Ew(2) . Then, we can rewrite 3.19 in the following form:
C
(N,p,α)
k,m =
1
N2
∑
dw=(w(1),w(2))∈W
(N)
k,m
ξ(N,α)(dw)
∏
e∈Edw
Eandw(e)
e E
[
d(N,p)
e
]ndw(e)
−
∏
e∈Ew(1)
Ea
n
w(1)(e)
e E
[
d(N,p)
e
]n
w(1) (e) ∏
e∈Ew(1)
Ea
n
w(2)(e)
e E
[
d(N,p)
e
]n
w(2)(e)
=
1
N2
∑
dw=(w(1),w(2))∈W
(N)
k,m
ξ(N,α)(dw)
( p
N
)|Edw| ∏
e∈Edw
Xndw(e)
−
( p
N
)|E
w(1) |+|Ew(2) | ∏
e∈E
w(1)
Xn
w(1) (e)
∏
e∈E
w(2)
Xn
w(2)(e)
. (3.20)
To perform the limiting transition, N →∞, it is natural to divide D(N)
k into
classes of equivalence. The double walks dw = (w(1), w(2)) and du = (u(1), u(2))
from D(N)
k,m are equivalent if and only if their first walks are equivalent and their
second walks are equivalent:
dw ∼ du ⇔
(
w(1) ∼ u(1) ∧ w(2) ∼ u(2)
)
.
Let us denote by [dw] the class of equivalence of the double walk dw, and by
F (N)
k the set of these classes. Then (3.20) can be written in the following form:
C
(N,p,α)
k,m =
1
N2
∑
[dw]∈F(N)
k,m
ξ(N,α)(dw)
{
p|Edw|[α N ]([α N ]− 1) . . . ([α N ]− |V1,w(1) |+ 1)
N |Edw|
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 251
V. Vengerovsky
×[α N ]([α N ]− 1) . . . ([α N ]− |V1,w(2) |+ 1)
×(N − [α N ])(N − [α N ]− 1) . . . (N − [α N ]− |V2,w(1) |+ 1)
×(N − [α N ])(N − [α N ]− 1) . . . (N − [α N ]− |V2,w(2) |+ 1)
×
∏
e∈Edw
Xndw(e)−
p|Ew(1) |+|Ew(2) |−|Edw|
N |E
w(1) |+|Ew(2) |−|Edw|
∏
e∈E
w(1)
Xn
w(1)(e)
∏
e∈E
w(2)
Xn
w(2)(e)
. (3.21)
Let us define a formal order of the passes for the double walk dw = (w(1), w(2))∈
D(N)
k,m:
dwi =
{
w
(1)
i , if 1 ≤ i ≤ k,
w
(2)
i−k, if k + 1 ≤ i ≤ k + m.
Let us denote the set of all minimal double walks of D(N)
k,m by G(N)
k,m. Then we
obtain
N C
(N,p,α)
k,m =
∑
w∈Gk,m
γ(dw) lim
N→∞
N |Vdw|−|Edw|−1
p−|Edw|
∏
e∈Edw
Xndw(e)
− pc(dw)
N c(dw)
∏
e∈E
w(1)
Xn
w(1)(e)
∏
e∈E
w(2)
Xn
w(2)(e)
, (3.22)
where c(dw) is the number of common edges of Gw(1) and Gw(2), i.e., c(dw) =
|Ew(1) |+ |Ew(2) | − |Edw|,
γ(dw) =
(
αβ(w(1))(1− α)|Vw(1) |−β(w(1)) + (1− α)β(w(1))α|Vw(1) |−β(w(1))
)
×
(
αβ(w(2))(1− α)|Vw(2) |−β(w(2)) + (1− α)β(w(2))α|Vw(2) |−β(w(2))
)
.
Gk,m is a finite set. Gdw has at most 2 connected components. But if Gdw has
exactly 2 connected components, then Vw(1) ∩ Vw(2) =∅ ⇒ Ew(1) ∩ Ew(2) =∅ ⇒
c(dw) = 0 ⇒
(∏
e∈Edw
Vndw(e) − pc(dw)
Nc(dw)
∏
e∈E
w(1)
Vn
w(1) (e)
∏
e∈E
w(2)
Vn
w(2) (e)
)
= 0.
Hence the contribution of such minimal double walks to N C
(N,p,α)
k,m is equal to 0.
Otherwise, Gdw is a connected graph and |Vw| − |Ew| − 1 ≤ 0. Thus (i) of
Theorem 2 is proved.
Let us define a cluster of an essential walk w as a set of non-oriented edges
incident to a given vertex v of Gw (v is a center of the cluster). Therefore
the cluster is a subgraph of the skeleton Gw. Also, let us define an ordered
cluster of the essential walk w as a cluster of the essential walk w with the
252 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
sequence of numbers nw(e0), nw(e1), . . . , nw(el), where {er}l
r=0 is a sequence of
edges of the cluster ordered by time of their first passing. We can derive from
two decomposition lemmas that the number of passes covering the ordered cluster
with numbers 2j, 2i1, 2i2, . . . 2il (s =
∑l
j=1 ij) is equal to
n(j; i1, i2, . . . , il) =
(
j + s− 1
j − 1
) s!
l∏
r=1
ir
s(s− i1)(s− i1 − i2) . . . il
l∏
r=1
ir!
. (3.23)
Indeed, the steps to the center of ordered cluster v are uniquely determined by
the choice of steps from the vertex v. We can choose the steps from v along the
edge e0 in
(
j+s−1
j−1
)
ways. After that we can choose the steps from v along the
edge e1 in
(
s−1
i1−1
)
ways. Then we can choose the steps from v along the edge e2 in(
s−i1−1
i2−1
)
ways, and so on. Thus, the number of the passes covering the ordered
cluster with numbers 2j, 2i1, 2i2, . . . 2il (s =
∑l
j=1 ij) is equal to
(
j + s− 1
j − 1
)(
s− 1
i1 − 1
)(
s− i1 − 1
i2 − 1
)
. . .
(
s− i1 − i2 − . . .− il−1 − 1
il − 1
)
=
(
j + s− 1
j − 1
)
× s! i1
s(s− i1)! i1!
(s− i1)! i2
(s− i1)(s− i1 − i2)! i2!
. . .
(s− i1 − i2 − . . .− il−1)! il
(s− i1 − i2 − . . .− il−1) 0! il!
. (3.24)
But it is evident that the numbers in (3.23) and (3.24) coincide.
Let us define the weight of the ordered cluster by
θ(j; i1, i2, . . . , il) = n(j; i1, i2, . . . , il)
l∏
r=1
(pX2ir). (3.25)
Combining (3.25) with (2.4) and estimating C1k
ke−k ≤ k! ≤ C2k
ke−k, we obtain
θ(j; i1, i2, . . . , il) ≤ 2jCs
3s
2s(1 + p)s. (3.26)
Let us define the ordered skeleton as a skeleton with all ordered clusters and a
chosen root. First we define the weight of the ordered skeleton as the number
of passes covering it multiplied by
∏
e∈Ew
(pXnw(e)). From (3.26), we get that
the weight of the ordered skeleton of essential walk w from Ek is not greater than
Ck
4 k2k(1+p)k. We can regard the ordered skeleton of essential walk as a half-plane
rooted tree in which for each edge there is a natural number assigned to it. To
calculate the number of all ordered skeletons corresponding to 2k-th moment, we
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 253
V. Vengerovsky
consider all appropriate half-plane rooted trees with i edges and all distributions
of k − i undistinguishable balls into i distinguishable boxes. It is seen that the
number of all ordered skeletons is not greater than
k∑
i=0
(
2i!
i!(i + 1)!
(
k − 1
i− 1
))
≤23k.
Thus (iii) of Theorem 2 is proved.
Acknowledgement. The author is grateful to the referee for valuable re-
marks.
References
[1] M. Bauer and O. Golinelli, Random Incidence Matrices: Spectral Density at Zero
Energy. Saclay preprint T00/087; cond-mat/0006472.
[2] B. Bollobas, Random Graphs. Acad. Press, 1985.
[3] M. Bauer and O. Golinelli, Random Incidence Matrices: Moments and Spectral
Density. — J. Stat. Phys. 103 (2001), 301–336.
[4] Fan R.K. Chung, Spectral Graph Theory. AMS, 1997.
[5] D.M. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs. Acad. Press, 1980.
[6] S.N. Evangelou, Quantum Percolation and the Anderson Transition in Dilute Sys-
tems. — Phys. Rev. B 27 (1983), 1397–1400.
[7] S.N. Evangelou and E.N. Economou, Spectral Density Singularities, Level Statistics,
and Localization in Sparse Random Matrices. — Phys. Rev. Lett. 68 (1992), 361–
364.
[8] S.N. Evangelou, A Numerical Study of Sparse Random Matrices. — J. Stat. Phys.
69 (1992), 361–383.
[9] Y.V. Fyodorov and A.D. Mirlin, Strong Eigenfunction Correlations Near the An-
derson Localization Transition. arXiv:cond-mat/9612218 v1
[10] Ch. Godzil and G. Royle, Algebraic Graph Theory. Springer–Verlag, New York,
2001.
[11] S. Janson, T. ÃLuczak, and A. Rucinski, Random Graphs. John Wiley & Sons, Inc.
New York, 2000.
[12] D. Jacobson, S.D. Miller, I. Rivin, and Z. Rudnick, Eigenvalue Spacing for Regular
Graphs. In: Emerging Applications of Number Theory. D.A. Hejhal et al. (Eds.),
Springer–Verlag, 1999.
[13] O. Khorunzhy, M. Shcherbina, and V. Vengerovsky, Eigenvalue Distribution of
Large Weighted Random Graphs. — J. Math. Phys. 45 (2004), No. 4, 1648–1672.
[14] O. Khorunzhy, B. Khoruzhenko, L. Pastur, and M. Shcherbina, The Large-n Limit
in Statistical Mechanics and Spectral Theory of Disordered Systems. Phase Tran-
sition and Critical Phenomena 15. Academic Press, 1992.
254 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2
Eigenvalue Distribution of a Large Weighted Bipartite Random Graph
[15] M.L. Mehta, Random Matrices. Academic Press, New York, 1991.
[16] A.D. Mirlin and Y.V. Fyodorov, Universality of the Level Correlation Function of
Sparce Random Matrices. — J. Phys. A Math. Jen. 24 (1991), 2273–2286.
[17] G.J. Rodgers and A.J. Bray, Density of States of a Sparse Random Matrix. — Phys.
Rev. B 37 (1988), 3557–3562.
[18] G.J. Rodgers and C. De Dominicis, Density of States of Sparse Random Matrices.
— J. Phys. A Math. Jen. 23 (1990), 1567–1566.
[19] E.P. Wigner, On the Distribution of the Roots of Certain Symmetric Matrices. —
Ann. Math. 67 (1958), 325–327.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 2 255
|