Intersections of randomly embedded sparse graphs are Poisson

Edward A. Bender ; E. Rodney Canfield

The electronic journal of combinatorics, Tome 6 (1999)

Résumé

Suppose that $t \ge 2$ is an integer, and randomly label $t$ graphs with the integers $1 \dots n$. We give sufficient conditions for the number of edges common to all $t$ of the labelings to be asymptotically Poisson as $n \to \infty$. We show by example that our theorem is, in a sense, best possible. For $G_n$ a sequence of graphs of bounded degree, each having at most $n$ vertices, Tomescu has shown that the number of spanning trees of $K_n$ having $k$ edges in common with $G_n$ is asymptotically $e^{-2s/n}(2s/n)^k/k! \times n^{n-2}$, where $s=s(n)$ is the number of edges in $G_n$. As an application of our Poisson-intersection theorem, we extend this result to the case in which maximum degree is only restricted to be ${\scriptstyle\cal O}(n \log\log n/\log n)$. We give an inversion theorem for falling moments, which we use to prove our Poisson-intersection theorem.

Détail

DOI : 10.37236/1468

Classification : 05C80, 05C05, 60C05, 05C30, 05A16, 60F05
Mots-clés : Poisson distribution, falling moments, spanning tree, complete graph, random embedding