Let sn be the number of strings consisting of the digits 0, 1, and 2 such that no substring is a square (a string concatenated with itself, e.g. 11 1212 102102 ...). We say sn is the number of squarefree words of length n over the ternary alphabet. Conjecturally, sn grows exponentially at a rate of about 1:317277n, the rate suggested by computational evidence. While known upper bounds are already relatively close to the conjectured rate, effective lower bounds are much more difficult to obtain. The best known lower bounds for sn, which are also exponential in n, have been obtained using what are known as Brinkhuis triple pairs. The task of finding Brinkhuis triple pairs is equivalent to the maximum hyperclique problem, which is NP-complete. However, clever heuristics can aid in algorithm development to give approximate solutions. Two algorithms are presented which give both random and deterministic solutions to this problem. Hypergraphs of high uniformity are great candidates for a randomized clique search. Additionally, a fast deterministic algorithm of linear complexity is developed which enables the discovery of a new lower bound on the asymptotic growth rate of the ternary squarefree numbers. The new lower bound on the number of n-letter ternary squarefree words is presented: 952n/53 &ap 1.1381531n, which improves the previous best result of 110n/42 &ap 1.1184191 n due to Xinyu Sun (2003).
展开▼
