An isoperimetric inequality for word overlap
Abstract
Let $A$ and $B$ be sets of words of length $n$ over some finite alphabet. Suppose that no suffix of a word in $A$ coincides with a prefix of a word in $B$. Then we show that the product of densities of $A$ and $B$ is upper bounded by $(1+o(1))/(en)$. This bound is asymptotically sharp.
Fields of Study & Subjects
Algorithms and Data Compression
semigroups and automata theory
Advanced Combinatorial Mathematics
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 23 February 2026
- Language
- EN
- Document type
- Preprint