Pach's selection theorem does not admit a topological extension

Abstract: Let

U_{1}, d o t s, U_{d + 1}

be

n

-element sets in

R^{d}

and let

l a n g l e u_{1}, l d o t s, u_{d + 1} a n g l e

denote the convex hull of points

u_{i}

in

U_{i}

(for all

i

) which is a (possibly degenerate) simplex. Pach's selection theorem says that there are sets

Z_{1} s u b s e t U_{1}, d o t s, Z_{d + 1} s u b s e t U_{d + 1}

and a point

u

in

R^{d}

such that each

| Z_{i} | > c_{1} (d) n

and

u

belongs to

l a n g l e z_{1}, ..., z_{d + 1} a n g l e

for every choice of

z_{1}

in

Z_{1}, d o t s, z_{d + 1}

in

Z_{d + 1}

. Here we show that this theorem does not admit a topological extension with linear size sets

Z_{i}

. However, there is a topological extension where each

| Z_{i} |

is of order

(l o g n)^{(} 1 / d)

.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Pach's selection theorem does not admit a topological extension