凸集的相交和覆盖性质外文翻译资料

 2022-08-22 10:08

英语原文共 15 页,剩余内容已隐藏,支付完成后下载完整资料


凸集的相交和覆盖性质

笑?这是因为你还没有看到根本的理论:如果船沉了,哈代淹死了,每个人都必须相信他已经证明了黎曼假设。然而,上帝不会让哈代有这么大的荣誉,所以他不会让船下沉。

我相信这个故事,因为几乎同样的事情发生在我的面前。另一个夏天哈代呆在恩格尔堡,在瑞士的一个高山峡谷,我们有一个小木屋。他喜欢阳光,但总是下雨,因为没有别的事可做,我们就打桥牌:哈迪,他桥牌打得很好,我和我的妻子,还有我的一个朋友,F.冈赛斯,数学家和哲学家。然而,过了一段时间,赛斯不得不离开,他不得不去赶火车。哈代对冈赛斯说:“请,当火车启动时,你打开窗户,把头探出窗外,仰望天空,大声说:lsquo;我是哈代。rsquo;”我当时在场。“现在,你们有些人在笑。你已经理解了基本的理论:当上帝认为哈代已经离开,他会创造好天气只是为了惹恼哈代。

我希望你吃午饭不会太晚。谢谢你!

1969年2月8日,圣克拉拉大学北加州分部会议。

凸集的相交和覆盖性质

加利福尼亚大学戴维斯分校G. D. Chakerian

1.介绍

本文综述了关于有限二维凸集的交和覆盖性质的组合几何的一些结论。我们主要关注的是以下定理的变体,它是由Eduard Helly在1913年发现的。

Helly定理 假设F是一个紧致的欧氏n维空间的凸子集族,它的性质是F中的每个n 1或更少的元素有一些共同点。那么F中的所有元素都有一个共同点。

我们所说的大部分内容都与优秀的参考文献[6]中的内容相重叠,[6]对Helly定理及其变体和各种应用进行了全面的考察。我们的叙述在很大程度上是对[6]中出现的一些选定主题的简短处理,包括自其发布以来发现的一些结果。(俄文译本[6],经修订和更新,并附有其他参考文献,计划很快出版)关于这一材料的另一个优秀参考文献是专著[11]。题目的选择自然反映了作者的兴趣,这些内容一般都强调与作者与S. K. Stein和G. T. Sallee的合作有关。

在下一节中,我们将从凸集理论中发展出一些重要的思想,这些思想除了本身的兴趣外,在后面几节中将会有用。我们用第三节来讨论Helly定理的证明,它使用了一些基本思想。由于我们说了很多的凸集的平移族,所以我们在第四节中专门讨论了平移的一些性质。后面的部分将涉及到这篇文章的真正内容,即Helly定理的变体以及凸集的覆盖和相交属性。

作者表示感谢B. Grtinbaum, V. Klee, G. T. Sallee, S. K. Stein,以及对这篇文章的手稿所作的大量有益评论的审稿人,这些评论有助于文章的改进。

2.一些开场白

在下文中,, n维欧几里得空间,对于之间通常的内积用表示。之间的距离我们用来表示。是以为中心的半径为的封闭球体。我们将考虑紧凑、凸子集的 ,也就是说,这些紧凑的子集有一个性质每当,到的线段上的每个点都属于 .因此是凸的当且仅当,每一个形式为 的凸组合,其中 是满足的非负实数,属于。一般来说,如果,那么通过这些点的凸组合,我们指的是一个点的形式,其中为非负实数,且满足。从定义中,我们可以很容易地看出,当且仅当的点的任何凸组合再次属于时,才是凸的。的一个常见且特别重要的凸组合是它们的质心,定义为。

