On covering by translates of a set

Abstract

In this paper we study the minimal number of translates of an arbitrary subset $S$ of a group $G$ needed to cover the group, and related notions of the efficiency of such coverings. We focus mainly on finite subsets in discrete groups, reviewing the classical results in this area, and generalizing them to a much broader context. For example, we show that while the worst-case efficiency when $S$ has $k$ elements is of order $1/\log k$, for $k$ fixed and $n$ large, almost every $k$-subset of any given $n$-element group covers $G$ with close to optimal efficiency.

41 pages; minor corrections; to appear in Random Structures and Algorithms

Cited by in corpus (6)

• Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings
• On the dimension of systems of algebraic difference equations
• Max-norm Ramsey Theory
• Packing Density of Sets With Only Two Nonmixed Gaps
• On some multiplicative properties of large difference sets
• Syndetic submeasures and partitions of $G$-spaces and groups