Studia Scientiarium Mathematicarum Hungarica 30. (1995)

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

HOW TO COLOR SHIFT HYPERGRAPHS 3 every k > 1 there is a set S — Sk of at least ak log k integers so that there is no good k-coloring for the shift hypergraph H{S). The proof of Theorem 1.1 is based on the ideas of [3] and is presented in the next section, together with some related extensions. In Section 3 we describe two proofs of Theorem 1.2; a probabilistic one and a constructive one. The final Section 4 contains some concluding remarks. Finding a good coloring Proof of Theorem 1.1. Let 5 be a given set of m = 4k2 distinct in­tegers. Our objective is to find a good ^-coloring c for the shift hypergraph H (S). To do so, we first choose a prime p so that the members of S are pair­wise distinct modulo p. Let P — {0,1,... ,p— 1} be the set of all remainders modulo p and let us split P into k pairwise disjoint intervals of consecutive remainders Ix, 72, • • • , Ik, where [p/k\ ^ |/,j < \p/k] for all 1 < i < k. For two integers a and b in P, let c = caib be the following fc-coloring of the set of integers. For every integer y, c(y) is the unique i so that (ay + + 6) (mod p)£/,. Define Y = Ya<b — {(as -f b) (mod p) : s £ 5}. We claim that if a, b are chosen in such a way that the set Y intersects every (cyclic) interval of length [p/kJ in P then every translate of S intersects each color class of c. To see this, observe that if z + S is a translate of S then the set {(ay + 6) (mod p) :y£x + S} is a cyclic translate of Y and hence it intersects every interval of length [p/k\ in P and in particular it intersects every implying the desired result. It thus suffices to choose a, b so that Yatb has the above property. We next show that this can be done. Fact. If a and b are chosen randomly and independently in P, according to a uniform distribution, then with positive probability the set Y = Ya<b intersects every cyclic interval of length at least [p/k\ in P. Proof. The argument essentially appears in [3], but since it is very short we repeat it here. Let J\,... , J2k be a fixed covering of P by 2k intervals of length \p/2k] each. Observe that if Y intersects each J, then it certainly satisfies the required property, since every cyclic interval of length \_p/k\ must fully contain at least one interval J,. Fix an i, 1 < i < 2k and put m= |5| =4k2. For each element s £ S let Xj be the indicator random variable whose value is 1 if (as4-6) (mod p) £ J, (and is 0 otherwise). Define X1 = Ylses X's and observe that X1 = 0 if and only if Y does not intersect Jx.

Next