Title: The heavy path approach to Galton-Watson trees with an application to Apollonian networks,
Abstract: We study the heavy path decomposition of conditional Galton-Watson trees. In
a standard Galton-Watson tree conditional on its size $n$, we order all
children by their subtree sizes, from large (heavy) to small. A node is marked
if it is among the $k$ heaviest nodes among its siblings. Unmarked nodes and
their subtrees are removed, leaving only a tree of marked nodes, which we call
the $k$-heavy tree. We study various properties of these trees, including their
size and the maximal distance from any original node to the $k$-heavy tree. In
particular, under some moment condition, the $2$-heavy tree is with high
probability larger than $cn$ for some constant $c > 0$, and the maximal
distance from the $k$-heavy tree is $O(n^{1/(k+1)})$ in probability. As a
consequence, for uniformly random Apollonian networks of size $n$, the expected
size of the longest simple path is $\Omega(n)$.