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

CREATORDmitrii Zakharov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-20143

Browse the full library · About the Tower of Babel