uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On Covering by Translates of a Set
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2011 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 38, no 1-2, 33-67 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we study the minimal number tau(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 ->infinity, then almost every k-subset of the cyclic group with order n comes close to the optimal efficiency.

Place, publisher, year, edition, pages
2011. Vol. 38, no 1-2, 33-67 p.
Keyword [en]
coverings, tilings
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-143657DOI: 10.1002/rsa.20346ISI: 000285313500002OAI: oai:DiVA.org:uu-143657DiVA: diva2:391032
Conference
14th International Conference on Random Structures and Algorithms Poznan, POLAND, AUG 03-07, 2009
Note
Conference: 14th International Conference on Random Structures and Algorithms in Poznan, POLAND, AUG 03-07, 2009Available from: 2011-01-24 Created: 2011-01-24 Last updated: 2012-02-16Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Analysis and Applied Mathematics
In the same journal
Random structures & algorithms (Print)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 366 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf