Name
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 $$V_1,\\ldots ,V_n \\subset {\\mathbb {R}}^d$$V1,¿,Vn¿Rd be $$n$$n disjoint sets of points (of $$n$$n `colors'). Suppose that for every $$V_i$$Vi and every point $$v \\in V_i$$v¿Vi there are at least $$\\delta |V_i|$$¿|Vi| other points $$u \\in V_i$$u¿Vi so that the line connecting $$v$$v and $$u$$u contains a third point of another color. Then the union of the points in all $$n$$n sets is contained in a subspace of dimension bounded by a function of $$n$$n and $$\\delta $$¿ alone. |
Year | DOI | Venue |
|---|---|---|
2015 | https://doi.org/10.1007/s00454-014-9647-9 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Sylvester–Gallai,Point configurations,Algebraic methods | Discrete mathematics,Topology,Colored,Combinatorics,Disjoint sets,Subspace topology,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
53 | 1 | 0179-5376 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zeev Dvir | 1 | 437 | 30.85 |
| Christian Tessier-Lavigne | 2 | 0 | 0.34 |