Fringe Trees for Random Trees With Given Vertex Degrees
Copyright policy )Fringe Trees for Random Trees With Given Vertex Degrees
ABSTRACTWe prove asymptotic normality for the number of fringe subtrees isomorphic to any given tree in uniformly random trees with given vertex degrees. As applications, we also prove corresponding results for random labeled trees with given vertex degrees, for random simply generated trees (or conditioned Galton–Watson trees), and for additive functionals. The key tool for our work is an extension to the multivariate setting of a theorem by Gao and Wormald (2004), which provides a way to show asymptotic normality by analyzing the behavior of sufficiently high factorial moments.
- University of Liverpool United Kingdom
- Leibniz Association Germany
- Uppsala University Sweden
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
- Uppsala universitet Sweden
Combinatorial probability, vertex degrees, toll functions, 60C05, 05C05, 60F05, Probability (math.PR), Random graphs (graph-theoretic aspects), simply generated trees, fringe subtrees, 510, 004, Trees, Conditioned Galton-Watson trees, uniformly random trees with given vertex degrees, Branching processes (Galton-Watson, birth-and-death, etc.), fringe trees, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), random trees, conditioned Galton-Watson trees, Mathematics - Probability, ddc: ddc:004
Combinatorial probability, vertex degrees, toll functions, 60C05, 05C05, 60F05, Probability (math.PR), Random graphs (graph-theoretic aspects), simply generated trees, fringe subtrees, 510, 004, Trees, Conditioned Galton-Watson trees, uniformly random trees with given vertex degrees, Branching processes (Galton-Watson, birth-and-death, etc.), fringe trees, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), random trees, conditioned Galton-Watson trees, Mathematics - Probability, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!