Studia Scientiarium Mathematicarum Hungarica 30. (1995)

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

4 N. ÁLON, I. KRIZ and J. NESETRIL We estimate the probability of this event by computing the expectation and variance of X1. By linearity of expectation E(Xi) = ^E(xi) = m\p/2k]/p. ses The crucial (and simple) fact for computing the variance is the fact that the random variables X‘, (s £ S) are pairwise independent. This follows from the fact that if s and t are two distinct members of S then when the pair (a, b) ranges over P x P so does the pair ((as + b) (mod p),(at-\-b) (mod p)), implying that X's and X\ are independent. Hence, Therefore, by Chebyschev’s Inequality, Prob(X' = 0) < Prob(\X' - E(X')\ > E(X')) $ < 2k/m. Since there are 2k possible values of i the probability that X1 = 0 for some i is strictly smaller than 4k2/m = 1, completing the proof of the fact. □ Returning to the proof of Theorem 1.1 observe that the last fact implies that randomly chosen a and b supply a good ^-coloring with positive prob­ability. In particular, there is at least one such pair a, b and hence a good coloring exists. For the algorithm, it is essential to choose a small prime p so that all members of S are distinct modulo p, that is, a prime which is smaller than some (fixed) polynomial in the length of the input. Fortunately, the existence of such a prime is simple. A prime p is not good if and only if it divides the product II (')• 5,S/G-S',S>S/ If each number in S is at most 2" (and at least 0, as we may assume since the problem is invariant under any additive shift of 5), and S has m members, 2 the last product is certainly at most 2nm . Since it is well known that the product of all primes smaller than x is e(1+°(1))x this shows that there is a prime p < nm2 that does not divide the product. Therefore, for the algorithm, we simply check, in parallel, for every prime p up to nm2 if it is good, i.e., if all the members of S are distinct modulo p. Once we find such a prime we check, in parallel, all pairs a, b and find Var(X') = Y, Var(Xt) = m^-1(1 - liW.). s£S

Next