Local Image Of Random Mapping Graphs

Abstract: Given vertices set [n] := {1,2,…, n}. For every vertex i, we inde-pendently and randomly choose a vertex from [n], and join these two vertices with an oriental edge which has initial point i and end point j. Such graph composed of these vertices and these edges, is generally called random map-ping graph. In the paper, we investigate the limit property of the local image of a random mapping graph and its use as n goes to infinity.First we study the joined probability of m fixed vertices in a random graph. Hence we get its precise formula and its second order expansion. For example as n goes to infinity, the probability that m vertices are joined is increasing to (?),while the the probability that m vertices are mutually disjoined is decreasing to (?).The paper next describes [k]-local image of a random mapping graph and [k]-good graph. The [k]-local image of a mapping graph is a minimal graph which keeps the topological structure of [k]. Some mapping graphs's [k]-local images have simple topological structure: it is still a mapping graph but with 2k vertices and it has [k] as leaves and the rest k vertices as inner vertices whose indegree is two. We call these whose [k]-local images have simple structure [k]-good graphs. It is easily to find that as n goes infinity, the probability that a random mapping graph is [k]-good asymptotic to one. Furthermore, the limitation of local image of a random mapping graph is equiv-alent to a Markov chain, random birth process of graphs more precisely. The time sequence of the sizes of components(or tree) of the graphs constructed by random birth process is a (0, 1/2) -Chinese Restaurant Processor (1/2,1/2) -Chinese Restaurant Process). The limit property of its local image can reflect the whole property of a random mapping graph . This make us can estimate the number of vertices with a certain of property and the height of some ver-tices of a random mapping through its local image. By the fact that the limit property of its local image can reflect the whole property of a random mapping graph, we can easily draw out the conclusion that three kind of travels which are defined on a random mapping graph , Harris walk, Travels on the contour and Travels in depth-first order, weekly converge to the same process called Reflected Brown Bridge.At last we introduce (α,θ)-Chinese Restaurant Process. Suppose that there are n customers in a restaurant and they occupy the first k tables with n_i customers sitting around the i-th. table. Let the next customer be brought either to the i-th occupied table with probability (n_i-α)/(n +θ) or to the first empty table with probability (θ+ kα)/(n +θ). Such a random sequence is called (α,θ)-Chinese restaurant process. We get asymptotic moments of the size of the largest table as n large enough for each pair (α,θ). Applying the above result that The time sequence of the sizes of components of the graphs constructed by random birth process is a (0,1/2) -Chinese Restaurant Process and the result that the limit property of its local image can reflect the whole property of a random mapping graph, We directly get the asymptotic moments of the size of the largest component of a random mapping graph as n goes to infinity. Furthermore, we get its asymptotic distribution directly from the as-ymptotic moments. Similarly, we find the asymptotic moments of the size of the largest tree and its asymptotic distribution.4...