On the Rigidity of Sparse Random Graphs

A graph with a trivial automorphism group is said to be rigid. Wright proved (Acta Math 126(1) (1971), 1–9) that for a random graph is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for with positive probability is nontrivial. We show that in the sparser case , it holds whp that G's 2‐core is rigid. We conclude that for all p, a graph in is reconstructible whp. In addition this yields for a canonical labeling algorithm that almost surely runs in polynomial time with o(1) error rate. This extends the range for which such an algorithm is currently known (T. Czajka and G. Pandurangan, J Discrete Algorithms 6(1) (2008), 85–92).     

On the Escape Probability for a Left or Right Continuous Random Walk

A formula for the escape probability in a left or right continuous random walk is derived in a simple manner, under natural conditions.AMS Subject Classification: 60G50.     

On the Ascending Subgraph Decomposition Problem

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｐａｐｅｒ［１］,Ａｌａｖｉａｎｄｏｔｈｅｒｓｄｅｆｉｎｅｄｔｈｅｃｏｎｃｅｐｔｏｆａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ：Ｄｅｆｉｎｉｔｉｏｎ　ＬｅｔＧｂｅａｇｒａｐｈｏｆｐｏｓｉｔｉｖｅｓｉｚｅｑ,ａｎｄｌｅｔｎｂｅｔｈａｔｐｏｓｉｔｉｖｅｉｎｔｅｇｅｒｆｏｒｗｈｉｃｈｎ＋１２ｑ＜ｎ＋２２．ＴｈｅｎＧｉｓｓａｉｄｔｏｈａｖｅａｎａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＡＳＤ）ｉｆＧｃａｎｂｅｄｅｃｏｍｐｏｓｅｄ…     

Random graphons and a weak Positivstellensatz for graphs

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2‐variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory     

More on the Bipartite Decomposition of Random Graphs

For a graph , let denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G , , where is the maximum size of an independent set of G . Erd?s conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph , with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for , with high probability. We prove a stronger bound: there exists an absolute constant so that with high probability.     

一类无标度随机图的度序列

本文从-个新的角度对-类随机图的度序列进行了分析.证明了此模型度分布的存在性,得到了网络规模比较大的情况下度为七的节点所占比例数的表达式.此外,我们还将模型扩展到每个时间步增加边数为随机变量的情形,得到了类似的结论.     

随机映射图的连接概率

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

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.     

模糊概率随机变量

研究了第二类模糊随机变量——具有清晰事件、模糊概率的随机变量的数学描述。在区间概率的基础上,利用模糊分解定理给出了概率模糊数集是可行的条件,进一步给出了具有模糊概率的随机变量及模糊概率随机变量的模糊分布函数和模糊分布列的定义和性质。提出并证明了具有模糊概率运算封闭性的模糊概率分解定理。研究了模糊概率随机变量的模糊数学期望和模糊方差的定义和性质。所有关于模糊概率随机变量的数学描述都具有模糊概率运算的封闭性,这为完善模糊概率的运算方法打下了基础。     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009     

“卡边随机现象”的一种概率模型

郭正光、张鸿秀．“卡边随机现象”的一种概率模型．本文首次提出了生产实践中存在的所谓“卡边随机现象”这一概率模型,并且导出了其相应的数据所服从的概率分布函数和密度函数。同时,利用计算机描绘了当ｎ＝２,ｍ＝１的卡边密度曲线并给出了其相应的卡边分布表     

随机赔偿,随机折现下的保险概率模型及若干结果

本文首先构造了保险的随机过程模型，即随机赔偿和随机折现的双随机模型．运用测度扩张理论将赔偿过程发展为随机赔偿恻度，在模型的基本假定之下研究赔偿过程的性质，给出保险和年金的测度表示以及诸多精算公式．最后针对随机利率的Gauss过程模型得到Hoem模型随机赔偿测度的现值矩发展了［7］中的主要结果．     

The Stationary Distribution of a Continuous-Time Random Graph Process

ＴｈｅＳｔａｔｉｏｎａｒｙＤｉｓｔｒｉｂｕｔｉｏｎｏｆａＣｏｎｔｉｎｕｏｕｓ－ＴｉｍｅＲａｎｄｏｍＧｒａｐｈＰｒｏｃｅｓｓ韩东ＴｈｅＳｔａｔｉｏｎａｒｙＤｉｓｔｒｉｂｕｔｉｏｎｏｆａＣｏｎｔｉｎｕｏｕｓ－ＴｉｍｅＲａｎｄｏｍＧｒａｐｈＰｒｏｃｅｓｓ￥...     

Subgraph statistics in subcritical graph classes

Let H be a fixed graph and a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series‐parallel graphs. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 631–673, 2017     

对称随机变量部分和的概率不等式

在对称随机变量分布函数关于原点的值大于或等于二分之一的基础上,阐明对称随机变量的部分和仍是对称随机变量,进一步,给出关于对称随机变量序列部分和的概率不等式.     

一类随机图的演化

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

Random Probability Measures with Given Mean and Variance

This article describes several natural methods of constructing random probability measures with prescribed mean and variance, and focuses mainly on a technique which constructs a sequence of simple (purely discrete, finite number of atoms) distributions with the prescribed mean and with variances which increase to the desired variance. Basic properties of the construction are established, including conditions guaranteeing full support of the generated measures, and conditions guaranteeing that the final measure is discrete. Finally, applications of the construction method to optimization problems such as Plackett's Problem are mentioned, and to experimental determination of average-optimal solutions of certain control problems.     

关于随机算子方程的随机解

本文研究了随机算子方程（Ａ（ω，ｘ）＝μｘ，（ω，ｘ）∈Ω×Ｄ，μ１）的随机解，得到了若干新的结果，同时，我们推广了著名的Ａｌｔｍａｎ定理．     

最大2-正则诱导子图的长度

设G是2-连通图，c(G)是图G的最长诱导圈的长度，c′(G)是图G的最长诱导2-正则子图的长度。本文我们用图的特征值给出了c(G)和c′(G)的几个上界。