On covering by translates of a set
- 21 October 2010
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 38 (1-2) , 33-67
Abstract
In this paper we study the minimal number τ(S,G) 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, the worst‐case efficiency when S has k elements is of order 1/log k. We show that if n(k) grows at a suitable rate with k, then almost every k‐subset of any given group with order n comes close to this worst‐case bound. In contrast, if n(k) grows very rapidly, or if k is fixed and n →∞, then almost every k‐subset of the cyclic group with order n comes close to the optimal efficiency. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Covering and packing in ${\Bbb Z}^n$ and ${\Bbb R}^n$ , (I)Monatshefte für Mathematik, 2008
- Connectivity of random k-nearest-neighbour graphsAdvances in Applied Probability, 2005
- On the coverage of space by random setsAdvances in Applied Probability, 2004
- Complementary Sets of Finite SetsMonatshefte für Mathematik, 2003
- Tiling the Integers with Translates of One Finite SetJournal of Algebra, 1999
- The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]dAdvances in Applied Probability, 1997
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978
- Tesselation of integersJournal of Number Theory, 1977
- Complements of finite sets of integers.The Michigan Mathematical Journal, 1967
- The undecidability of the domino problemMemoirs of the American Mathematical Society, 1966