7 papers
Faster random walks via infrequent steering
Boris Bukh, Quentin Dubroff
Random walks on graphs can be slow. To speed them up, imagine that at each step instead of choosing the neighbor at random, there is a small probability that we can…
Covering large-dimensional Euclidean spaces by random translates of a given convex body
Boris Bukh, Jun Gao, Xizhi Liu +2
Determining the minimum density of a covering of by Euclidean unit balls as is a major open problem, with the best known results being the lower bound…
Most frequent subsequences in a word
Boris Bukh, Aleksandre Saatashvili
We prove that every -letter word over -letter alphabet contains some word as a subsequence in at least many ways, and that this is sharp as . F…
The Oddtown problem modulo a composite number
Boris Bukh, Ting-Wei Chao, Zeyu Zheng
A family of subsets of an -element set is called an -Oddtown if the sizes of all sets are not divisible by , but the sizes of pairwise intersections ar…
Maximal sets of a given diameter in Hamming cubes
Boris Bukh, Aleksandre Saatashvili
A subset of the Hamming cube over -letter alphabet is said to be -maximal if its diameter is , and adding any point increases the diameter. Our main result shows that each…
Convex polytopes in restricted point sets in
Boris Bukh, Zichao Dong
For a finite point set , denote by the ratio of the largest to the smallest distances between pairs of points in . Let be…