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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom