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.

(William Gasarch will be teaching a grad course on Ramsey Theory in the Spring. This talk is an example of what will be covered.)

William Gasarch (aka Bill) got his BS in Math and Applied Math (well rounded!) from SUNY Stonybrook in 1980 and a PhD in Computer Science from Harvard in 1985. He has worked in Computational Complexity, Computability Theory, Ramsey Theory, and Muffins. He has been a professor at the Univ of MD since the Fall of 1985.

He has mentored over 100 high school students and undergraduates on research projects. He has ran an REU program which has projects that combine math and computers science since 2013.

Bill has been co-blogging with Lance Fortnow on complexity theory since 2007 at http://blog.computationalcomplexity.org He has written four books

(1) Bounded Queries in Recursion theory

(with Georgia Martin)

(2) Problems with a Point

(with Clyde Kruskal)

(3) Mathematical Muffin Morsels: Nobody wants a small piece

(with Erik Metz, Jacob Prinz, Daniel Smolyak)

(4) Computational Intractability: A Guide to Algorithmic Lower Bounds

(with Erik Demaine, Mohammad Hajiaghayi)

He collects novelty songs and has the largest collection of satires of Nobel Laureate Bob Dylan.