Studia Scientiarium Mathematicarum Hungarica 30. (1995)

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

2 N. ÁLON, I. KRIZ and J. NESETRIL many applications of the Local Lemma, the proof in [8] supplies neither a randomized nor a deterministic polynomial time algorithm for finding, given a set 5 of a sufficiently large cardinality, a fc-coloring so that each translate of S meets every color. The recent technique of J. Beck [5] and its modification in [1] that supply efficient sequential and parallel deterministic algorithms for various applications of the Local Lemma do not seem to apply directly to the problem of Straus mentioned above, even when the cardinality of S is much larger than Q(k\ogk). Note that here the length of the input is the number of bits in the representation of 5 whereas it is not even clear if the output can be represented with a finite number of bits, as the output is a k-coloring of the infinite set of integers. Our technique here yields a very efficient parallel algorithm that pro­duces, for a given set S of at least 4k2 integers a k-coloring of the integers so that every translate of S meets every color class. In fact, the required coloring can be found in constant time in the standard model for parallel computation known as a CRCW PRAM with a polynomial number of par­allel processors. (See, e.g., [11] for the exact definition of a CRCW PRAM; we assume that each processor is capable of adding, comparing, multiplying or dividing numbers of size as that of the members of 5 in constant time.) Since the required k-coloring is a coloring of an infinite set we agree that the k-coloring is produced successfully if it can be described by a polynomial number of bits that enable us, given any integer x, to compute the color of x efficiently; in our case this will be done by a constant number of modular additions and multiplications. The basic approach can be combined with the technique in [5] and yield efficient sequential coloring algorithms even if S has only ck log k elements for some (large) constant c. Still, we believe that the most interesting consequence of the argument is the new method for solving Straus’ original problem. Another result we prove here is the fact that the estimate in (1) is sharp. In order to formulate our results and proofs in a more concise form we introduce two definitions. For a set of integers 5, let H — H(5) denote the infinite hypergraph whose set of vertices is the set Z of all integers and whose set of edges is the set of all translates of 5, i.e., the set {x + S: x € Z}. We call H the shift hypergraph of 5. A k-coloring c : Z >-* {1,2,... , k} is called good (for H), if every edge of H meets every color class, i.e., if for every i, 1 = * = ^ and for every integer x there is an s € S so that c(x + s) — i. In this notation, our two main results are the following. Theorem 1.1. Let S be a set of at least 4k2 integers. Then there exists a good k-coloring c for the shift hypergraph H(S). Such a coloring can be found in constant time, using a polynomial number of parallel processors on a CRCW PRAM. In addition, there exists a positive constant c such that for every set S of at least ck log k integers one can find a good k-coloring for the shift hypergraph H (5) in (sequential) polynomial time. Tehorem 1.2. There exists an absolute positive Constanta such that for

Next