An isoperimetric inequality for word overlap
Dmitrii Zakharov · 2026
Read An isoperimetric inequality for word overlap by Dmitrii Zakharov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-20143.txt.
Description
Take two sets of words, all of the same length, over a finite alphabet. Suppose no suffix of a word in the first set matches a prefix of a word in the second set. How large can the two sets both be? A 2026 arXiv paper by Dmitrii Zakharov, working alone, answers with an isoperimetric inequality for word overlap.
The paper shows the product of the two sets' densities is upper bounded by about one over e times n, where n is the word length, with a small vanishing correction. The bound is asymptotically sharp, meaning no substantially stronger universal bound of this form is possible. Readers gain a clean quantitative limit on how much two word sets can overlap in this suffix-prefix sense, and a proof that the limit cannot be improved in general.
Catalog record
| CREATOR | Dmitrii Zakharov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 14 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-20143