A note on near‐optimal coloring of shift hypergraphs1. Issue 1 (6th August 2014)

• Record Type: Journal Article
• Authors: Harris, David G.; Srinivasan, Aravind
• Is Part Of: Random structures & algorithms. Volume 48:Issue 1(2016)
• Page Start: 53
• Page End: 56
• Publication Date: 2014-08-06
• Subjects: Lovasz Local Lemma -- shift hypergraphs -- hypergraph coloring; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20565
• Languages: English
• ISSNs: 1042-9832

Abstract

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