Tight bound for the skew Hamming set-pair problem

Abstract

Let $X$ be an alphabet, let $t\ge 0$ and $n\ge t+1$, and let $((a_i,b_i){)}_{i=1}^m$ be an ordered family of word pairs in $X^n$ satisfying $dist(a_i,b_i)\ge t+1$ for every $i$ and $dist(a_i,b_j)\le t$ whenever $i<j$. We prove the sharp bound $m\le 2^{t+1}$, thereby resolving a problem posed by Alon, Jin, and Sudakov. Our proof uses a linear-algebraic method based on a characteristic-two algebra, which may be of independent interest.