The Maximum Number of Squares in a Tree

摘要

We show that the maximum number of different square substrings in unrooted labelled trees behaves much differently than in words. A substring in a tree corresponds (as its value) to a simple path. Let sq(n) be the maximum number of different square substrings in a tree of size n. We show that asymptotically sq(n) is strictly between linear and quadratic orders, for some constants c_1,c_2 > 0 we obtain: C_1n~(4/3) ≤ sq(n) ≤ c_2n~(4-3).