Premium
A note on near‐optimal coloring of shift hypergraphs
Author(s) -
Harris David G.,
Srinivasan Aravind
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20565
Subject(s) - lemma (botany) , combinatorics , mathematics , integer (computer science) , set (abstract data type) , order (exchange) , hypergraph , colored , discrete mathematics , finite set , upper and lower bounds , computer science , ecology , mathematical analysis , materials science , poaceae , finance , economics , composite material , biology , programming language
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