MA530 -- Discrete Mathematics I

Hints for Assignment 3

1. Given the original coloring of integers, consider a (sufficiently large) integer n and color the edges of the complete graph K_n by the following rule: edge {i,j} gets color equal to the color of the integer |i-j| in the original coloring.

2. First verify that the polygon formed by a set of n points in the plane is convex if and only if any quadrilateral formed by four of these n points is convex. Now use Ramsey's Theorem.

3. Use the probabilistic method. Each edge of K_n is to be replaced by an arc; do this at random, choosing each direction with probability 1/2. For a given set M of m vertices, let D(M) be the event that there is no x which dominates M. Compute the probability of event D(M).

4. Consider substrings of length k obtained by shifting by a fixed offset modulo p.

William J. Martin / WPI / martin `at' wpi.edu