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

Zeev Dvir, Christian Tessier-Lavigne

Research output: Contribution to journalArticle

1 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)38-47
Number of pages10
JournalDiscrete and Computational Geometry
Volume53
Issue number1
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Algebraic methods
  • Point configurations
  • Sylvester–Gallai

Fingerprint Dive into the research topics of 'A Quantitative Variant of the Multi-colored Motzkin–Rabin Theorem'. Together they form a unique fingerprint.

  • Cite this