A Quantitative Variant of the Multi-colored Motzkin–Rabin Theorem

Abstract

We prove a quantitative version of the multi-colored Motzkin–Rabin theorem in the spirit of Barak et al. (Proceedings of the National Academy of Sciences, 2012): Let (Formula presented.) be (Formula presented.) disjoint sets of points (of (Formula presented.) ‘colors’). Suppose that for every (Formula presented.) and every point (Formula presented.) there are at least (Formula presented.) other points (Formula presented.) so that the line connecting (Formula presented.) and (Formula presented.) contains a third point of another color. Then the union of the points in all (Formula presented.) sets is contained in a subspace of dimension bounded by a function of (Formula presented.) and (Formula presented.) alone.