A Connection Between Unbordered Partial Words and Sparse Rulers

Abstract

<p><em>Partial words</em> are words that contain, in addition to letters, special symbols ♢ called <em>holes</em>. Two partial words a=a₀…a_n and b=b₀…b_n are <em>compatible</em> if, for all i, a_i=b_i or at least one of a_i,b_i is a hole. A partial word is <em>unbordered</em> if it does not have a proper nonempty prefix and a suffix that are compatible. Otherwise, the partial word is <em>bordered</em>.</p><p><br>A set R⊆{0,…,n} is called a <em>complete sparse ruler of length</em> n if, for all k∈{0,…,n}, there exists r,s∈R such that k=r−s. These are also known as <em>restricted difference bases</em>.<br><br>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 the 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, depending on the reported values of the minimal number of marks in a length-135 ruler. We have not verified this value.<br><br>We then study a two-dimensional generalization of these results. We adapt methods from the one-dimensional case to solve the correct asymptotic for the number of holes that an unbordered two-dimensional binary partial word can have.</p>