Description:

Title: Detecting correlation in uniform attachment trees

Abstract: We introduce and study a new model of correlated uniform attachment (UA) trees, where correlation is sprinkled throughout the time evolution of the process. In this model, two UA trees are grown in parallel from a single node labeled 0, and at the nth time step, a new node labeled n is added to each tree, with an edge between it and a uniformly chosen existing vertex in the respective tree. The two choices of attachment are correlated: With probability α, the edges attach to nodes with the same label in both trees, and with probability 1-α, the choices are made independently.

A fundamental question is how well the correlation can be detected from a single pair of unlabeled correlated UA trees. We show that this can be done with probability tending to one as the size of the trees goes to infinity, by constructing a statistic of the unlabeled trees that converges to the correlation parameter α.

The construction of our statistic relies on two key ideas. The first is that we can use a notion of centrality to identify subsets of vertices of each tree whose intersection has a sufficient number of common early vertices. The second idea is that across different scales, it is possible to approximately determine the labels of vertices that have attached to these early vertices, using the sizes of fringe subtrees. Our analysis includes quantitative bounds on the fraction of early vertices that remain most central, which may be of independent interest. Joint work with Johannes Bäumler, Miklós Rácz, and Anirudh Sridhar.