4
$\begingroup$

Helly's Theorem states the following: Suppose that $X_1,X_2,...,X_n$ are convex sets in $\mathbb{R}^d$, such that for any $|I|\leq d+1$, $\cap_{i\in I}X_i \neq \emptyset$. Then $\cap_{i=1}^{n}X_i \neq \emptyset$.

I'm looking for interesting problems, the solutions of which use this theorem.

Here is one example: Let $K_1,K_2,...,K_n$ be closed intervals parallel to the $y$ axis. Assume that for any $|I|\leq d+2$ there exists a polynomial of degree at most $d$, the graph of which intersects all $K_i$ where $i\in I$. Show that there exists a polynomial of degree at most $d$, the graph of which intersects all the intervals $K_1,K_2,...,K_n$.

  • 0
    Could you please tell me, from where we can see the solution's of your example; Let $K_1, K2,...,K_n$ be closed intervals parallel to the $y$ axis...2017-06-05

2 Answers 2

1

Problem 127 in Bollobas, The Art of Mathematics: Let $C$ be a convex body in ${\bf R}^n$, a compact convex set with non-empty interior. A maximal interval $[u,v]$ contained in $C$ is a chord of $C$. Show that $C$ contains a point $c$ that is not far from being central in the following sense: for every chord $[u,v]$ through $c$, ${\|c-u\|\over\|v-u\|}\le{n\over n+1}$

Bollobas' solution uses Helly's Theorem. He also refers to Danzer, Grunbaum, and Klee, Helly's theorem and its relatives, in Convexity, Proc Symp Pure Math VII (1963) 101-180.

1

Problem 18 in Yaglom & Boltyanskii's Convex Figures:

a) Given $n$ points in the plane, prove there exists a point $O$ such that every line through $O$ cuts off at least $1/3$ of the points (including those that lie on the line). In other words, there is no line through $O$ that leaves $< n/3$ points on one side of it.

b) Given a bounded curve in the plane (possibly not connected), prove there exists a point $O$ such that every line through $O$ cuts off at least $1/3$ of the length of the curve.

c) Given a bounded figure in the plane (possibly not connected), prove there exists a point $O$ such that every line through $O$ cuts off at least $1/3$ of the area.

Their solution uses Helly's Theorem for infinite collections of sets.