Finding Adam

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.

Continue reading

Advertisements

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.

Continue reading