On covering by translates of a set
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 t...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Journal article |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
2009
|
| _version_ | 1826273099626053632 |
|---|---|
| author | Bollobas, B Janson, S Riordan, O |
| author_facet | Bollobas, B Janson, S Riordan, O |
| author_sort | Bollobas, B |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T22:23:01Z |
| format | Journal article |
| id | oxford-uuid:55b6385b-e9d8-4c2c-8316-8b40c8d13a5f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:23:01Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | oxford-uuid:55b6385b-e9d8-4c2c-8316-8b40c8d13a5f2022-03-26T16:45:40ZOn covering by translates of a setJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:55b6385b-e9d8-4c2c-8316-8b40c8d13a5fEnglishSymplectic Elements at Oxford2009Bollobas, BJanson, SRiordan, OIn 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. |
| spellingShingle | Bollobas, B Janson, S Riordan, O On covering by translates of a set |
| title | On covering by translates of a set |
| title_full | On covering by translates of a set |
| title_fullStr | On covering by translates of a set |
| title_full_unstemmed | On covering by translates of a set |
| title_short | On covering by translates of a set |
| title_sort | on covering by translates of a set |
| work_keys_str_mv | AT bollobasb oncoveringbytranslatesofaset AT jansons oncoveringbytranslatesofaset AT riordano oncoveringbytranslatesofaset |