The Eigenvalues of Very Sparse Random Symmetric Matrices

Let W _n be an n × n random symmetric sparse matrix with independent identically distributed entries such that the values 1 and 0 are taken with probabilities p/n and 1-p/n, respectively; here is independent of n. We show that the limit of the expected spectral distribution functions of W _n has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points , and 0 belong to this set.     

On Universal Representation of Random Graphs

It is shown that every probability measure on the interval [0, 1] gives rise to a unique infinite random graph g on vertices {v₁, v₂, . . .} and a sequence of random graphs gn on vertices {v₁, . . . , v_n} such that . In particular, for Bernoulli graphs with stable property Q, can be strengthened to: probability space (, F, P), set of infinite graphs G(Q) , F with property Q such that .AMS Subject Classification: 05C80, 05C62.     

The Flooding Time in Random Graphs

Based on our analysis of the hopcount of the shortest path between two arbitrary nodes in the class G _p (N) of random graphs, the corresponding flooding time is investigated. The flooding time T _N (p) is the minimum time needed to reach all other nodes from one node. We show that, after scaling, the flooding time T _N (p) converges in distribution to the two-fold convolution ^(2*) of the Gumbel distribution function (z)=exp (–e ^–z ), when the link density p _N satisfies Np _N /(log N)³ if N .     

随机环境中广义随机游动的灭绝概率

随机环境中广义随机游动(GRWRE)是随机环境中随机游动(RWRE)的推广．该文构造了非负整数集上的GRWRE,证明了这种模型的存在性,并计算了灭绝概率．     

Boundaries and Harmonic Functions for Random Walks with Random Transition Probabilities

The usual random walk on a group (homogeneous both in time and in space) is determined by a probability measure on the group. In a random walk with random transition probabilities this single measure is replaced with a stationary sequence of measures, so that the resulting (random) Markov chains are still space homogeneous, but no longer time homogeneous. We study various notions of measure theoretical boundaries associated with this model and establish an analogue of the Poisson formula for (random) bounded harmonic functions. Under natural conditions on transition probabilities we identify these boundaries for several classes of groups with hyperbolic properties and prove the boundary triviality (i.e., the absence of non-constant random bounded harmonic functions) for groups of subexponential growth, in particular, for nilpotent groups.     

Explicit Bounds for the Return Probability of Simple Random Walks

We give an exact computation of the second order term in the asymptotic expansion of the return probability, P_2n^d(0,0), of a simple random walk on the d-dimensional cubic lattice. We also give an explicit bound on the remainder. In particular, we show that P_2n^d(0,0) < 2 (d/4n)^d/2 where n M=M(d) is explicitly given.     

The Diameter of Sparse Random Graphs

We consider the diameter of a random graph G(n, p) for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of random graph G(n, p) is close to if np → ∞. Moreover if , then the diameter of G(n, p) is concentrated on two values. In general, if , the diameter is concentrated on at most 21/c₀ + 4 values. We also proved that the diameter of G(n, p) is almost surely equal to the diameter of its giant component if np > 3.6.     

随机环境中多维分枝链的增长率及灭绝概率

本文在随机环境中马氏链的框架下研究随机环境中多维分枝链(简记MBCRE)的极限性质,获得了MBCRE的母函数的一些性质,利用这些性质和随机矩阵乘积的弱收敛性证明了MBCRE中的条件均方收敛性与a．s．收敛性以及灭绝概率的估算等．这些结果是对Athrey与Karlin(1972)和Cohn(1989)的极限定理的推广．     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

三维随机SIERPINSKI地毯的相位和临界概率

本文用概率论的基本方法结合矩阵表示上的置换方法,证明了三维随机 Ｓｉｅｒｐｉｎｓｋｉ地毯随着保留概率从０到１变化,过程组态经历几个不同的相位,并求出各相位间的临界概率或给出其范围．     

广义稠密随机交集图的度分布(英文)

广义随机交集图是一类重要的随机图模型,它是E-R随机图的变种,被广泛用于复杂社会网络的研究中.本文研究了在顶点度的期望趋于无穷的情况下,广义随机交集图的度分布.我们对二项模型给出了中心极限定理,并且对一致模型给出了极限定理.     

Sparse Graphs which Decompose into Closed Trails of Arbitrary Lengths

