Title: Rectangle-Free Grid Coloring
Speaker: Elizabeth Kupin, Rutgers University
Date: Wednesday, February 3, 2010 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Imagine a sheet of graph paper, that we will fill in entirely by assigning each square a color. How many colors do we need to be able to guarantee that no 4 squares that are the corners of an (axis-parallel) rectangle have the same color? This Ramsey-type question turns out to be similar to a question about bipartite Ramsey numbers, and lately there has been some effort in lowering the bounds and constructing exact solutions. I'll talk about some of the history of the problem, the many questions that are still open, and maybe a bit of the work I've done to try to tackle these problems.