๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Random minimal spanning tree and percolation on the N-cube

โœ Scribed by Mathew D. Penrose

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
251 KB
Volume
12
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

โœฆ Synopsis

The N-cube is a graph with 2 N vertices and N 2 Ny1 edges. Suppose indepen- dent uniform random edge weights are assigned and let T be the spanning tree of minimal ลฝ .

y 1 N ฯฑ y3 total weight. Then the weight of T is asymptotic to N 2 ร i as N ยช ฯฑ. Asymp-is1 totics are also given for the local structure of T and for the distribution of its kth largest edge weight, k fixed.

๐Ÿ“œ SIMILAR VOLUMES

Subcube Coverings of Random Spanning Sub
Subcube Coverings of Random Spanning Subgraphs of the n-Cube
โœ Karl Weber ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 896 KB

Let G(n, p ) denote the probability space consisting of all spanning subgraphs g of the n-cube En, and the probability is defined as ERDOS and SPENCER investigated the connectedness of such random graphs for fixed probability p , O<p<l (cf. [l]). I n this paper we study coverings of the vertex set

Stratified random walks on the n-cube
Stratified random walks on the n-cube
โœ F. R. K. Chung; R. L. Graham ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 226 KB ๐Ÿ‘ 1 views

In this paper we present a method for analyzing a general class of random ## ลฝ . walks on the n-cube and certain subgraphs of it . These walks all have the property that the transition probabilities depend only on the level of the point at which the walk is. For these walks, we derive sharp bound