Barany, I;
Meshulam, R;
Nevo, E;
Tancer, M;
(2018)
Pach's Selection Theorem Does Not Admit a Topological Extension.
Discrete & Computational Geometry
, 60
(2)
pp. 420-429.
10.1007/s00454-018-9998-8.
Preview |
Text
Barany ntp071016.pdf - Accepted Version Download (258kB) | Preview |
Abstract
Let U1,…,Ud+1 be n-element sets in Rd . Pach’s selection theorem says that there exist subsets Z1⊂U1,…,Zd+1⊂Ud+1 and a point u∈Rd such that each |Zi|≥c1(d)n and u∈conv{z1,…,zd+1} for every choice of z1∈Z1,…,zd+1∈Zd+1 . Here we show that this theorem does not admit a topological extension with linear size sets Zi . However, there is a topological extension where each |Zi| is of order (logn)1/d .
| Type: | Article |
|---|---|
| Title: | Pach's Selection Theorem Does Not Admit a Topological Extension |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00454-018-9998-8 |
| Publisher version: | https://doi.org/10.1007/s00454-018-9998-8 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Science & Technology, Technology, Physical Sciences, Computer Science, Theory & Methods, Mathematics, Computer Science, Pach's Selection Theorem, Gromov's Overlap Theorem, EXPANDERS, PLANES |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/1522760 |
Archive Staff Only
 |
View Item |
