摘要:

AbstractWe give a randomized algorithm usingO(n7log2n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound isO(n6log4n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, andO(n5log4n) for centrally symmetric polytopes with a polynomial number of facets. We also give anO(n6logn) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34]on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley&Sons, I

ISSN:1042-9832    

DOI:10.1002/rsa.3240040402

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

年代:1993

数据来源: WILEY

摘要:

AbstractA classical result of Rödl (inGraphs, Hypergraphs and Block Systems, 1976, pp. 211 to 220) says that for any acyclic digraphDthere is a graphG=G(D)such that every acyclic orientation ofGcontains an induced copy ofD. A recent result of Rödl and Winkler (SIAM J. Discrete Math.,2: 402–406, 1989) implies that there is such a graphGof orderO(n3(logn)2), wheren= |D| is the order ofD. Here we show by probabilistic means that almost every graphGnof order [(4/9)n2n/2] has the property that every acyclic orientation ofGncontains an induced copy ofeveryacyclic digraph onnvertices. We also show that the order of any such graphGnhas to be greater than (1/10)n2n/2. Thus our results are essentially best possible. Moreover, we show that there are Paley graphs of orderO(n24n) having the property above. We also consider some problems raised by Cochand and Duchet (Irregularities of Partitions, Springer‐Verlag, Berlin, 1989, pp. 39–46.) on related topics. © 1993 John Wiley&S

ISSN:1042-9832    

DOI:10.1002/rsa.3240040403

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe prove nonconvergence and inseparability in the first‐order theory of random matchings and random graphs on an ordered set of points. © 1993 John Wiley&Sons, I

ISSN:1042-9832    

DOI:10.1002/rsa.3240040404

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

年代:1993

数据来源: WILEY

摘要:

AbstractAn approach for translating results on expected parameter values from subcritical Galton–Watson branching processes to simply generated random trees under the uniform model is outlined. As an auxiliary technique for asymptotic evaluations, we use Flajolet's and Odlyzko's transfer theorems. Some classical results on random trees are re‐derived by the mentioned approach, and some new results are presented. For example, the asymptotic behavior of linearly recursive tree parameters is described and the asymptotic probability of levelkto contain exactly one node is determined. © 1993 John Wiley&Sons,

ISSN:1042-9832    

DOI:10.1002/rsa.3240040405

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

年代:1993

数据来源: WILEY

摘要:

AbstractLetD2(n) be the probability space of 2‐regular digraphs onnvertices with the uniform measure. Asntends to infinity, the probability that the digraphs are 2‐connected tends to 1. © 1993 John Wiley&Sons,

ISSN:1042-9832    

DOI:10.1002/rsa.3240040406

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

年代:1993

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240040401

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

年代:1993

数据来源: WILEY