摘要:

AbstractWe prove that for everyr⩾ 2 there isC>0 such that ifpCn−1/2then almost surely everyr‐coloring of the edges of the binomial random graphK(n, p) results in a monochromatic triangle. © 1994 John Wiley&Son

ISSN:1042-9832    

DOI:10.1002/rsa.3240050202

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractFor every 1>δ>0 there exists ac=c(δ)>0 such that for every groupGof ordern, and for a setSofc(δ) lognrandom elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graphX(G, S)is at most (1 ‐ δ). This implies that almost every such a graph is an ϵ(δ)‐expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases. © 1994 John Wiley

ISSN:1042-9832    

DOI:10.1002/rsa.3240050203

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractWe initiate a study of random walks on undirected graphs with colored edges. In our model, a sequence of colors is specified before the walk begins, and it dictates the color of edge to be followed at each step. We give tight upper and lower bounds on the expected cover time of a random walk on an undirected graph with colored edges. We show that, in general, graphs with two colors have exponential expected cover time, and graphs with three or more colors have doubly‐exponential expected cover time. We also give polynomial bounds on the expected cover time in a number of interesting special cases. We described applications of our results to understanding the dominant eigenvectors of products and weighted averages of stochastic matrices, and to problems on time‐inhomogeneous Markov chains. © 1994 John Wiley&Sons,

ISSN:1042-9832    

DOI:10.1002/rsa.3240050204

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractCartesian trees are binary search trees in which the nodes exhibit the heap property according to a second (priority) key. If the search key and the priority key are independent, and the trees is built based onnindependent copies, Cartesian trees basically behave like ordinary random binary search trees. In this article, we analyze the expected behavior when the keys are dependent: in most cases, the expected search, insertion, and deletion times are Φ(√n). We indicate how these results can be used in the analysis of divide‐and‐conguer algorithms for maximal vectors and convex hulls. Finally, we look at distributions for which the expected time per operation grows likenaforaϵ[1/2, 1]. © 1994 John Wiley&S

ISSN:1042-9832    

DOI:10.1002/rsa.3240050205

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractThreshold probabilities for the existence in a random graph onnvertices of a graph isomorphic to a given graph of orderCnand average degree at least three are investigated. In particular it is proved that the random graphG(n, p) onnvertices with edge probability contains a square grid onEn/2 vertices. © 1994 John Wiley&Sons, Inc

ISSN:1042-9832    

DOI:10.1002/rsa.3240050206

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractA process of growing a random recursive treeTnis studied. The sequence {Tn} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height ofTnis asymptotic, with probability one, toclogn. In particular,c=e= 2.718 … for the uniform recursive tree, andc= (2γ)−1, where γe1+γ= 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a randomm‐ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union‐find tree, and our theorem on the height of the uniform recursive tree. © 1994 Joh

ISSN:1042-9832    

DOI:10.1002/rsa.3240050207

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractIn this article, we present an efficient and very simple unbiased estimator for the Permanent of square (0–1) matrices. As the main result, we prove that our estimator, even though its worst case behavior is provably very bad, runs in time polynomial in the size of the input matrix for almost all matrices. We also generalize our technique and apply it to another enumeration problem, that of counting Hamilton cycles in directed graphs. The ease with which this was done suggests that the basic technique may have wide applicability. © 1994 John Wiley&Sons, I

ISSN:1042-9832    

DOI:10.1002/rsa.3240050208

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractIn a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost allr‐regular graphs are hamiltonian for any fixedr⩾ 3, by an analysis of the distribution of 1‐factors in random regular graphs. Moreover, almost all such graphs arer‐edge‐colorable if they have an even number of vertices. Similarly, almost allr‐regular bipartite graphs are hamiltonian andr‐edge‐colorable for fixedr⩾ 3. © 1994 Jo

ISSN:1042-9832    

DOI:10.1002/rsa.3240050209

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240050201

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY