On covering by translates of a set

Details On covering by translates of a set On covering by translates of a set

2009-10-20

arxiv.org/abs/0910.3815v2

Random Structures and Algorithms 38 (2011), 33--67

Mathematics

Combinatorics

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

Scientific paper

10.1002/rsa.20346

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.

Affiliated with

Also associated with

No associations

Rating

On covering by translates of a set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On covering by translates of a set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On covering by translates of a set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-144360