String Powers in Trees

Abstract

We investigate the asymptotic growth of the maximal number $\mbox{powers}\alpha(n)$ of different $\alpha$-powers (strings $w$ with a period $|w|/\alpha|w|$) in an edge-labeled unrooted tree of size $n$. The number of different powers in trees behaves much unlike in strings. In a previous work (CPM, 2012) it was proved that the number of different squares in a tree is $\mbox{powers}2(n)=\Theta(n^{4/3})$. We extend this result and analyze other powers. We show that there are phase-transition thresholds: 1. $\mbox{powers}\alpha(n)=\Theta(n^2)$ for $\alpha<2$; 2. $\mbox{powers}\alpha(n)=\Theta(n^{4/3})$ for $2\le \alpha<3$; 3. $\mbox{powers}\alpha(n)=O(n\log n)$ for $3\le\alpha<4$; 4. $\mbox{powers}\alpha(n)=\Theta(n)$ for $4\le\alpha$. The difficult case is the third point, which follows from the fact that the number of different cubes in a rooted tree is linear (in this case, only cubes passing through the root are counted).

Publication
CPM pp:284-294
Date