Technion
 
         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
             rectangles?
 
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.
 
----------------------------------------------------------
Visit our home page-   <http://www.cs.technion.ac.il/~colloq>
Mon Oct 17 07:33:14 IST 2011
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Hadas Heier   <heier@cs.technion.ac.il>