Tight bound for the skew Hamming set-pair problem

Abstract

Let $X$ be an alphabet, let $t\geq 0$ and $n\geq 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)\geq t+1$ for every $i$ and $dist(a_i,b_j)\leq t$ whenever $i<j$. We prove the sharp bound $m\leq 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.

Disclosure

“Declaration on the use of generative AI The authors used generative AI tools to assist in discussing proof strategies, checking proofs, and improving the exposition. The authors take full responsibility for the mathematical arguments, results, and conclusions, all of which were”

PDF page 6

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:58:41.696089Z

Structural counts