Abstract:

We will be looking at colorings of grids.
A c-coloring of a grid is an assignment toe
every grid point a color.  For example, this is a
2-coloring of the 3 x 7 grid using colors R,B,G.

rrbbbrr
bbrbrbb
rrrrbrb

Note that there is a rectangle with all four corners
the same color (we use capital letters to denote it)

RrbbbRr
bbrbrbb
RrrrbRb

If a grid can be c-colored without a monochromatic
rectangle we say that the grid is c-colorable.

Which grids can be 2-colored? 3-colored? 4-colored? etc.

1) We have characterized EXACTLY which grids are 2-colorable.

2) We have characterized EXACTLY which grids are 3-colorable.

3) We have made porgress on EXACTLY which grids are 4-colorable.

4) We have GIVEN UP on trying to find EXACTLY which grids are 
5-colorable.

The work is a combination of some clever math and some computer work.
The questions has its origins in Ramsey Theory which we will also discuss.

Paper co-authored by Fenner, Gasarch, Glover, Purewal

Short Bio:

William Gasarch recieved a BS in Math and Applied Math at the State
University of Stonybrook in 1980. He then went on to recieve a PhD in
Computer Science from Harvard in 1985. Since then he has been at the
University of Maryland at College Park.
His research interests include Complexity Theory, Computability theory, 
and Combinatorics with an emphasis on Ramsey Theory.  
He has advised many students on all levels including over 20 high school
students.