This post will outline the paper Finding Adam in random growing trees by Bubeck, Devroye, and Lugosi. The main question examined in this paper is simply stated and relatively unstudied: given a tree, which has been generated under some attachment model, find the first vertex. “First” here meaning oldest. Think about the spread of a rumor, or disease. In these situations, the resulting distribution is known, but the starting point is not.

# Category Archives: Level 3

# Triangle Removal Lemma

The triangle removal lemma shows that if a lot of edges must be removed to make a graph triangle-free, then there must have been a lot of triangles in the original graph. While this observation may not sound ground breaking, it is a very useful tool in combinatorics.