due 11/2

1.  Define the chromatic number of a graph as the minimum number of
    colours required such that when each vertex is assigned a colour,
    adjacent vertices get different colours.  A lower bound on the
    chromatic number of a graph is its clique number, i.e. largest n
    such that K_n is its subgraph.  It is tempting to think that this
    relationship is tight.  But it turns out that there are graphs in
    which the chromatic number is much larger than its clique number.
    This can be established very easily by a probabilistic argument.

    Construct an $n$ vertex graph by adding each edge independently
    with probability 1/2.  Use the simple natural argument to find the
    probability that the constructed graph does not contain a clique
    of size $r$, nor an independent set of size $r$ (If not, the graph
    must contain a subset of vertices which either is a clique or is
    independent, and the probability of any such subset existing is
    ...).  Show that this probability is non-zero for r=log n, and
    large enough n.  Note that the vertices of any single colour in
    any colouring form an independent set.  Thus if an n vertex graph
    does not contain an independent set of size log n, then it must
    need at least n/log n colours.  However, you also proved that its
    clique number is less than log n -- this establishes that the
    clique number can be much smaller than the chromatic number!


2.  Problems 1,2,4 of notes on MIS.