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>