如果A是的任意非空子集,那么A的凸包,即conv A,是包含A的所有凸集的交集。因为有限个点的任意凸组合包含在每个包含A的凸集中,可以看出所有这些凸组合的集合是conv A的子集。另一方面,很容易看出,所有这些凸组合的集合本身就是一个包含A的凸集合,因此包含了conv A。由此可见,convA实际上与A的有限子集的所有凸组合的集合是一致的。由C. Caratheacute;odory定理可知,在构造conv A时,通过形成点的凸组合,不需要取n 1个点以上的凸组合。换句话说,conv A的每个点都包含在某个顶点属于A的单纯形中。

Caratheacute;odory定理 让。那么conv A中的任何点都可以表示为A的n 1或更少点的凸组合。

我们不会在这里证明Caratheodory定理,但它与Helly定理是等价的,在这个意义上,两个定理中的一个可以很容易地从另一个中推导出来(为了证明,读者可以参考[7])。然而,我们稍后将使用以下Caratheodory定理的直接推论来证明Helly定理。

推论1 设z是的质心,其中一些,但不是所有的可能重合。那么z就是与z不同的上的n 1或更少的点的凸组合。

如果K是一个紧子集,是上的某个点,那么连续函数(x在K上变化)在K上达到一个最小值。根据T. S. Motzkin定理,用最近的点来描述紧致凸集(定理的证明和一些有趣的相关问题见[16,Part VII])。

Motzkin定理 令是紧致的。那么是凸的当且仅当对于每个都有一个唯一的最近点K

