Abstract

An $(n,d)$-robust positioning sequence (RPS) is a binary sequence where every pair of length-$n$ subwords is distance $d$ apart. In this paper, we study the quantity $P(n,d)$, which denotes maximum length of an $(n,d)$-RPS, and provide tight estimates in the range $n/2 < d\le n$. First, we show that the usual Plotkin bound cannot be attained when certain divisibility conditions hold. Next, using the concept of differences, we construct an infinite family of RPSs that attain a modified Plotkin bound. Finally, except for 16 cases, we determine the {\em exact} values of $P(n,d)$ for $\delta(n) \le d\le n\le 50$, where $\delta(n)=\ceiling{n/2}$ if $n\not\equiv 0 \mod{4}$ and $\delta(n)=(n+2)/2$ if $n\not\equiv 0\mod{4}$


Presenters

Duc Tu Dao

Nanyang Technological University

Han Mao Kiah

Nanyang Technological University

Hengjia Wei

Ben-Gurion University of the Negev

Session Chair

Navin Kashyap

Indian Institute of Science