Bernoulli Trials of Fixed Parity,Random and Randomly Oriented Graphs

Suppose you can colour n biased coins with n colours, all coins having the same bias. It is forbidden to colour both sides of a coin with the same colour, but all other colourings are allowed. Let X be the number of different colours after a toss of the coins. We present a method to obtain an upper bound on a median of X. Our method is based on the analysis of the probability distribution of the number of vertices with even in-degree in graphs whose edges are given random orientations. Our analysis applies to the distribution of the number of vertices with odd degree in random sub-graphs of fixed graphs. It turns out that there are parity restrictions on the random variables that are under consideration. Hence, in order to present our result, we introduce a class of Bernoulli random variables whose total number of successes is of fixed parity and are closely related to Poisson trials conditional on the event that their outcomes have fixed parity.     

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 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.     

On Some Properties of Randomly Indexed Sequences of Random Elements

Let be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N _n ,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F _k ,k≥1} be a family of probability laws and let X be some random element defined on and taking values in (S,ρ). In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X _n,k ,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that , and moreover as  n→∞. Furthermore, we consider the speed of convergence to X as n→∞.      

On the Edge Reconstruction of Graphs Embedded in Surfaces II

In this paper, we prove the following theorems. (i) Let G bea graph of minimum degree 5. If G is embeddable in a surface and satisfies (–5)|V(G)|+6()0, then G is edge reconstructible.(ii) Any graph of minimum degree 4 that triangulates a surfaceis edge reconstructible. (iii) Any graph which triangulatesa surface of characteristic 0 is edge reconstructible.     

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.     

随机环境中随机指标分枝过程矩的渐近性

引入了随机环境中随机指标分枝过程模型,证明了该模型矩的渐近性。     

Edge Colorings of Embedded Graphs

 In his paper, we discuss under what conditions graphs embedded in a surface Σ will be class one. Received: August 14, 1997 Revised: April 15, 1998     

随机图的谱矩

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

The Minimum Stretch Spanning Tree Problem for Typical Graphs

Acta Mathematicae Applicatae Sinica, English Series - With applications in communication networks, the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the...     

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.     

Asymptotic Distribution of Extremes of Randomly Indexed Random Variables

Let {X _n} be a sequence of i.i.d. random variables and let {_k} be a sequence of random indexes. We study the problem of the existence of non-degenerated asymptotic distribution for min{X ₁,..., X _n}.     

嵌入曲面的特殊图的边染色

设图G是嵌入到欧拉示性数χ(∑)≥0的曲面上的图,χ′(G)和△(G)分别表示图G的边色数和最大度.将证明如果G满足以下条件:1)△(G)≥5;2)图中3-圈和4-圈不相邻;3)图G中没有5-圈的一次剖分,则有χ′(G)=△(G).     

随机映射图的局部图

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