Intersections of randomly embedded sparse graphs are Poisson
This paper considers random embeddings of an \(m\)-vertex graph \(G\) into the complete graph \(K_{n}\) where \(m\leq n\). If \(V(G)=\{1,2,\ldots ,m\}\), by a random embedding of \(G\) into \(K_{n}\) is meant that one of the \((n)_{m}\) injections of an \(m\)-set into an \(n\)-set is chosen from the uniform distribution. The reviewer [Discrete Math. 169, No. 1-3, 283-286 (1997; Zbl 0873.05051)] has shown that the number of edges a randomly embedded graph \(G_{n}\) has in common with a random spanning tree of \(K_{n}\) is asymptotically Poisson when the degree of the graph is bounded. This can be interpreted in terms of random embeddings of pairs of graphs in \(K_{n}\). Theorem 1 of this paper discusses random embeddings of \(t\)-tuples of graphs giving sufficient conditions for the number of edges common to all \(t\) of the labellings to be asymptotically Poisson as \(n\rightarrow \infty \) (which are, in a sense, best possible). In Theorem 2 this theorem is used to extend the reviewer's result from graphs of bounded degree to those whose degrees may grow as fast as \(o(n\) log log \(n\)/ log \(n\)). The proof of Theorem 1 requires an inversion theorem for falling moments, which is proved in the paper.
- Random trees in a graph and trees in a random graph
- Poisson convergence of numbers of vertices of a given degree in random graphs
- An improved upper bound on the density of universal random graphs
- An improved upper bound on the density of universal random graphs
- scientific article; zbMATH DE number 3904623
- On the Maximum Degree of a Random Planar Graph
- scientific article; zbMATH DE number 747032
- On the number of subtrees for almost all graphs
- scientific article; zbMATH DE number 3891422
This page was built for publication: Intersections of randomly embedded sparse graphs are Poisson
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1307020)
