𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Large Trees in a Random Mapping Pattern

✍ Scribed by Lyuben Mutafchiev

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
224 KB
Volume
14
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

Mapping patterns may be represented by unlabelled directed graphs in which each point has outdegree one. We consider the uniform probability measure on the set of all mapping patterns on (n) points and derive the limiting distribution of the size of the largest tree as (n \rightarrow \infty). It is also shown that the asymptotic results concerning the structure of trees of a random mapping pattern coincide with those obtained earlier for the graphs of mappings on labelled point-sets.

πŸ“œ SIMILAR VOLUMES

Patterns in random binary search trees
Patterns in random binary search trees
✍ Philippe Flajolet; Xavier Gourdon; Conrado MartΓ­nez πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 243 KB

In a randomly grown binary search tree BST of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probabilit

Predecessors in a random mapping
Predecessors in a random mapping
✍ Jerzy Jaworski πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 208 KB πŸ‘ 1 views

A random mapping T ; q of a finite set V, V s 1, 2, . . . , n into itself assigns independently to each i g V its unique image j g V with probability q if i s j and with Ε½ . Ε½ . probability Ps 1 y q r n y 1 if i / j. The number of predecessors of elements from a given subset of V is studied. Exact r

Distribution of points by degree and orb
Distribution of points by degree and orbit size in a large random tree
✍ C. K. Bailey πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 383 KB

## Abstract Using generating functions and asymptotic techniques, the probability that in a large random tree a point is of degree __r__ and an orbit of size __s__ for __r__ ≀ 7 and __s__ ≀ 7 is calculated. For example, it is found that about 17% of the points of a random tree are fixed and have de

Diameter of random spanning trees in a g
Diameter of random spanning trees in a given graph
✍ Fan Chung; Paul Horn; L. Lu πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 144 KB πŸ‘ 1 views

## Abstract Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph __G__ is between and with high probability., w