PC Seminar: Apollonian Networks and k-heavy trees

Abstract: An Apollonian network is a iteratively generated planar graph that is in bijection with ternary trees. The problem of finding the longest path in an Apollonian network can be bounded by finding a large binary subtree of this ternary tree. A greedy approach from the top that chooses the 2 largest branches is called the 2-heavy tree.

The Apollonian network / ternary tree can be generated by various random models, e.g. conditioned Galton-Watson trees and split trees. For conditioned Galton-Watson trees, it has been shown that the 2-heavy tree has $O(n)$ nodes and therefore covers a non-vanishing fraction of the tree. In this talk, we focus on split trees, where we show that the 2-heavy tree has $\Theta(n^\beta)$ nodes, with some $\beta\in(0,1)$ given as a solution of a equation. With the contraction method, a limit distribution can also be found.

This is a seminar in our seminar series on Probability and Combinatorics (PC).