Intersections of randomly embedded sparse graphs are Poisson (Q1307020): Difference between revisions

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.