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.

Show that the property "no isolated vertices" for has a

*sharp*threshold function .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?*)

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.*)