Homework 6

Deadline: Nov. 18, 22:00:00
  1. Let be an integer and be a -uniform -regular graph (namely, each edge contains exactly vertices and each vertex appears in exactly edges).
    Show that there exists a proper -coloring of .

  2. Let be a -regular directed graph without parallel edges (namely, each vertex has exactly outgoing edges, and there is no edge if exists).
    Show that has a collection of vertex-disjoint cycles.

  3. Let be a simple graph, and suppose each is associated with a set of colors of size at least , where . Suppose, in addition, that for each and there are at most neighbors of such that lies in . Prove that there is a proper coloring of assigning to each vertex a color from its class .

    (Hint: Independent sets.)

  4. The van der Waerden number is the least number such that any -coloring of gives a monochromatic arithmetic progression of length .
    Show that .

  5. (Bonus) Let be a SAT formula, where is the set of variables and is the set of clauses.
    Assume each clause contains at least variables and at most variables, and each variable belongs to at most clauses.
    For any , if , show that there exists a satisfying assignment for and for any and any ,

    where is an assignment chosen uniformly at random from all possibilities.

    (Hint will be given in the next week.)