CLR cover
Previous problem

Problem 82: Number of Square Factors in Labelled Trees

Next problem

It is known that the number of (distinct) square factors in a given word is linear (see Problem 72). Unfortunately, the property does not hold for edge-labelled trees.

The problem shows a surprising lower bound based on relatively simple example trees.

Prove that an edge-labelled binary tree of size $n$ can contain $\Omega(n^{4/3})$ (distinct) square factors.
Consider comb trees.

References

  • M. Crochemore, C. S. Iliopoulos, T. Kociumaka, M. Kubica, J. Radoszewski, W. Rytter, W. Tyczynski, and T. Walen. The maximum number of squares in a tree. In J. Kärkkäinen and J. Stoye, editors, Combinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Helsinki, Finland, July 3-5, 2012. Proceedings, volume 7354 of LNCS, pages 27-40. Springer, 2012.