Skip to main content

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

Author(s): Dvir, Zeev; Tessier-Lavigne, Christian

To refer to this page use:
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.
Publication Date: 19-Nov-2014
Electronic Publication Date: 2014
Citation: Dvir, Z, Tessier-Lavigne, C. (2015). A Quantitative Variant of the Multi-colored Motzkin–Rabin Theorem. Discrete and Computational Geometry, 53 (38 - 47. doi:10.1007/s00454-014-9647-9
DOI: doi:10.1007/s00454-014-9647-9
Pages: 38 - 47
Type of Material: Journal Article
Journal/Proceeding Title: Discrete and Computational Geometry
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.