1.  Show that C_r * C_c  (product of cycles) has bisection width at
    least 2r, assuming r <= c and c even.  Embed the complete directed
    graph.

Any solution to this will have the following structure:

   * how the edges of the complete directed graph are embedded.

   * pick any edge of the host graph and describe which pairs will
     contribute congestion to it.

   * find the congestion: number of all possible pairs.
   
   * There may be different type of edges, and the above computation
     has to be repeated for each, and the maximum picked.

   * Use the formula B >= N^2/4C.

----------------------------------------------------

2.  Show that P_r * P_c has bisection width at least r, assuming r<=c
    and c even.  Do not embed the complete directed graph, but give an
    argument based on the shape of the bisection etc.  Try to
    structure your argument well.

The following sequence of lemmas needs to be proved.  Assume that
vertices on one side of the partition are white and the other black.

1.  There exists an optimal solution in which in every column the
    black vertices are at the bottom and the white at the top.  Also
    black to left and white to right.

2.  If the optimal solution has a full white row as well as a
    full black row, then r=c and all rows are monochromatic, and the
    bisection is r.

3.  The optimal solution cannot have full white rows but not full
    black rows.  (why: the number of edges must be > number of rows
    containing black elements, and these must be at least c)

4.  If the optimal solution has neither full black rows and full black
    columns, then r is a lower bound.

-----------------

3.  Problem 8 of chapter 10 of parallel computation notes.

-----------------------

4.  Show that Q_n can be embedded into Q_k, where k<n, with
    load=congestion=2^{n-k}, dilation=1.

----------------------------