A note on near‐optimal coloring of shift hypergraphs |
| |
| Authors: | David G. Harris Aravind Srinivasan |
| |
| Affiliation: | 1. Department of Applied Mathematics, University of Maryland, College Park, Maryland;2. Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland |
| |
| Abstract: | As shown in the original work on the Lovász Local Lemma due to Erd?s & Lovász (Infinite and Finite Sets, 1975), a basic application of the Local Lemma answers an infinitary coloring question of Strauss, showing that given any integer set S, the integers may be k‐colored so that S and all its translates meet every color. The quantitative bounds here were improved by Alon, Kriz & Nesetril (Studia Scientiarum Mathematicarum Hungarica, 1995). We obtain an asymptotically optimal bound in this note, using the technique of iteratively applying the Lovász Local Lemma in order to prune dependencies. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 53–56, 2016 |
| |
| Keywords: | Lovasz Local Lemma shift hypergraphs hypergraph coloring |
|
|
