Aleksandre Saatashvili

collaborators

2 papers

math.CO2025

Most frequent subsequences in a word

Boris Bukh, Aleksandre Saatashvili

We prove that every $n$ -letter word over $k$ -letter alphabet contains some word as a subsequence in at least $k^{n /4 k (1 + o (1))}$ many ways, and that this is sharp as $k \to \infty$ . F…

math.CO2025

Maximal sets of a given diameter in Hamming cubes

Boris Bukh, Aleksandre Saatashvili

A subset of the Hamming cube over $n$ -letter alphabet is said to be $d$ -maximal if its diameter is $d$ , and adding any point increases the diameter. Our main result shows that each…