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

Zeev Dvir; Christian Tessier-Lavigne

doi:10.1007/s00454-014-9647-9

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

Zeev Dvir, Christian Tessier-Lavigne

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	38-47
Number of pages	10
Journal	Discrete and Computational Geometry
Volume	53
Issue number	1
DOIs	https://doi.org/10.1007/s00454-014-9647-9
State	Published - Jan 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

Access to Document

10.1007/s00454-014-9647-9

Cite this

@article{4782812ca7d447d9b9bae0be33463fd6,

title = "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.) {\textquoteleft}colors{\textquoteright}). 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.",

keywords = "Algebraic methods, Point configurations, Sylvester–Gallai",

author = "Zeev Dvir and Christian Tessier-Lavigne",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2015",

month = jan,

doi = "10.1007/s00454-014-9647-9",

language = "English (US)",

volume = "53",

pages = "38--47",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

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

AU - Dvir, Zeev

AU - Tessier-Lavigne, Christian

PY - 2015/1

Y1 - 2015/1

N2 - 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.

AB - 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.

KW - Algebraic methods

KW - Point configurations

KW - Sylvester–Gallai

UR - http://www.scopus.com/inward/record.url?scp=84922103441&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84922103441&partnerID=8YFLogxK

U2 - 10.1007/s00454-014-9647-9

DO - 10.1007/s00454-014-9647-9

M3 - Article

AN - SCOPUS:84922103441

SN - 0179-5376

VL - 53

SP - 38

EP - 47

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this