假设K是的一个紧致凸子集。对于每个,令是的唯一最近点(例如,当且仅当。这很容易证明。

(1),对于所有

特别地,它得出连续地依赖于,我们在下一节将用到的的一个性质是,如果不包含于K,那么K完全位于与向量正交的超平面的一边,并且包含。这个超平面是K的一个支持超平面,由该平面所围成的含K的封闭支撑半空间可表示为

(2)

3.Helly定理的证明

现在我们应用上一节的一些思想来证明Helly定理。这个证明在原则上与[7]和漂亮的论文[14]中出现的证明是一样的。实际上,我们加重了这种重复的罪恶,并通过在一个阶段求助于一个强大的拓扑定理破坏了证明的基本性质,但这样做是希望获得一些更容易概念化的东西。这里需要强调的是,有很多Helly定理的证明比这个证明要简单得多。Helly自己的证明是其中最简单的,几乎不需要任何机械方面的东西。事实上,正如Victor Klee指出作者Helly定理(对于有限凸集族,其中可以去掉紧致性的限制)并不依赖于任何拓扑条件,事实上,它在任意序域上的有限维向量空间中是有效的。对于其中的一些证明,以及对其他证明的引用,读者可以参考[6]。

我们的证明过程如下。一个利用的紧性的简单论证证明了情形9中的定理只包含有限多的元素。假设K1,hellip;, Kr,我们现在假设f中的所有元素都没有公共点,并证明一些n 1或更少的元素没有公共点。

一个利用F的紧致性的简单论证证明了情形9中的定理只包含有限多的元素,假设我们现在假设F中的所有元素都没有公共点,并证明一些n 1或更少的元素没有公共点。

B是包含所有F的闭球,定义一个映射f :,为每个分配F中元素的最近点集的质心。也就是说,设,其中是到的最近点。那么f是BB的一个定义良好的连续映射,因此,根据Brouwer的不动点定理,对于某些,。换句话说,有些是的质心。因为我们假设没有一个点对F的所有元素都是公共的,所以点并不都是重合的(否则它们将与它们的质心重合,对是公共的)。因此推论1向我们保证,是那些与不同的一些的凸组合。在不丧失一般性的情况下,我们可以重新标记一切,并用表示这些,用 表示F的相应元素。那么我们有

对于某些,其中是到的最近点,。

为了完成证明,我们观察到,由于在集的凸壳中,并且由于在其边界上有的闭半空间,与正交(不包含z)是的支撑半空间,,那么这个族不能有任何共同点(图1说明了的情况)。为了实际证明这一点,我们可以假设而不失一般性。这使我们能够写(见方程式(2)),

那么所有的公共点p也将是所有的公共点,因此将满足 或。因此,gt;,这是一个矛盾,表明不存在这一点p。这就完成了证明。

这个证明的关键是z点的存在。它是具有指导意义的,为证明z的存在性,指出以下等价的论点。对于每个,绘制从x指向的向量,并形成结果。这就在B上产生了一个指向B边界内的连续向量场。根据另一个著名的拓扑理论,这样的场在B内必须有一个“驻点”,即它消失的点z。那么,这正是z是的质心的条件。

4.凸集平移的一些性质

的两个子集和的向量和是形式的所有点的集合,有和。如果和是紧凸集,那么也是紧凸集。在由单个点组成的特殊情况下,向量和是的一个平移,我们有点滥用这个符号来为这个平移写。

如果,是任何实数,那么是形式的所有点的集合,。如果,我们写。如果与的某个平移重合,则是中心对称的。如果存在并且gt;使得,则与是类似的。

的差集被定义为。如果是的紧凸集,则是关于原点中心对称的紧凸集。验证是包含原点的所有平移的并集是一个简单的代数练习。也就是说,

给定,令表示的所有的平移,包含所有的点。也就是说,

是一个紧致凸集,如果K是,并且与K的所有平移的重合一致,K是包含的凸包,注意,特别是,这是K的差集的平移。

的紧子集的直径是它的任何一对点之间的最大距离。众所周知,conv QQ具有相同的直径。注意,这个性质可以用下面的等价形式表示。如果Q是的紧子集,B是球,然后,当且仅当Q的每一对点都能被B的平移所覆盖时,conv Q的每一对点都能被B的平移所覆盖。通过替换B的任意紧凸集K,我们可以得到(正确)的这个结论。这个结论相当于在有限维Banach空间中对于它的单位圆盘,任何集合的直径等于它的凸包的直径。以下引理是这些事实的概括。

引理1Q是的一个子集,K是的一个紧凸子集。设r为固定的正整数。那么conv Q的每一个r点都可以被K的平移覆盖当且仅当Q的每一个r点都可以被K的平移覆盖。

证明 引理的“仅当”部分是平凡的,因为,所以假设Q的每个r点可以被K的平移覆盖,令,那么如果是Q的任意点,我们有。因为可以是Q的任意点,我们有所以因为是凸的。因此,对于每个,都有一个包含的K的平移。对于任何。因为可以是Q的任意点,所以有所以有因此,对于每个,有一个包含的K的平移。用同样的方法,我们得到,所以,对于每一个,有一个包含的K的平移。按照这种方式,我们最终得到了包含的K的平移,并且证明是完整的。

5.Helly定理和万有覆盖

下面的定理可以看作是Helly定理的一个推广(以定理中的为例)。简短而优雅的证明来自于V. Klee[13]。

定理1P是的一个固定紧凸子集,令F是的一个紧凸子集,其性质是F的每n 1个或更少的元素,共同具有P的平移。那么F的所有元素都有一个共同的P的平移。

证明 对于每个F,定义 为,令。那么 是紧致凸集族,使得每n 1个或更少的元素有一个共同点。根据Helly定理,有一个点对于所有的元素都是公共的,然后,对于所有的F。这就完成了证明。

下面的推论可以直接用Helly定理来证明,但我们更喜欢下面的证明,因为它很好地应用了定理1,并提供了上一节的一些思想。

推论2 Q是的一个子集,K是的一个紧凸子集,假设Q的每n 1个点可以被K的平移覆盖,那么Q可以被K的平移覆盖。

证明 通过假设,如果,则有一个含有的K的平移,因此)有一个共同的K的平移。因此,族的每n 1个元素都有一个共同的K的平移,所以它们都有一个共同的K的平移。这个平移包含了每个,证明是完整的。

一个紧凸子集是一个万有覆盖,如果任何有直径

剩余内容已隐藏,支付完成后下载完整资料


资料编号:[409510],资料为PDF文档或Word文档,PDF文档可免费转换为Word

原文和译文剩余内容已隐藏,您需要先支付 30元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。