DIMACS - Graduate Student Combinatorics Seminar

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.