Homework 5

Deadline: Nov. 4, 22:00:00
  1. Show that there is a finite such that any directed graph on vertices in which each outdegree is at least contains an even simple directed cycle.

  2. Show that the property "no isolated vertices" for has a sharp threshold function .

  3. Consider a random bipartite graph . We claim that the property " has a perfect matching" has a sharp threshold function . We prove this conclusion as follows.

    • Show that for any , if then does not have a perfect matching.

    • Show that if does not have a perfect matching, then there exists a set such that (i) , where is the set of all neighbors of ; (ii) ; (iii) every vertex in has at least two neighbors in .

    • Show that if , does not contain such of size asymptotically almost surely.

      (Hint: You may need the estimation , and compute for the case and respectively.)

    • Complete the whole proof.

      (Hint: Is there any situation we're missing above?)

  4. We now claim a four-point concentration for the chromatic number of sparse random graphs.

    Let be fixed, and . We will show that for all , there exists a function such that

    Let be the smallest positive integer such that , and be the random variable that is the minimum size of where can be properly -colored. If is already at most , then .

    • Upper bound the difference of with respect to the vertex-exposure martingale and the edge-exposure martingale, respectively.

    • Use the bounded differences inequality to show that for some .

    • Show that .

    • Show that for any subset of size at most (where does not depend on ), the induced subgraph can be properly colored with colors with probability .

      (Hint: Review the previous lecture notes.)