找回密码
 快速注册
搜索
查看: 52|回复: 6

Helly定理

[复制链接]

3149

主题

8386

回帖

6万

积分

$\style{scale:11;fill:#eff}꩜$

积分
65391
QQ

显示全部楼层

hbghlyj 发表于 2023-5-7 06:27 |阅读模式
(百度百科居然有两个词条:黑利定理 | 海莱定理)
在平面上,设$M_1,M_2,…,M_n\ (n≥3)$是凸集,如果其中每三个凸集都有公共点,那么这$n$个凸集必有公共点.
A2 A1 A4 (2) A3 A2 A4 A3 A1 (3) (1) A1 A2 A3 A4 下面我们证明海莱定理. 证明:我们对凸集的个数$n$用数学归纳法. 1、当$n=3$时,命题显然成立. 2、设$n=k(k>3)$时,命题成立.我们证明命题对于$n=k+1$成立.即设$M_1,M_2,…,M_{k+1}$为$k+1$个凸集,其中每三个有公共点,要证明这$k+1$个凸集有公共点. 由于$k$个凸集$M_2,M_3,M_4,…,M_k,M_{k+1}$中每三个有公共点,根据归纳假设,这$k$个凸集有公共点$A_1$.同样,设$M_1,M_3,M_4…,M_{k+1}$有公共点$A_2$;$M_1,M_2,M_4,…,M_{k+1}$有公共点$A_3$;$M_1,M_2,M_3,M_5,…,M_{k+1}$有公共点$A_4$. 如果$A_1,A_2,A_3,A_4$这四个点中有相同的,比如$A_1$和$A_2$相同,那么$A_1$就是$M_1,M_2,…,M_{k+1}$这$k+1$个凸集的公共点,命题成立.如果$A_1,A_2,A_3,A_4$这四个点互不相同,考察它们的凸包$H$.有下面三种情况: (i)$H$为凸四边形$A_1A_2A_3A_4$. 这时线段$A_1A_3$与$A_2A_4$相交于一点$A$,因为$A_1∈M_2,A_3∈M_2$,$M_2$是凸集,所以$A∈M_2$.同理$A∈M_4,A∈M_5,…,A∈M_{k+1}$.又因为$A_2∈M_1,A_4∈M_1$,$M_1$是凸集,所以$A∈M_1$.同理$A∈M_3$.因此$A$是$M_1,M_2,…,M_{k+1}$这$k+1$个凸集的公共点. (ii)$H$为$△A_1A_2A_3$. 这时因为$A_1,A_2,A_3$都属于$M_4$,所以$△A_1A_2A_3$包含于$M_4$,从而由$A_4∈△A_1A_2A_3$,得到$A_4∈M_4$.因此$A_4$是$M_1,M_2,…,M_{k+1}$这$k+1$个凸集的公共点. (iii)$H$为一线段$A_1A_2$. 这时$A_4∈A_1A_2$,从而$A_4$包含于$M_4$,所以是$A_4$是$M_1,M_2,…,M_{k+1}$这$k+1$个凸集的公共点. 综上所述就证明了海莱定理.

3149

主题

8386

回帖

6万

积分

$\style{scale:11;fill:#eff}꩜$

积分
65391
QQ

显示全部楼层

 楼主| hbghlyj 发表于 2023-5-7 06:29
CSDN
陈述:设$X_1,X_2,⋯,X_n$为$n$个在$\Bbb R^d$空间中的凸集合,且$n>d$.如果任意$d+1$个凸集合交集不为空,那么这个凸集合的交集不为空.
一个直观的例子:对于二维空间,我们有4个圆形.如果他们任意三个交集不为空,那么这4个圆形的交集一定不为空.
证明:当$n=d+1$时是平凡的.设$n=d+2$.注意根据我们的assumption,我们有:任意$d+1$交集为不空.对于$j=1,2,3,⋯,n$,均存在一个点$x_j$在$X_i(i≠j)$的交集中,但不在$X_j$中.如果$1\neq k$,但$x_1=x_k$,那么我们可以直接得出结论,交集是非空的,这是平凡的.设$x_j$互不相同,$A=\{x_j:j=1,2,3,⋯,n\}$.根据radon定理,对于这$n$个点,我们可以找到(也一定存在)一个划分将$A$划分为$A_1$和$A_2$两个凸集合,使得他们存在radon点(convex hull的交点).不妨假设这个radon点是$p$,下面我们证明这个$p$在所有$X_j$中,也即:$p$就是我们的要找的交集中的一个点.
讨论:既然我们我们将$\{x_j\}$分为了两个集合(交集为空).
1.假设$x_j$在$A_1$中,自然地,$x_j$不在$A_2$中.那么有$A_2$一定是$X_j$的子集.(因为这$n$个点中,唯一不在$X_j$中的就是$x_j$了,而$A_2$中的点一定在$X_j$中).由于$A_2$在$X_j$中,而且$X_j$是一个凸集合,所以conv($A_2$)$\subset X_j$,所以conv($A_2$)和conv($A_1$)交点$p$(请注意$p$可能落在convex hull上也可能就是$A$中的点)一定在$X_j$中.($p$在$X_j$中是由凸性来做保证的)

3149

主题

8386

回帖

6万

积分

$\style{scale:11;fill:#eff}꩜$

积分
65391
QQ

显示全部楼层

 楼主| hbghlyj 发表于 2023-5-7 06:33
2.同理,如果$x_j$在$A_2$中,也容易证明$p$在$X_j$中.进一步,$p$在所有的$X_j$中.我们找到了这个$n$个凸集合交集的一个$p$:如果我没说明白,我画了一个图:
220325182800b9607434206a80.png
好了.我们已经完成了$n=d+2$的情况.
下面就是归纳了.因为定理是比我们刚才证明要更强的:$n$只要大于$d$就成立的.
假设$n\ge d+3$,并且我们手中已经有$n+2$时候成立了.考虑$X_1$和$X_n$,我们使用$X_{n-1}∩X_n$(非空,凸集)代替他们.就可以进行推广了.

3149

主题

8386

回帖

6万

积分

$\style{scale:11;fill:#eff}꩜$

积分
65391
QQ

显示全部楼层

 楼主| hbghlyj 发表于 2023-5-7 06:36
Linear Algebra and Its Applications 线性代数及其应用 [美] Peter D. Lax 人民邮电出版社 ; 第170页

本章最后一个内容是卡拉泰奥多里定理的对偶定理.
定理 12 (黑利 (Helly)) 设 $X$ 是实数域上的 $n$ 维线性空间. $\left\{K_1, \cdots, K_N\right\}$ 是 $X$ 中的一集凸集, 假设其中任意 $n+1$ 个凸集 $K$ 的交都非空, 则全体 $K$ 必有一个公共点.
证明 (拉东 (Radon)) 对集合个数 $N$ 进行归纳, $N=n+1$ 时是显然的. 假设 $N>n+1$, 且定理对 $N-1$ 个集合成立. 因此, 如果去掉一个集合, 比如 $K_i$, 其余集合有一个公共点 $x_i:$
$$\tag{27}
x_i \in K_j, \quad j \neq i
$$
我们断言存在不全为零的数 $a_1, \cdots, a_N$, 使得
\begin{gather}
\sum_1^N a_i \boldsymbol{x}_i=0,\tag{28} \\
\sum_1^N a_i=0 .\tag{28$'$}
\end{gather}上面两式表示含 $N$ 个未知数的 $n+1$ 个方程. 由第 3 章定理 2 的推论 $\mathrm{A}^{\prime}$ (基本形式), 如果方程个数少于未知数个数, 齐次线性方程组必有非平凡解 (即不全为零的解). 而此处假设了 $n+1<N$, 故 (28) 式和 (28$'$) 式有一组非平凡解.
由 $(28)^{\prime}$ 式可知, 并非全体 $a_i$ 都同号, 必然有正有负. 因此重新排序后可使 $a_1, \cdots, a_p$ 为正, 其余为负.
定义 $a$ 为
$$\tag{29}
a=\sum_1^p a_i
$$
注意, 由 $(28^{\prime})$ 式有
$$\tag{29$'$}
a=-\sum_{p+1}^N a_i
$$
定义 $y$ 为
$$\tag{30}
y=\frac{1}{a} \sum_1^p a_i \boldsymbol{x}_i
$$

3149

主题

8386

回帖

6万

积分

$\style{scale:11;fill:#eff}꩜$

积分
65391
QQ

显示全部楼层

 楼主| hbghlyj 发表于 2023-5-7 06:37
注意由 (28) 式和 (30) 式有
$$\tag{30$'$}
\boldsymbol{y}=\frac{-1}{a} \sum_{p+1}^N a_i \boldsymbol{x}_i
$$
每个点 $\boldsymbol{x}_i(i=1, \cdots, p)$ 都属于 $K_j(j>p)$ 中的每个集合. 由 (29) 式可知, (30) 式将 $\boldsymbol{y}$ 表示为 $\boldsymbol{x}_1, \cdots, \boldsymbol{x}_p$ 的一个凸组合. 对任意 $j>p$, 由于 $K_j$ 是凸集, 所以有 $\boldsymbol{y} \in K_j$. 另一方面, 每个 $\boldsymbol{x}_i(i=p+1, \cdots, N)$ 都属于 $K_j(j \leqslant p)$. 由 $(29)^{\prime}$ 式可知, $(30)^{\prime}$ 式将 $\boldsymbol{y}$ 表示为 $x_{p+1}, \cdots, \boldsymbol{x}_N$ 的一个凸组合. 对任意 $j \leqslant p$, 由于 $K_j$ 是凸集, 所以 有 $y \in K_j$. 这就完成了黑利定理的证明.
注记 黑利定理即便在 1 维情形下也不是显然的. 此时每个 $K_j$ 都是区间, 若假设每两个 $K_i$ 和 $K_j$ 都相交, 则任意 $K_i$ 的左端点 $a_i$ 都小于或等于每个 $K_j$ 的右端点. 所有 $K_i$ 的公共点就是 $\sup a_i$ 或 $\inf b_i$, 或者介于这两者之间的任何一点.
注记 本章我们仅仅利用包含凸集的空间的线性结构定义了凸开集、凸闭集、有界凸集等概念. 当然, 在欧几里得距离意义下开、闭、有界这些概念有各自的拓扑意义. 容易看出, 如果一个凸集在拓扑意义下是开的、闭的或有界的, 那么在本章 所讨论的线性结构下它就是开的、闭的或有界的.
练习 20 证明: 在有限维欧几里得空间中, 如果一个凸集在线性结构下是开的、闭的或是有界的, 则它在拓扑意义下也是开的、闭的或是有界的, 反之亦然.

3149

主题

8386

回帖

6万

积分

$\style{scale:11;fill:#eff}꩜$

积分
65391
QQ

显示全部楼层

 楼主| hbghlyj 发表于 2023-5-7 09:13
en.wikipedia.org/wiki/Helly
We prove the finite version, using Radon's theorem as in the proof by Radon(1921). The infinite version then follows by the finite intersection property characterization of compact space: a collection of closed subsets of a compact space has a non-empty intersection if and only if every finite subcollection has a non-empty intersection (once you fix a single set, the intersection of all others with it are closed subsets of a fixed compact space).

The proof is by induction:

Base case: Let $n=d+2$. By our assumptions, for every $j=1,⋯,n$ there is a point $x_j$ that is in the common intersection of all $X_i$ with the possible exception of $X_j$. Now we apply Radon's theorem to the set $A=x_1,...,x_n$, which furnishes us with disjoint subsets $A_1,A_2$ of $A$ such that the convex hull of $A_1$ intersects the convex hull of $A_2$. Suppose that $p$ is a point in the intersection of these two convex hulls. We claim that
$$p\in\bigcap_{j=1}^n X_j.$$
Indeed, consider any $j∈\{1,...,n\}$. We shall prove that $p∈X_j$. Note that the only element of $A$ that may not be in $X_j$ is $x_j$. If $x_j∈A_1$, then $x_j∉A_2$, and therefore $X_j⊃A_2$. Since $X_j$ is convex, it then also contains the convex hull of $A_2$ and therefore also $p∈X_j$. Likewise, if $x_j∉A_1$, then $X_j⊃A_1$, and by the same reasoning $p∈X_j$. Since $p$ is in every $X_j$, it must also be in the intersection.

Above, we have assumed that the points $x_1,...,x_n$ are all distinct. If this is not the case, say $x_i=x_k$ for some $i≠k$, then $x_i$ is in every one of the sets $X_j$, and again we conclude that the intersection is nonempty. This completes the proof in the case $n=d+2$.

Inductive Step: Suppose $n>d+2$ and that the statement is true for $n−1$. The argument above shows that any subcollection of $d+2$ sets will have nonempty intersection. We may then consider the collection where we replace the two sets $X_{n−1}$ and $X_n$ with the single set $X_{n−1}∩ X_n$. In this new collection, every subcollection of $d+1$ sets will have nonempty intersection. The inductive hypothesis therefore applies, and shows that this new collection has nonempty intersection. This implies the same for the original collection, and completes the proof.

3149

主题

8386

回帖

6万

积分

$\style{scale:11;fill:#eff}꩜$

积分
65391
QQ

显示全部楼层

 楼主| hbghlyj 发表于 2023-5-7 09:14
The Art of Mathematics: Coffee Time in Memphis, page 23-24

28. Convexity and Intersecting Simplices
(i) Let $X=\left\{\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{n+2}\right\}$ be a set of $n+2$ points in $\mathbb{R}^{n}$ and, for a non-empty subset $I$ of $\{1, \ldots, n+2\}$, let $X(I)$ be the convex hull of the points $\mathbf{x}_{i}, i \in I$. Show that there are disjoint sets $I, J$ such that $X(I) \cap$ $X(J) \neq \varnothing .$
(ii) The convex hull $\operatorname{conv} X$ of a set $X \subset \mathbb{R}^{n}$ is the smallest convex set containing $X$ : the intersection of all convex sets containing it. Equivalently,
$$
\operatorname{conv} X=\left\{\sum_{i=1}^{k} \lambda_{i} \mathbf{x}_{i}: \mathbf{x}_{i} \in X, \lambda_{i} \geq 0, \sum_{i=1}^{k} \lambda_{i}=1, k=1,2, \ldots\right\}
$$
Show that in the sums above we need not take more than $n+1$ terms, i.e., the convex hull of a set $X \subset \mathbb{R}^{n}$ is
$$
\operatorname{conv} X=\left\{\sum_{i=1}^{n+1} \lambda_{i} \mathbf{x}_{i}: \mathbf{x}_{i} \in X, \lambda_{i} \geq 0, \sum_{i=1}^{n+1} \lambda_{i}=1\right\}
$$
29. Intersecting Convex Sets. Let $\mathcal{C}$ be a finite family of convex sets in $\mathbb{R}^{n}$ such that for $k \leq n+1$ any $k$ members of $\mathcal{C}$ have a non-empty intersection. Show that the intersection of all members of $\mathcal{C}$ is non-empty.
30. Judicious Partitions of Points. Let $P_{1}, \ldots, P_{n}$ be $n$ points in the plane. Show that there is a point $P$ such that every line through $P$ has at least $n / 3$ points $P_{i}$ in each of the two closed half-planes it determines.

手机版|悠闲数学娱乐论坛(第3版)

GMT+8, 2025-3-4 12:02

Powered by Discuz!

× 快速回复 返回顶部 返回列表