Helly’s theorem

Suppose $A_{1},\\ldots,A_{m}\\subset\\mathbb{R}^{d}$ is a family of convex sets, and every $d+1$ of them have a non-empty intersection. Then $\\bigcap_{i=1}^{m}A_{i}$ is non-empty.

Proof.

The proof is by induction on $m$ . If $m=d+1$ , then the statement is vacuous. Suppose the statement is true if $m$ is replaced by $m-1$ . The sets $B_{j}=\\bigcap_{i\eq j}A_{i}$ are non-empty by inductive hypothesis. Pick a point $p_{j}$ from each of $B_{j}$ . By Radon’s lemma, there is a partition of $p$ ’s into two sets $P_{1}$ and $P_{2}$ such that $I=(\\operatorname{conv}P_{1})\\cap(\\operatorname{conv}P_{2})\eq\\emptyset$ . For every $A_{j}$ either every point in $P_{1}$ belongs to $A_{j}$ or every point in $P_{2}$ belongs to $A_{j}$ . Hence $I\\subseteq A_{j}$ for every $j$ .∎

单词	HellysTheorem
释义	Helly’s theorem Suppose $A_{1},\\ldots,A_{m}\\subset\\mathbb{R}^{d}$ is a family of convex sets, and every $d+1$ of them have a non-empty intersection. Then $\\bigcap_{i=1}^{m}A_{i}$ is non-empty. Proof. The proof is by induction on $m$ . If $m=d+1$ , then the statement is vacuous. Suppose the statement is true if $m$ is replaced by $m-1$ . The sets $B_{j}=\\bigcap_{i\eq j}A_{i}$ are non-empty by inductive hypothesis. Pick a point $p_{j}$ from each of $B_{j}$ . By Radon’s lemma, there is a partition of $p$ ’s into two sets $P_{1}$ and $P_{2}$ such that $I=(\\operatorname{conv}P_{1})\\cap(\\operatorname{conv}P_{2})\eq\\emptyset$ . For every $A_{j}$ either every point in $P_{1}$ belongs to $A_{j}$ or every point in $P_{2}$ belongs to $A_{j}$ . Hence $I\\subseteq A_{j}$ for every $j$ .∎
随便看	TopologicalGroup topological group TopologicalGroupobsolete topological group (obsolete) TopologicalGroupRepresentation topological group representation TopologicalGspace topological G-space TopologicalInvariant topological invariant Bertrand’s conjecture Bertrand’s conjecture, proof of Bertrand’s problem BesselFunctionsAndHelicalStructureDiffractionPatterns Bessel functions and helical structure diffraction patterns BesselInequality Bessel inequality BesselsEquation Bessel’s equation BestApproximation best approximation BestApproximationInInnerProductSpaces best approximation in inner product spaces BetaFunction beta function