摘要:

AbstractSupposenboys andngirls rank each other at random. We show that any particular girl has at least (1/2 − ϵ) innand at most (1 + ϵ) inndifferent husbands in the set of all Gale/Shapley stable matchings defined by these rankings, with probability approaching 1 asn→ ∞, if ϵ is any positive constant. the proof emphasizes general methods that appear to be useful for the analysis of many other combinatorial al

ISSN:1042-9832    

DOI:10.1002/rsa.3240010102

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph modelKn, p, by fixing attention to a fixed time, and the modelKn, N, by studying it at the random time it contains exactlyNedges. in particular, we obtain the asymptotic distribution asn→ ∞ of the number of subgraphs isomorphic to a given graphG, both forKn, p(pfixed) andKn, N(N/(n2)→p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers ofn(the variance grows slower forKn, N; the powers ofnusually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not n

ISSN:1042-9832    

DOI:10.1002/rsa.3240010103

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe consider a natural parallel version of the classical greedy algorithm for finding a maximal independent set in a graph. This version was studied in Coppersmith, Raghavan, and Tompa and they conjecture there that its expected running time on random graphsof arbitrary edge density of O(logn). We prove that conjecture.

ISSN:1042-9832    

DOI:10.1002/rsa.3240010104

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn nearest neighbor random walk on ann‐dimensional cube a particle moves to one of its nearest neighbors (or stays fixed) with equal probability. the particle starts at 0. How long does it take to reach its stationary distribution? in fact, this occurs surprisingly rapidly. Previous analysis has shown that the total variation distance to stationarity is large if the number of stepsNis1/4nlogn. This paper derives an explicit expression for the variation distance asn→ ∞ in the transition regionN˜ 1/4nlogn. This permits the first careful evaluation of a cutoff phenomenon observed in a wide variety of Markov chains. the argument involves Fourier analysis to express the probability as a contour integral and saddle point approximation. the asymptotic results are in good agreement with numerical results fornas small

ISSN:1042-9832    

DOI:10.1002/rsa.3240010105

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn a randomn‐vertex digraph, each arc is present with probabilityp, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, whennis large andnpis equal to a constantcgreater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about Θ2nvertices, where Θ is the unique root in [0, 1] of the equation 1 −x−e−ex= 0. Nearly all the vertices outside the large strong component line in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected timeO(n).for all choices ofnandp, the expected execution time of the algorithm isO(w(n)(nlogn)4/3), wherew(n)is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω(n2)the algorithm presents the transitive closure in the compact form(A × B)UC, whereAandBare sets of vertices, andCis a

ISSN:1042-9832    

DOI:10.1002/rsa.3240010106

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn this article it is shown that for almost every random cube process the hitting time of a complete matching equals the hitting time of having minimal degree (at least) one and also the hitting time of connectedness. It follows from this that ift= (n+c+o(1))2n−2for some constantc, then the probability that a random subgraph of then‐cube having preciselytedges has a complete matching tends toe −

ISSN:1042-9832    

DOI:10.1002/rsa.3240010107

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe introduce an equivalence class of varied properties for hypergraphs. Any hypergraph possessing any one of these properties must of necessity possess them all. Since almost all random hypergraphs share these properties, we term these properties quasi‐random. With these results, it becomes quite easy to show that many natural explicit constructions result in hypergraphs which imitate random hypergraphs in a variety of way

ISSN:1042-9832    

DOI:10.1002/rsa.3240010108

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

年代:1990

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240010101

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

年代:1990

数据来源: WILEY