Studia Scientiarium Mathematicarum Hungarica 30. (1995)

1-2. szám - Alon N.-Kriz I.-Nešetril J.: how to color shift hypergraphs

Studio Scienttarum Mathematicarum Hungarica 30 (1995), 1-11 HOW TO COLOR SHIFT HYPERGRAPHS N. ÁLON, I. KRIZ and J. NEŐETRIL Abstract Let g(k) denote the minimum integer m so that for every set S of m integers there is a ^-coloring of the set of all integers so that every translate of S meets every color class. It is a well known consequence of the Local Lemma that g(k) is finite for all k. Here we present a new proof for this fact, that yields a very efficient parallel algorithm for finding, for a given set 5, a coloring as above. We also discuss the problem of finding colorings so that every translate of S has about the same number of points in each color. In addition, we prove that for large k (l + o(l))fc log k ^ g(k) ^ (3 + o(l))k log k. Introduction Straus (cf. [8]) raised the following problem: Is there a function g(k)(< oo) such that for every set S of at least g(k) integers there is a coloring of the integers by k colors so that every translate of S meets all the colors? This problem was solved by Erdős and Lovász [8], who proved that (1) g(k) < O(k\ogk). The proof of [8] is probabilistic and uses the Lovász Local Lemma, a result that has been used for tackling many other combinatorial problems in nu­merous subsequent papers. As remarked in [12] there is no known proof for the finiteness of f(k) that does not use the Local Lemma. Our first result in the present short paper is such a proof, namely a solution of Straus’ problem that does not apply the Local Lemma. Although our basic solution works only for sets S of cardinality at least 4k2 it has the advantage that it is more constructive than the original solution of [8], and yields very efficient deterministic and parallel algorithms for finding a coloring of the integers with the required properties. As is the case with 1991 Mathematics Subject Classification. Primary 05C65; Secondary 05C55. Key words and phrases. Hypergraph coloring, probabilistic methods, sum-free sets. Research supported in part by a United States Israel BSF Grant. 0081-6906/95/$ 4.00 ©1995 Akadémiai Kiadó, Budapest MAGYAR TUDOMÁNYOS AKADÉMIA könyvtara