Computer Science Colloquium
Time+Place : Sunday 06/11/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Bill Gasarch
Affiliation: CS, University of Maryland
Host       : Johann Makowsky
Title      : When can you color a grid and not have any monochromatic
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.
Note that there is a rectangle with all four corners the same color (we use
capital letters to denote it)
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
Visit our home page-   <>
Mon Oct 17 07:33:14 IST 2011
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>