随机映射图的局部图

讨论了当n趋向无穷大时,n个顶点的随机映射图的k-局部图收敛于随机生长过程时刻k的二叉图,这儿,k-局部图是随机映射图前k个顶点{1,2,…,k}所生成的最小图.在这种意义下,称随机映射图为渐近二叉的.     

随机映射图的连接概率

本文将计算随机映射图的给定顶点集的任意分类的连接概率及其极限性质,导出随机映射图的连通分支个数的分布与渐进分布．     

随机非线性单调映射

本文讨论随机非线性单调映射的基本性质,得到了关于强制型、扰动型及非强制型随机非线性单调映射的一些重要结果.本文所得结果,改进和推广了近期一些作者的工作.     

图映射的非游荡点和深度

设 $G$ 是一个图, $f:G\rightarrow G$ 是连续映射. 用$R(f)$和$\Omega (f)$分别表示$f$的回归点集和非游荡集. 设$\Omega_0 (f)=G$, $\Omega_n (f)=\Omega (f|_{\Omega_{n-1} (f)})$(对任$n\in {\N}$). 满足$\Omega_{m} (f)=\Omega_{m+1} (f)$的最小的$m\in {\N}\cup \{\infty\}$称为$f$的深度. 证明了$\Omega_2(f)=\overline{R(f)}$且 $f$的深度不超过2. 进一步, 还得到$f$的非游荡点的若干性质.     

随机弱内向映射的多个随机不动点定理

利用随机不动点指数理论及Banach常微分方程理论的随机结果,证明了关于随机弱内向映射一个随机三解定理.     

一类随机图的演化

定义一随机图过程:如果图Gt-1不是完全图时,图Gt分别以概率p和q加一个点和一条有向边;如果图Gt-1是完全图时,则以概率1加一个点．研究图Gt顶点和边的概率分布以及当顶点数固定时,边数的期望界值估计．     

层次结构中封闭子图的映射

在[3]中,我们就层次结构(BS)中,任意一个封闭子图G_(5)∈G_(5)真的扩展,建立了其边界映射的三原则,并在这些原则的基础上,构造了该映射的表达式。本文,进一步按映射三原则扩展这一映射表达式,并使之一般化。最后,我们还建立了封闭子图G_(5)映射定理,说明了如果映射存在则G_(5)的映射像ε(G_(5))就可以构造而得。     

图映射的渐近稳定集

设f为图G的连续自映射．在本文中，我们讨论了图映射的渐近稳定集，并给出了f的不动点为渐近稳定的一个充分必要条件．     

图闭模糊映射与闭模糊映射的关系研究

给出图闭模糊映射和闭模糊映射的关系:图闭模糊映射一定是闭模糊映射;若闭模糊映射是上半连续的则它也是图闭模糊映射.     

随机偏好连接图的中心极限定理

我们研究了一类具有随机顶点和边的随机连接图模型, 其中顶点的随机性由一个Poisson 点过程所决定, 边的随机性由一个概率连接函数所决定. 我们得到了带偏好的随机连接图模型的关于所有随机边的长度和的一个中心极限定理.     

Local Semicircle Law for Random Regular Graphs

We consider random d‐regular graphs on N vertices, with degree d at least (log N)⁴. We prove that the Green's function of the adjacency matrix and the Stieltjes transform of its empirical spectral measure are well approximated by Wigner's semicircle law, down to the optimal scale given by the typical eigenvalue spacing (up to a logarithmic correction). Aside from well‐known consequences for the local eigenvalue distribution, this result implies the complete (isotropic) delocalization of all eigenvectors and a probabilistic version of quantum unique ergodicity.© 2017 Wiley Periodicals, Inc.     

Local Limit Theorems for Sequences of Simple Random Walks on Graphs

In this article, local limit theorems for sequences of simple random walks on graphs are established. The results formulated are motivated by a variety of random graph models, and explanations are provided as to how they apply to supercritical percolation clusters, graph trees converging to the continuum random tree and the homogenisation problem for nested fractals. A subsequential local limit theorem for the simple random walks on generalised Sierpinski carpet graphs is also presented.      

Generating Random Regular Graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n^1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. * Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

随机图的谱矩

简单图G的k阶谱矩定义为G的特征值的k阶幂之和,记为Mk(G).应用概率和代数的方法,对于几乎所有的图G,本文给出Mk(G)的一个精确估计.此外,对于几乎所有的多部图G,本文给出了Mk(G)的上界和下界.     

Random Matchings in Regular Graphs

d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x. We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) : Theorem. For any d-regular graph G, (a) , so that , (b) , where the rates of convergence depend only on d. Received: April 12, 1996     

Random Motion on Simple Graphs

Consider a stochastic process that lives on n-semiaxes joined at the origin. On each ray it behaves as one dimensional Brownian Motion and at the origin it chooses a ray uniformly at random (Kirchhoff condition). The principal results are the computation of the exit probabilities and certain other probabilistic quantities regarding exit and occupation times.