Description
In this talk, we present a new family of hypergraphs with arbitrarily large uniformity and chromatic number. We discuss two applications of these hypergraphs.
First, we give a new proof of a theorem of Chen, Pach, Szegedy, and Tardos. They showed that for any constants c,d>1, there exists a point set P of n points in the plane with the following property: for every coloring of P with c colors, there is an axis-parallel rectangle containing at least d points, all of the same color. Their original proof is probabilistic; we present an explicit construction. Moreover, in the case d=2, we show that one can even realize a graph of arbitrarily high girth and chromatic number using points and axis-parallel rectangles.
Second, we answer a question raised by Domotor Palvolgyi. We show that for any constants c,d>1, there exists a set S of positive integers with the following property: for every c-coloring of S, there is a finite arithmetic progression A whose difference is a power of two such that A\cap S is monochromatic and has size at least d.
Finally, we describe a strong connection between these two, at first sight rather different, problems.