A Connection Between Unbordered Partial Words and Sparse Rulers

Partial words are words that contain, in addition to letters, special symbols called holes. Two partial words of a=a₀ aₙ and b=b₀ bₙ are compatible if for all i, aᵢ = bᵢ or at least one of aᵢ, bᵢ is a hole. A partial word is unbordered if it does not have a nonempty proper prefix and a suffix that are compatible. Otherwise the partial word is bordered. A set R ⊆ \0, , n\ is called a complete sparse ruler of lengthn if for all k ∈ \0, , n\ there exists r, s ∈ R such that $k = r - s$. These are also known as restricted difference bases. From the definitions it follows that the more holes a partial word has, the more likely it is to be bordered. By introducing a connection between unbordered partial words and sparse rulers, we improve bounds on the maximum number of holes an unbordered partial word can have over alphabets of sizes $4$ or greater. We also provide a counterexample for a previously reported theorem. We then study a two-dimensional generalization of these results. We adapt methods from one-dimensional case to solve the correct asymptotic for the number of holes an unbordered two-dimensional binary partial word can have. This generalization might invoke further research questions.