The semirandom method (R\"odl Nibble) is the general approach to prove the existence of something by generating it through many iterations, applying probabilistic reasoning at each step.
One area of Combinatorics where semirandom method has had the greatest impact is graph coloring. In fact, many of the strongest result in graph coloring over the past decade are examples of this method. In this talk we will illustrate how semirandom method works by proving the following result:
Let G=(V,E) be a graph with the sets of lists S(v), one for each vertex v of G, such that
1. for every vertex |S(v)|=(1+o(1))d and
2.for each color c in S(v), the number of neighbors of v that have c in their list is at most d. Then there exist a proper coloring of G from these lists. This result is asymptotically tight.
This is joint work with Bruce Reed.