（运筹学与控制论专业论文）ekr性质研究.pdf

e k r 性质研究 摘要 e k r 定理是组合数学中最基本、最核心的结论之一，其研究对象是有限集 合的子集族上的交性质它的起源可以追溯到1 9 6 1 年e r d 6 s ，k o 和r a d o 的一个 定理：由r , 元集合上的r ( 2 r n ) 元子集构成的具有交性质且基数最大的交簇是 一个星经过几十年的发展，e k r 定理已具有各种形式的推广 同时，e k r 定理还可用图的语言描述为：一个简单图g ，以n 元集合上的 所有r 元子集为顶点，两个顶点相邻当且仅当它们所对应的r 元子集不相交， 此图称为k n e s e r 图，记作i q r ，n ) 则k n e s e r 图的独立数q ( k c r ，礼) ) = ( 肛r - - 1 1 、，并 且k ( r ，n ) 图的最大独立集由均包含一个公共元素的所有，元子集构成因此， e k r 性质的研究就可转换为图的独立集研究，由此引发出了一般图的e k r 性 质研究这一热门课题 本文在前人的工作基础上，继续研究了一些特殊点传递图直积的独立集结 构，解决了如下问题： ( 1 ) 刻画了点传递二部图与任意点传递图直积的独立集结构； ( 2 ) 应用c r o s s 交定理1 2 3 给出了确定图g ( & ) h 的独立集结构的另一 种证明方法： ( 3 ) 给出了对称群圈积晶? 晶的e k r 性质以及由其构成的图g ( & ? & ) 与 任意点传递图直积的独立集结构 关键词：直积；，s 一本原；圈积；独立集；点传递：m i s n o r m a l 1 i ， 厶 i 、 f - 一 s o m er e s e a r c ho ne k r p r o p e r t i e s a b s t r a c t e k rt h e o r e mi so n eo ft h em o s tb a s i ca n dc o r et h e o r e m si nc o m b i n a t o r i c s ，w h o s e r e s e a r c ho b j e c ti st h ei n t e r s e c t i n gp r o p e r t yo nt h es u b f a m i l i e so f f i n i t es e t i t ss o u r c e c a m ef r o mat h e o r e mo fe r d 6 s ，k oa n dr a d oi n19 61 ：i nt h es e to fa l lr - s u b s e t so f n 。s e t ( 2 r n ) ，t h em a x i m a l s i z e di n t e r s e c t i n gf a m i l yi sas t a r a f t e rs e v e r a ld e c a d e s o fd e v e l o p m e n t ，e k rt h e o r e mh a sv a r i o u sf o r m so f p r o m o t i o n m e a n w h i l e ，b yt h el a n g u a g eo fg r a p ht h e o r y , e k rt h e o r e mc a na l s ob es t a t e da s ： as i m p l eg r a p hg ，w h o s ev e r t e xs e ti sa l lo ft h er - s u b s e t so fn - s e t ，a n dt w ov e r t i c e si s a d j a c e n ti fa n do n l yi ft h e i rc o r r e s p o n d i n gr - s u b s e t si sd i s j o i n t 。w es a yt h eg r a p hga s k n e s e rg r a p h ，d e n o t e db yk ( r n ) ，t h e na ( ( ，n ) ) = ( n r _ 1 - 1 ) ，a n dt h em a x i m a l i n d e p e n d e n ts e to fk ( r n ) i sa l lo ft h er - s u b s e t sw h i c hh a v eo n eo ft h es a m ee l e m e n t t h u s t h e r e s e a r c ho ft h ee k r p r o p e r t yc a nb et r a n s f e r r e dt ot h er e s e a r c ho ft h ei n d e p e n d e n ts e t o fg r a p h s t h i sg i v e sr i s et ot h eh o tt o p i co ft h er e s e a r c ha b o u tt h ee k r p r o p e r t yo f g e n e r a lg r a p h s i nt h i sp a p e r , b a s e do nt h ew o r ko ft h ep r e d e c e s s o r s ，w ec o n t i n u e dt os t u d yt h e s t r u c t u r e so fm a x i m a l 。s i z e di n d e p e n d e n ts e t so fs o m es p e c i a lv e r t e x t r a n s i t i v eg r a p h s ， a n ds o l v e dt h ef o l l o w i n g p r o b l e m s ： ( 1 ) t h es t r u c t u r e so fm a x i m a l s i z e di n d e p e n d e n ts e t so ft h ed i r e c tp r o d u c to f v e r t e x - t r a n s i t i v eb i p a r t i t eg r a p ha n da n yv e r t e x - t r a n s i t i v eg r a p h ； ( 2 ) a n o t h e rm e t h o dt oi d e n t i f yt h es t r u c t u r e so fm a x i m a l s i z e di n d e p e n d e n ts e t s o ft h ed i r e c tp r o d u c to fg ( & ) a n d a n yv e r t e x t r a n s i t i v eg r a p h ； ( 3 ) t h ee k rp r o p e r t yo ft h ew r e a t hp r o d u c to ft h es y m m e t r yg r o u pa n dt h e s t r u c t u r e so fm a x i m a l s i z e di n d e p e n d e n ts e t so ft h ed i r e c tp r o d u c to fg ( & 2 & ) a n d a n yv e r t e x t r a n s i t i v eg r a p h k e y w o r d s ：d i r e c tp r o d u c t ；i s p r i m i t i v e ；w r e a t hp r o d u c t ；i n d e p e n d e n ts e t ；v e r t e x t r a n s i t i v e ；mi s v i , o r m c l z i i i ， - r 目录 摘要i a b s t r a c t i i 目录i v 1 绪论1 1 1 前言1 1 2 相关概念及e k r 性质的研究现状3 1 2 1 子集格上的e k r 性质3 1 2 2 着色集上的e k r 性质5 1 2 3 点传递图直积的e k r 性质7 1 2 4c r o s , y , 交上的e k r 性质1 2 1 3 本文的主要研究内容1 5 2 点传递二部图与任意点传递图直积的e k r 性质1 6 2 1 些引理1 6 2 2 定理2 1 的证明1 7 3 对称群s 。的e k r 性质2 0 4 对称群圈积晶? & 的e k r 性质2 4 4 1 图g ( 品2 & ) 的独立数及最大独立集结构2 5 4 2 图g ( r ? & ) h 的独啻= 数及最大独立集结构2 6 参考文献3 0 在学期问的研究成果及发表的论文3 5 致谢3 6 浙江师范大学学位论文独创性声明3 7 学位论文使用授权声明3 7 浙江师范大学学位论文诚信承诺书3 8 i v ，- ， 1 1 前言 1 绪论 1 9 2 8 年s p e m e r 给出了下面这个著名定理。 定理1 1 ( s p e m e r 定理) 设s 是一个n 元集合，4 是s 的一个子集族若对任意 a ，b 4 都有a 垡b ，那么 川( 。妙 并且等式成立当且仅当4 由所有【j 一元子集或i n l 一元子集构成( p 1 表示不小 于。的最小整数，b j 表示不大于z 的最大整数) 由n 元集合s 的所有子集按包含关系构成的偏序集，就是我们熟知的子集 格，记为氏用现代术语来讲，s p e m e r 定理建立了子集格上的s p e m e r 性质然而 这个看似简单的结论却引起了相关学者的极大兴趣，关于它的推广、模拟、精化 以及新证明举不胜举经过近一个世纪的发展，s p e m e r 定理已经发展成为组合数 学中一门系统的理论一- - s p e m e r 理论( 见文献【1 】) 在组合极值理论中与s p e m e r 定理同等著名的还有e r d 6 s ，k o ( 柯召) 和r a d o 在1 9 6 1 年发表的一个结论 定理1 2 ( e r d 6 s k o r a d o 定理) 设4 是由7 , 元集合s 的r - 元子集构成的一个子 集族，其中n 2 r 若对任意a ，b 4 都有anb d ( 么被称为交簇) ，那么 川( 一r - ：) ， 并且等式成立当且仅当- 4 由所有包含一个公共元素的r 元子集构成，这样的么 称为一个星 1 绪论 与s p e r n e r 定理类似，e r d 6 s ，k o r a d o 定理( 简称e k r 定理) 也为有限集上的 组合学发展提供了巨大的推动力该结论自发表以来，得到了不断的发展，如 e r d 6 s 本人和s c h s n h e i m 【2 】给出e k r 定理的因子格的模拟；b o l l o b ：i s 3 】给出 e k r 定理的l y m 不等式的证明，从而引出关于交集的l y m 性质；h s i e h 4 】以及 g r e e n e ，k l e i t m a n 【5 】给出e k r 定理的有限向量空间的模拟；d e z a 和f r a n k l 【6 】给 出e k r 定理的对称群的模拟，oa h l s w e d e ，a y d i n i a n 和k h a c h a t r i a n 【7 】、f r a n k l 8 】 给出子集格直积的e k r 犁结论；h i l t o n 和m i l n e r 【9 】9 首先将子集格上的交性质推 广到c r o s s 一交性质，之后，h i l t o n 【1 0 】又对6 - 甲0 8 8 一交性质进行深入研究，从而引 出了集合上的c r o s s 一交性质有兴趣的读者可参考文献1 9 2 1 1 如果我们以n 元集合上的所有7 元子集为顶点，两个顶点相邻当且仅当它们 所对应的r 元子集不相交，所形成的图便是我们熟知的k n e s e r 图，记作k ( t ，n ) ， 其中n 2 r ，那么子集格上的交簇与k n e s e r 图的独立集就形成了一一对应显 然e k r 定理给出了k n e s e r 图的独立数及最大独立集结构类似的，我们可以在 已定义交性质的集合上构造一个简单图，并且该集合上的交簇与此图的独立集 形成了一一对应，从而交性质的研究便可转换为图的独立集研究，由此引发出 了一般图的e k r 性质研究这一热门课题目前，关于图的e k r 性质研究已有许 多结果，如h o l r o y d 、s p e n c e r 和t a l b o t 【2 2 】给出任意个完全图之并的e k r 性质； h o l r o y d 和t a l b o t 【2 3 】给出两个完全多部图之并的e k r 性质，有兴趣的读者可参 考文献【2 4 _ 2 6 】 然而与s p e r n e r 定理不同的是，e k r 定理经过五十几年的发展，还远未发展 成一门完善的理论例如：( 1 ) s p e m e r 定理已经推广到一般偏序集上，而且对子集 格所用的方法在一般的分次偏序集都有相应的表述，但对e k r 定理却做不到这 一点；( 2 ) 在一般偏序集上，已建立了各种s p e m e r 型性质的直积定理，而对于交性 质的e k r 型直积定理目前存在的只是一些猜想因此，在本论文中，我们主要研 究集合上的交性质 下面将介绍相关概念及e k r 性质的研究现状有时为了叙述方便，我们将采 用图的语言来叙述 2 1 绪论 1 2 相关概念及e k r 性质的研究现状 在本节中，我们主要介绍子集格上的e k r 性质、着色集上的e k r 性质、 点传递图直积的e k r 性质以及c , t 0 5 8 交型e k r 性质的研究现状 1 2 1 子集格上的e k r 性质 记( ，) 为佗元集合上的所有r 元子集构成的集合，t 一交簇c ( 是指： 对任意的a l ，a s 满足l a lna s l t 当t = 1 时，我们简称为交簇记所 有的t 一交簇构成的集合为，( n ，7 _ ，) ，最大一交簇的上界为 m ( n ，r ，t ) = m n z i i ，( 佗，r ，t ) ) i 事实上，在文献【2 7 】中，e r d 6 s ，k o 和r a d o 也给出了子集格上最大t 一交 簇的上界：当n n o ( r ，t ) 时，m ( n ，7 ，t ) = ( r r t 一- t ) ，其中l t 7 n ，n o ( r ，t ) 取适当的值1 9 7 8 年，f r a n k l 【1l 】确定了当t 1 5 时的参数伽( 7 ，t ) 的下确 界紧接着w i l s o n 【1 2 】确定了满足任意正整数t 的参数n o ( r ，t ) 的表达式 n o ( r ，t ) = ( 7 一t + 1 ) ( t + 1 ) 1 9 9 7 年，a h l s w e d e 和k h a c h a t r i a n 【1 6 】刻画了当 7 l l 时的最大非平凡t 一交簇的结构o 定理1 6 ( f r a n k l 1 5 9 设1 t 7 _ 佗，n n l ( r ，) ，其中n l ( r ，t ) 取适当值，则： ( i ) 当t + 1 r 2 t + 1 时，- 砑( 9 2 ，r ，t ) = i v l ( n ，r ，) l ，其中i ) l ( n ，r ，t ) = v ( 掣) ：i 1 ，t + 2 】nv l t + 1 ) ； ( i i ) 当r 2 t + 1 时，丽，7 ，) = i v 2 ( 9 2 ，7 ，t ) l ，其中屹( n ，7 ，) = 【y ( m ，) ： 1 ，t 】v 【1 + t ，r + 1 】nv 仍) u 【l ，7 + l 】一 i ) ：i 【1 ，亡】) 1 9 8 6 年，f r a n k l 和f i r e d i 【1 7 】提出：是否存在常数c ，当n ( t + 1 ) ( r - t + i ) 且7 2 t + l 时，丽( n ，r ，t ) = m a x l 1 ) l ( n ，r ，t ) l ，i 协( n ，r ) 1 ) 2 0 0 8 年，b a l o g h 和m u b a y i 【2 4 】基于f r a n k l 和f i i r e d i 在文献【1 7 】中的思想， 利用压缩算子及w i l s o n 【1 2 】中的一个结论，给出了当扎 ( t + 1 ) ( r t + 1 ) 且 r 2 t 十1 时，最大非平凡t 一交簇结构的简短证明 1 2 2 着色集上的e k r 性质 设集合4 是一个7 元集合，集合b 冬k = 1 ，2 ，k ( k 2 ) ) ，用集合b 中 的颜色给集合a 中的元素着色，显然一种着色方法对应于一个映射：，：a _ b 记由所有的有序对( a ，) 构成的集合为，如果对任意的( 4 ，) ，( b ，g ) ，存 在z anb ，满足f ( x ) = 9 ( z ) ，则我们称为着色集上的交簇 1 9 9 7 年，b o l l o b a s 和l e a d e r 【3 0 】证明了当集合a 为【词上的所有，元集合时 的着色集上的e k r 型结论： 定理1 8 ( b o l l o b a s 和l e a d e r 【3 0 1 ) 设是当集合a 为上的所有7 元集合时的 着色集上的交簇，那么l i k r - i ( n ，一- 1 1 ) ，等号成立当且仅当存在x 0 a ，6 0 【叫， 使得中的所有有序对( a ，) 满足：f ( x o ) = 6 0 如果我们令着色集中的集合a = 【叫，集合b = ，如果要求集合a 中的任 意两个元素着不同的颜色，那么该着色集上的全体着色方式所对应的映射，所形 成的集合便是我们熟知的对称群岛m 个元素上的全体置换作成的一一变换群) 若对任意的盯，r c & ，存在i 【叫，满足o ( i ) = 7 - ( i ) ，则我们称置换盯与丁 相交，为对称群瓯上的交簇 1 9 7 7 年。d e z a 和f r a n k l 【6 】给出了对称群& 上的最大交簇的上界 i i ( n 一1 ) ! 2 0 0 3 年，c a m e r o n 和k u 【3 l 】确定了最大交簇的结构：是 一个具有某一个稳定点的子群的陪集，即对任意的，存在i ，j 【n 】，满足 f ( i ) = j 之后，l a r o s e 和m a l v e n u t o 【3 2 1 ，王军和张俊【3 3 1 分别采用其他方法证明 了该结论有兴趣的读者可参考文献【6 ，3 1 3 4 s 1 绪论 为方便引用，我们将上述结论用图的语言叙述如下：首先在对称群& 上构造 一个简单图g ( & ) ：以对称群岛的元素为项点，两个顶点相邻当且仅当它们所对 应的置换不相交 定理1 9 ( k u 和l e a d e r 【3 1 ，b l a r o s e 和m a l v e n u t o 【3 2 ，王军和张俊【3 3 1 ) 设礼为 正整数，为图g ( 晶) 的独立集，则q ( g ( & ) ) = ( n 一1 ) ! ，且图g 的最大独立集结 构为1 = ，晶：f ( i ) = j ，其中i ，歹【h i 如果我们将上述着色集上的集合a 改为n 元集合上的r 元集合，那么所 有有序对u a ( 【，) ( a ，厂) 所形成的集合便是7 一部分置换相应的，称为r 一部 分置换上的交簇，如果对任意的吼7 ，存在i n 以倒) a ，j m ，满足 o ( i ) = r ( i ) = j 2 0 0 6 年，k u 和l e a d e r 【3 5 1 研究了7 一部分置换上的交簇的上界及最大交簇 的结构：当r 礼一1 时，i i ( n 卜- 1 i ，而( n - 研d ! ，并且当8 7 n 一3 时，等号成立当 且仅当存在i n 倒) a ，j m ，使得中的所有有序对( a ，) 满足：，( i ) = i 同时他们提出如下猜想： 猜想1 1 ( k u 和l e a d e r 【3 5 1 ) 设是r 一部分置换上的交簇且7 n ，则i l 似r - 一1 1 、 亟( n - 型r ) ! ，等号成立当且仅当存在i n ( ，) a ，歹 n l ，使得中的所有有序 对( 月，) 满足：f ( i ) = 歹 2 0 0 7 年，李玉双和王军【3 6 】解决了上述猜想，从而完善了r 一部分置换上的 e k r 型结论 最近，b o r g 【3 7 】确定了着色集上的最大t 一交簇的上界及结构，以及当映射， 为单射时，着色集上的一相交e k r 型结论 定理1 1 0 ( pb o r g 【3 7 】) 设7 ，k ，t 为任意的正整数且t 7 ，记( r ，t ) = ( ：) ( 4 1 ) ， 若对任意的k ( 7 ，) ，及任意的集族满足t q ( ) r ，其中q ( ) 为集族 中最大集合所包含元素的个数，则着色集上最大的t 一相交子集族中每个集合 均包含t 个公共元素 定理1 1 1 ( pb o r g 【3 7 】) 设r ，t 为任意的正整数且t 2 ，图g n 是否也是m i s n o r m a l 的? 该问题已由张华军【4 2 】做出了肯定回答，并指出图g n 是i s - 本原的因为 当图g 为，s 一非本原时，集合bxv ( c ) u 丙【b 】，( g ) 也为图g 2 的最大独立 集，其中x ( c ) 为图g 的最大独立集，集合b 为非本原独立集也就是说，当图g 为，s 一非本原时。图g n 不是m ，s n o r m a l 的 定理1 1 3 ( 张华军【4 2 1 ) 设图g 为点传递的非二部图，若图g 2 是m i s 一扎o r m a l 的，则对任意的正整数n 3 ，图g n 也是m i s n o r m a l 的并且是i s - 本原的 到目前为止，我们已知道t a r d i f 问题中的等式对一些特殊点传递图类是成 立的如( nn ) 图，c i r c ( r ，n ) 图等所谓c i r c ( r ，n ) 图是指其顶点集为，两个 9 l 绪论 顶点i ，歹m 相邻，当且仅当l i 一引 r 或者l n + i j i r 下面先给出图k ( n i ，7 i ，t i ) 的定义o 设佗= n l + + 仡m ，? = 7 1 + + 7 r n ，q = f h + + q m 且i q i i = n i ，其 中，佗，r ，啦，7 i ，i = 1 ，2 ，m 均为正整数，定义 澎邛( ) ：i f nf z d 邓其中2 ，m ) 给定正整数t i ( 其中1 t f i ，1 i m ) ，如果对任意的a ，b c 形， 存在某个正整数i ( 1 i m ) 满足l anb nq i i t i ，则我们称集合a 与集 合b 是( t 1 ，t m ) 相交的，集簇是( t 1 ，t m ) 交簇以彤中的集合为顶 点，两顶点相邻当且仅当它们所对应的集合是( t l ，t 仇) 相交的，记所形成 的图为 兀k ( n i ，n ，t i ) 特别的，当t l = t 2 = = t 。= 1 时，我们简记图 兀k ( n i ，7 i ，t i ) 为兀k ( r t i ，r i ) i 一 i 一 r n l i m 事实上，确定图兀k ( n i ，7 i ，t i ) 的独立数及独立集结构，作为t a r d i f 问题 的一种特殊图类，该问题早已由f r a n k l 提出之后，s a l i 在文献【4 3 】中以子集格上 的交性质的形式正式提出 1 9 9 6 年，f r a n k l 【8 】利用特征值的方法，首先确定了图1 7k ( n i ，7 i ) 的独立 l i m 数，及当n i2 ( 7 i t i + 1 ) ( t i + 1 ) 时，图兀k ( n i ，7 i ，i ) 的独立数： l 2 r 时，k 七r ，佗) 和 c i r c 七r ，n ) 都是m i s n o r m a l 的； ( i i ) ( m a r i ov a l e n c i a p a b o n 和j u a nv e r a 【4 4 ) l kc 嘶 t ，) = m a x 僻磊r 2 n 七 i i n i 1 七 2 0 0 7 年，c h e n gy e a wk u 和t o n yw h w o n g 【4 5 】刻画了若干个图g ( & ) 直积 后的独立集结构： 定理1 1 8 ( c h e n gy e a wk u 和t o n gw h w o n g 【4 5 】) 设h i , 礼2 ，为七个正整 数，并且满足n 1 n 2 1 7 , 七，则 q ( g ( 晶，) c c s 。) g ( 晶。) ) n l 一1 ) 11 7n i ! ， 2 s i s 七 并且直积图g ( & 。) xg ( & 。) x xg ( 晶。) 是m i s 一，l , o r z l 2 a l 的，除非： l l 1 绪论 ( i ) n l = n 2 = = n p = 2 扎p + 1 = 3 饰+ 2 n 口其中l p 尼； ( i i ) n l = n 2 = 3 n 3 n k ； ( i i i ) 7 1 = n 2 = 7 1 3 = 2 n 4 礼七 最近，张华军在其它一些特殊图类上肯定回答了t a r d i f 问题，并刻画了相应 图类的独立集结构 定理1 1 9 ( 张华军 4 6 1 ) 设n ，r 为正整数且礼2 r ，图日是一个点传递图，则 q ( c i r c ( 7 ，仡) h ) = m a x r l h i ，n q ( h ) 并且图c i r c ( r ，扎) h 是m i s n o r m a l 的，除非： ( i ) 哿 2 且。奶，奶，为情形l 或情形2 目前，王军和张华军【2 l 】又将其推广，得到了更一般的结论： 眇i c 持l , 若m m 篡i g - - - - l - i ，。 ( i ) m 器且i 奶i = i 奶i = = l 娠l = ，是图g 上的最大独立集； 1 4 丝r 垫r 一 仇 m 若 若 r 1 七 一 、 v 小吖冲 ，一、j 1 1 l 一 一 n r n 、i_j、liil l 绪论 ( i j i ) r n = 掐且奶，奶，碥为情形l 或情，髟2 ，或者存在一个独立集a 是非 本原的，满足ac 磁， 卅，蟛，a - ) 是一个c r 0 5 8 交簇，同时也是丙f a 】 的一个划分，其中卅= 西一a ，i 【m 】 1 3 本文的主要研究内容 本文在前人的工作基础上，围绕t a r d i f 问题，继续研究一些特殊点传递图类 的独立数及最大独立集结构： 在第二章中，刻画了点传递二部图与任意点传递图直积的独立集结构 在第三章中，应用c r 0 8 8 交定理1 2 3 给出了确定图g ( & ) h 的独立集结构 的另一种证明方法同时应用该定理，给出了定理1 1 8 的另一种证明方法 在第四章中，刻画了对称群圈积& c & 的最大交簇的结构，及由其构成的图 g ( & ? & ) 与任意点传递图直积g ( & 2r ) h 的独立集结构同时利用该结论， 得出若干个图g ( & 2 & ) 直积后的e k r 型结论 1 5 2 点传递二部图与任意点传递图直积的e k r 性质 目前，我们已经知道t a r d i f 问题对于一些特殊的点传递图类是成立的，如 k ( r ，n ) 、c i r c ( r ，礼) 等在本章中，将给出当其中一个图为二部图时，t a r d i f 问题 中的等式也成立，并刻画点传递二部图与任意点传递图直积的独立集结构 首先给出二部图与连通图的概念 定义2 1 若图g