Description
Abstract: We study polychromatic colorings and prove results of the following nature: For every positive integer k and any finite set of points in the plane, one can k-color the pairs of points so that every disc that contains at least 5^k points, also contains a pair of points from each of the k color classes.
We generalize this result to arbitrary hypergraphs with bounded VC-dimension that satisfy some nice properties (such as shrinakability and coveribility). We prove that there exists a constant c=c(d) so that the d+1 tuples in any such hypergraph with VC-dimension at most d can be k-colored so that any hyperedge of size at least c^k contains a d+1 tuple from each of the k color classes.
We also study the relation of the polychromatic subsets coloring to the classical well studied notion of vertex polychromatic coloring. Finally, we show a relation of the subsets coloring to a recently introduced notion of epsilon-t-nets.
Joint work with Milos Stojakovic