A quantitative variant of the multi-colored Motzkin-Rabin theorem

2014/06/05 by Zeev Dvir, Dvir, Zeev, Christian Tessier-Lavigne +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Point processes and geometric inequalities #math.CO

paper · pdf · doi:10.48550/arxiv.1406.1530

arxiv created 2014/06/05 · openalex publication_date 2014/06/05 · arxiv updated 2014/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove a quantitative version of the multi-colored Motzkin-Rabin theorem in the spirit of [BDWY12]: Let V₁,…,V_n ⊂ R^d be n disjoint sets of points (of n `colors'). Suppose that for every V_i and every point v ∈ V_i there are at least δ|V_i| other points u ∈ V_i so that the line connecting v and u contains a third point of another color. Then the union of the points in all n sets is contained in a subspace of dimension bounded by a function of n and δ alone.

Related

• Bounding a global red-blue proportion using local conditions
• Colouring multijoints
• Tolerance for colorful Tverberg partitions
• Equal coefficients and tolerance in coloured Tverberg partitions
• Quantitative Tverberg theorems over lattices and other discrete sets