String Powers in Trees

Abstract

We investigate the asymptotic growth of the maximal number $\mbox{powers}\alpha(n)$ofdifferent$\alpha$-powers(strings$w$withaperiod$|w|/\alpha|w|$)inanedge-labeledunrootedtreeofsize$n$.Thenumberofdifferentpowersintreesbehavesmuchunlikeinstrings.Inapreviouswork(CPM,2012)itwasprovedthatthenumberofdifferentsquaresinatreeis$\mbox{powers}2(n)=\Theta(n^{4/3})$.Weextendthisresultandanalyzeotherpowers.Weshowthattherearephase-transitionthresholds: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).