1 凸体与格
假设e1,e2, ,en是n维欧氏空间En的一组标准正交基.也就是说,它们满足
其中,?x,y?表示向量x和y的内积.这时,En中的每一点x都能唯一地表示为
其中,xi被称为x的第i个坐标,通常记为
这时,两点x和y之间的距离可以定义为
定义1.1 假设X是En的一个子集.如果对其中的任意两点x和y以及任意满足0<λ<1的实数λ都有
λx+(1-λ)y∈X,
那么称其为一个凸集.另外,如果它还是一个具有内点的紧集,则称其为一个凸体.
作为一个几何性质,凸意味着如果两点属于该集合,那么连接这两点的整条线段都属于该集合.例如,图1.1的(a)和(b)是凸的,(c)则不是.
图1.1
容易验证,n维空间中的单位球
和单位立方体都是中心对称①的凸体.另外,如果x1,x2, ,xn+1是n+1个不共面的点,那么也是一个凸体,称为一个n维单纯形.通常称
为集合X的凸包.换句话说,凸包是包含该集合的*小凸集.例如,三角形就是它的3个顶点的凸包,而圆盘则是它的边界圆周的凸包.
为了方便,在今后的论述中用K表示一个n维凸体,用v(K)表示它的体积,用C表示一个中心对称的n维凸体.
关于凸体有许多既重要又有意思的结论,在这里介绍两个作为例子.
Helly定理 假设F是En中的一族凸体.如果其中的任意n+1个凸体都有公共点,那么
证明思路 零维(只有一个点)的情况是显然的.假设该定理在En-1是正确的,进而证明它在En也是正确的.
用反证法.如果F有一个子集合G和一个凸体K0同时满足
容易看出,B一定是一个凸集合.这时由凸集合的基本性质一定存在一个超平面H将K0和B严格分开.
假设K1,K2, ,Kn是G中的任意n个凸体,由上述假设可得.
事实上,如果,那么
这样,由归纳假设可以导出
显然,它与H将K0和B严格分开相矛盾.Helly定理得证.
注1.1 从图1.2及其高维推广可以看出Helly定理中的n+1是*佳的.
注1.2 这一定理不仅与著名的Carathé Godory定理①以及Radon定理②等价,并有许多重要的推广和应用.例如,Brny,Katchalski和Pach曾证明了如下推广:假设F是En中的一个由有限个凸体组成的集合.如果F中的任意2n个凸体的交集的体积都不小于1,那么F中的所有凸体的交集的体积一定不小于n-n2.相关参见文献(Danzer et al.,1963;Eckhoff,1993).
图1.2
注1.3 E.Helly(1884~1943),奥地利数学家,曾任维也纳大学讲师,后移民美国.生前仅发表6篇数学论文,没有得到应有的学术地位和荣誉.后来,由他*先发现并以他的名字命名的Helly定理被许多著名数学家进一步地推广和应用,成为组合几何学中的一颗明珠.
接下来介绍John定理.*先观察一个例子.
例1.1假设T是一个三角形,如图1.3(a)所示一定可以找到一个椭圆E满足
如果P是一个平行四边形,那么如图1.3(b)所示总可以找到一个椭圆E?满足
图1.3
基于这一观察,自然会问:是否每一个凸体都会夹在两个成适当比例的椭球之间?实际上,有如下结论:
展开