A simple, connected even graph G with vertex set V(G) and edge set E(G) is said to be ADCT (Arbitrarily Decomposable into Closed Trails) if for any collection of positive integers x ₁, x ₂,...,x _m with and x _i ≥ 3 for 1 ≤ i ≤ m, there exists a decomposition of G into closed trails (circuits) of lengths x ₁, x ₂,...,x _m . In this note we construct an 8-regular ADCT graph on 6n vertices, for each each n ≥ 3. On the other hand, we also show that there are only finitely many 4-regular graphs which are ADCT. Received July 26, 2006. Final version received: March 5, 2008.     

几何随机图大连通分支覆盖面积及其在传感器网络中的应用

随机网络中的大连通分支能体现一个网络的连通情况,是几何随机图研究的-个热点,具有重要的理论意义和应用价值.本文利用渗流理论,研究了几何随机图大连通分支覆盖面积所具有的性质,并将理论结果应用到大型无线传感器网络中,研究了无线传感器网络覆盖的性质.研究结果表明,对于节点服从泊松分布的大型无线传感器网络,其大连通分支覆盖区域大小与总区域大小的比值趋于-个常数,且并估计出了2维空间中没有被大连通分支所覆盖的连通区域(本文称为空洞)的大小.这些结果为衡量无线传感器网络性能提供了理论基础,对实际布网和网络优化等具有一定的指导意义.     

Distance-2-Matchings of Random Graphs

In this paper we study the maximal size of a distance-2-matching in a random graph G _n;M , i.e., the probability space consisting of subgraphs of the complete graph over n vertices, K _n , having exactly M edges and uniform probability measure. A distance-2-matching in a graph Y, M ₂, is a set of Y-edges with the property that for any two elements every pair of their 4 incident vertices has Y-distance 2. Let M₂(Y) be the maximal size of a distance-2-matching in Y. Our main results are the derivation of a lower bound for M₂(Y) and a sharp concentration result for the random variable AMS Subject Classification: 05C80, 05C70.     

Ups and Downs of First Order Sentences on Random Graphs

whenever is a fixed positive irrational. This raises the question what zero-one valued functions on the positive irrationals arise as the limit probability of a first order sentence on these graphs. Here we prove two necessary conditions on these functions, a number-theoretic and a complexity condition. We hope to prove in a subsequent paper that these conditions together with two simpler and previously proved conditions are also sufficient and thus they constitute a characterization. Received October 2, 1998     

Random near-regular graphs and the node packing problem

Nemhauser and Trotter [12] proposed a certain easily-solved linear program as a relaxation of the node packing problem. They showed that any variables receiving integer values in an optimal solution to this linear program also take on the same values in an optimal solution to the (integer) node packing problem. Let π be the property of graphs defined as follows: a graph G has property π if and only if there is a unique optimal solution to the linear-relaxation problem, and this solution is completely fractional. If a graph G has property π then no information about the node packing problem on G is gained by solving the linear relaxation. We calculate the asymptotic probability that a certain type of ‘sparse’ random graph has property π, as the number of its nodes tends to infinity. Let m be a fixed positive integer, and consider the following random graph on the node set {1,2 …, n}). We join each node, j say, to exactly m other nodes chosen randomly with replacement, by edges oriented away from j; we denote by G_n(m) the undirected graph obtained by deleting all orientations and allowing all parallel edges to coalesce. We show that, as n → ∞,

$\text{P(G}{}_{\mathrm{n}}\text{(m)}\text{has property}\text{π)→}\text{0}\text{if}\text{m = 1,}\text{1}\text{if}\text{m ? 3,}$

and we conjecture that $\text{P(G}{}_{\mathrm{n}}\text{(2)}\text{has property}\text{π)→ (1–2e}{}^{\mathrm{?2}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$.     

On the Convergence of Probabilities of First-Order Sentences for Recursive Random Graph Models

Doklady Mathematics - We study first-order zero–one law and the first-order convergence law for two recursive random graph models, namely, the uniform and preferential attachment models. In...     

随机矩阵的平均极限矩阵的几个定理

本文引入了随机矩阵的平均极限矩阵的概念，并讨论它与原矩阵之间的关系，给出了几个很好的结果．