（计算数学专业论文）偏序集上的组合学中的几个问题.pdf

大连理工大学博士学位论文 摘要 论文主要研究d y c k 路偏序集的m 6 b i u s 函数和着色布尔格的交性质 本文第一部分研究d y c k 路偏序集的m s b i u s 函数计算及其应用d y c k 路偏 序集的序关系为模式包含( p a t t e r nc o n t a i n m e n t ) 关系论文首先给出d y c k 路的序列 表示d y c k 序列，从中可以看到d y c k 路偏序集是s a g a n 和v a t t e r 定义的扩展子 字序的特殊情况，但包含他们重点研究的整数有序分拆偏序集作为特例根据这个 观察可直接推出d y c k 路偏序集的m s b i u s 函数采用结构分解的办法建立秩函数的 m s b i u s 反演公式，得到偏序集秩函数的另一种表达最后证明其中一类子偏序集具 有秩单峰性和s p e r n e r 性质 本文第二部分研究偏序集的交性质首先定义一个一般性的概念一着色布尔 格，它是普通的布尔格的一种推广，并且包含b o u o b h s 和l e a d e r 定义的哥符号集 合( 文中称为全着色集) 偏序集以及k u 和l e a d e r 定义的部分置换( 文中称为单着色 集) 偏序集作为特例本文建立单着色布尔格的交反链的一个l y m - 型不等式，由 该不等式可立即推出k u 和l e a d e r 给出的k 一部分置换交族的e k r 定理，并证明他 们提出的关于缸部分置换交族极值结构的唯一性的猜想；给出着色布尔格的又一 个特例一无不动点着色布尔格，证明它具有e k r 性质，交族极值结构的唯一性以 及交反链的一个l y m - 型不等式；建立着色直积的交性质的一个一般性定理最后 给出置换( 单着色m 集) 的交性质的k a t o n a - 型证明 关键词；d y c k 路偏序集；着色布尔格；m s b i u s 函数；e r d s s - k o - r a d o ( e k r ) 定理； 唯一性；l y m - 型不等式 偏序集上的组合学中的几个问题 s e v e r a lp r o b l e m si nc o m b i n a t o r i c so fp o s e t s a b s t r a c t t h i st h e s i si n v e s t i g a t e st h em s b i u sf u n c t i o no fd y c kp a t hp o s e t sa n dt h ei n t e r s e c t i n g p r o p e r t yo fc o l o r e db o o l e a nl a t t i c e s t h ef i r s tp a r to ft h i st h e s i sc o n t r i b u t e st ot h ec o m p u t a t i o na n da p p l i c a t i o n so ft h e m s b i n sf u n c t i o no fd y c kp a t hp o s e t s t h ed y c kp a t hp o s e ti so r d e r e db yp a t t e r nc o n t a i n - m e r i t as e q u e n c er e p r e s e n t a t i o no fd y c kp a t h si sp r e s e n t e d ，w h i c hs h o w st h a tt h ed y c k p a t hp o s e ti sas p e c i a lc a s eo ft h eg e n e r a l i z e ds u b w o r do r d e rd e f i n e db ys a g a na n dv a t t e r b u tc o n t a i n st h ec o m p o s i t i o np o s e ra sas u b p o s e t ，t ow h i c hs a g a na n dv a t t e rp a i dm o r e a t t e n t i o n n o mt h i si tf o l l o w st h em s b i u sf u n c t i o no ft h ep o s e ta n dt h em s b i n si n v e r s e o ft h er a n kf u n c t i o n ，w h i c hd e r i v e sa n o t h e re x p r e s s i o no ft h er a n kf u n c t i o n i nt h ee n d ，a k i n do fs p e r n e ra n du n i m o d a ls u b p o s e ti sg i v e n t h es e c o n dp a r to ft h i st h e s i sr e s e a r c h e st h ei n t e r s e c t i n gp r o p e r t yo fp o s e t s t h e a u t h o r sf i r s ti n t r o d u c eag e n e r a lc o l i c e p 扛q h ec o l o r e db o o l e a nl a t t i c e ，w h i c hi sa ne x t e n - s i o no ft h en o r m a lb o o l e a nl a t t i c e ，a n di n c l u d e st h ep o s e to fq - s i g n e ds e t si n t r o d u c e db y b o l l o b 缸a n dl e a d e r ( c a l l e df u nc o l o r e db o o l e a nl a t t i c ei nt h et h e s i s ) a n dt h ep o s e ro f p a r t i a lp e r m u t a t i o n si n t r o d u c e db yk ua n dl e a d e r ( c a l l e di n j e c t i v ec o l o r e db o o l e a nl a t t i c ei nt h et h e s i s ) t h ea u t h o r se s t a b h s ha l y m t y p ei n e q u a l i t yf o rt h ei n j e c t i v ec o l o r e d b o o l e a nl a t t i c e ，w h i c hd e d u c e st h ee k rt h e o r e mf o rk - p a r t i a lp e r m u t a t i o n sg i v e nb yk u a n dl e a d e ri m m e d i a t e l y , a n ds o l v et h e i rc o n j e c t u r eo nt h es t r u c t u r eo fm a x i i n a i n t e r s e c t - i n gf a m i l i e s ；t h et h e s i sg i v e sa n o t h e re x a m p l eo fc o l o r e db o o l e a nl a t t i c e - - - f i x e d - p o i n tf t e e c o l o r e db o o l e a nl a t t i c e ，p r o v e si t se k rp r o p e r t y , t h eu n i q u e n e s so fi t sm a x i m a li n t e r s e c t i n gf a m i l i e sa n d a nl y m - t y p ei n e q u a l i t yo fi t si n t e r s e c t i n ga n t i c h a i n s ；t h ed i r e c tp r o d u c t o fc o l o r i n g s ( a ss e t s ) i sa l s od i s c u s s e d a tl a s t ，t h ea u t h o r sg i v eak a t o n 扣t y p ep r o o ff o r i n t e r s e c t i n gp e r m u t a t i o n s k e y w o r d s ：d y c kp a t hp o s e t ；c o l o r e db o o l e a nl a t t i c e ；m s b i u sf u n c t i o n ；e r d s s - k o - r a d o ( e k r ) t h e o r e m ；u n i q u e n e s s ；l y m - t y p ei n e q u a l i t y i i 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或者其他单位的学位或证书所使用过的材料与我一同工 作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意 作者签名： 大连理工大学博士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权 使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印 件和电子版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段 保存和汇编学位论文 作者签名丝 导师签名 薹迢 超盟年j 月堕日 大连理工大学博士学位论文 1 绪论 1 1 记号、术语和基本结论 设p 是一个非空集合，如果在p 的元素中有一个二元关系“”满足； ( 1 ) 自反性：对任一$ p 有茹s ， ( 2 ) 反对称性：。y ，y sz 商z = y ( 3 ) 传递性；。y ，y z 毒$ z ， 那么“ ”称为p 上的一个偏序，p 连同此偏序“”称为一个偏序集，记为( p ，) 在不引起混淆的情况下，常把( p ，) 简记为p 对为y p ，如果z y 或y z ， 就说。与y 在偏序“9 下是可比较的；否则。与y 是不可比较的如果。y 但 击y ，则记为z y 当z y 且不存在z p 使得。 z y ，则称f 覆盖z ，记为 z y 对。p ，如果y p 和y x 蕴涵y = 霉，那么就说z 是p 的一个极小元类 似地有极大元的概念 设p 和p ，是两个偏序集，如果存在一个双射庐：p p 7 使得在p 中z y 当 且仅当在中( z ) ( ) ，那么就说咖是从偏序集p 到p 7 的一个( 保序) 同构，p 与 p 7 称为是同构的偏序集p 的一个自同构是指从p 到p 的一个同构 设p q 为两个偏序集且q p 如果对任意z ，y q ，在q 中z y 当且仅当 在p 中sy ，那么偏序集q 称为偏序集p 的子偏序集当z y 时，( 闭) 区间 p ，y 】_ p p ：z 。疗是p 的一类特殊子偏序集( 空集不是一个区间) 如果p 的每个区间都是有限的，则说p 是局部有限偏序集一个局部有限偏序集p 完全 由它的覆盖关系所决定有限偏序集尸的h a s s e 图是这样一种图：它的结点是p 的 元素，它的边就是覆盖关系，满足如果z y ，则y 被画在z 的上面 如果存在一个元素6 p 使得z 之o 对所有的z p 成立，我们说偏序集p 有 1 偏序集上的组合学中的几个问题 一个6 类似地，如果存在一个元素i p 使得。i 对所有的z p 成立，我们说 p 有一个i 用户表示p 并上6 和i ( 尽管p 可能已经存在6 和i ) 设，是p 的一个子偏序集，若，中任意两个元素都是可比较的，那么就说 ，是p 的一条链，其长记为i ，l 一1 ；若，中的元素是两两不可比较的，那么就说 ，是p 的一条反链如果在链，= z os 宝1 。) 中，对1 l 恒有 瓤覆盖。l 一1 ，则说，是饱和链p 的最长的饱和链称为极大链如果p 的所有 极大链都有相同的长度n ，则说p 是秩为竹的分次偏序集，此时p 存在一个秩函 数p ：p ， 0 ，1 ，n ) ，满足当z 是p 的极小元时，p ( x ) ；0 ；当y 覆盖z 时， p ( y 1 = p ( x ) + 1 称p 中秩为1 的元素为原子本文所涉及到的偏序集均是分次的 对p 的一个子集，如果。i 并且y z 有y i 成立，则说j 是p 的一 个序理想当p 有限时，p 的所有反链，与所有序理想f 之间存在一个一一对 应，即，是j 的极大元的集合，此时j = 协p ：z y ，f 刀，称f 生成j ，如果 ，= 和1 ，吼 ，则记i = ( z 1 ，o k ) ；如果，= ( z ) ，则序理想i = ( z ) 被称为由z 生成的主序理想 设。，口p ，如果存在2 p 使得。z ，。y ，那么z 称为z ，y 的一个下界 如果对毛口的其它下界u 均有usz ，那么。称为z ，y 的最大下界类似地有最小 上界的概念如果p 中任意两个元素均有最大下界和最小上界，那么就说p 是一 个格有限格p 是一个半模格，如果它满足下面两条中的任意一条 ( i ) p 是分次的；对所有的z ，f p ，秩函数p 满足p ( 。) + p ( ) p p 2 ，) + p v ) ( i i ) 如果。和y 都覆盖z a ，那么vy 都覆盖z 和y 有限格p 是一个模格当且仅当它是分次的，且对所有的y p ，秩函数p 满足 p ( x ) + p ( y ) = p ( x ay ) + p ( x v 口) 如果p 的每个元素都是一些原子的并，则称p 为 原子格如果p 既是有限半模格，又是原子格，则称p 为有限几何格如果格p 满 足分配律z v ( y a ：) = p v y ) a p vz ) ，z a 国vz ) = p a y ) v p az ) ，则称p 为分配 格偏序集p 的序理想格j ( p 1 就是一个分配格序理想的格运算v 和a 就是普通 的并与交运算( 看作p 的子集) 对于格p 的一个元素z ，如果它不能写成z = y v z ， 这里y 。，2 z ，则称它为并不可约元( 交不可约元可做对偶定义) 偏序集p 的 序理想，在，( p ) 中是并不可约的当且仅当它是p 的主序理想 设p 是局部有限偏序集，p 的m s b i u s 函数p 可递归地定义为 p ( z ，正) = 1 ，对所有的z p 2 ( 1 1 1 ) 大连理工大学博士学位论文 肛( z ，) = 一i d ( x ，z ) ，对所有的t y x z y 这里肛( 而) 表示p ( p ，】) 下面列举了较为常见的偏序集的m 6 b i u s 函数： ( 1 ) 链n 的m s b i u s 函数为 f 1 如果i = j ； u ( i ，j ) = 一1 如果i + 1 = j ； l0 其它 ( 2 ) 秩为n 的布尔格的m 6 b i u s 函数为p ( l s ) = ( - 1 ) 1 s - t i ，如果t s ( 3 ) p = n 1 + 1 xn 2 + 1x n k + 1 ，其中竹1 ，n 2 ，n k 是非负整数它的 m 6 b i u s 函数为 p ( ( 0 1 ，o ) ，( b l ，b k ) ) ：( 一1 ) 以一“如果每个 = 或l ； ( 1 1 ，2 ) ：7 r l i l l l b i - a i 0 【0口h ， 、7 如果n = p ? 。p 孤这里p 是不同的素数，则p 同构于的因子格( 的 正因子在整除关系下构成的偏序集) ，这时，( 1 1 2 ) 具有如下形式： p s ) = 扩”罂蠡，；是。个不同素数的乘积； 即p ( r ，5 ) 是数论中经典的m 6 b i u s 函数p ( s r ) ( 4 ) p 是q 元域上的 维向量空间，这里q 是素数的方幂它的m s b i u s 函数为 h = ( 一1 ) n 口( ；) ( 5 ) p 是有限集合s 的所有分拆在加细序下构成的偏序集它的m s b i u s 函数为 p 。= ( 一1 ) “一1 ( n 一1 ) ! 设p 是秩为n 的分次偏序集，对0 msn ，记p = 和p ：p ( z ) = m ， = ( p ) = i p m i 称，为p 的第m 个秩集，矸，m 为p 的第m 个秩数或第 m 个w h i t n e y 数函数f ( t ) = 昂( t ) = ”m ：o w m t 称为p 的秩生成函数如果存在 0 l n ，使得 w o w 1 s w - 一1 h - 2 w l + 1 2 w 名， 则说p 是秩单峰的如果对所有0 m n 均有w m = 矸0 一。，则说p 是秩对称 的 3 偏序集上的组合学中的几个问题 为了方便起见，对秩为n 的分次偏序集p ，以事瓦一1 = 厩一1 ( p ) 表示p 的第i 个 最大w h i t n e y 数( 相应的秩集称为p 的第i 个最大秩集) ，那么一w 0 一w 1 p 吒 设，p ，如果在，中不存在k ，链，则说，是p 的一个女一族特别地，1 一族即 反链，而任意k 个秩集的并是p 的一个k 族另一方面，易知p 的每个女族都是 p 的( 不超过) k 个反链的并p 中含元素个数最多的，族称为p 的一个s p e r n e r “族用氐( p ) 表示p 的s p e m e r k 一族所含元素个数，d 1 ( p ) 称为p 的d i l w o r t h 数 如果如( p ) = 譬厩，即p 中k 个最大的秩集的并是p 的一个s p e m e rk 族，则 说p 是k - s p e m e r 的1 - s p e r n e r 的简称为s p e r n e r 的如果对所有的k21 ，p 都是 k - s p e r n e r 的，则称p 具有强s 卵m e r 性质 给定一个原子a 尸l ，定义p i ( a ) ：= 缸只iz n ，称p ( o ) 是一个i 一星令 ，p 如果，只，则称，是i - u n i f o m ；如果，中的每对元素都有一个秩1 的 公共下界，则称，是一个交族；如果，既是交族又是一条反链，则称芦是一条交 反链 如果对每个- u n i f o r m 交族，都满足 ，i 搿l 毋( 。) i ， ( 1 1 3 ) 则称p 具有秩i 上的e k r 性质如果p 在每一秩集只上都具有秩i 上的e k r 性 质，则称它具有e k r 性质如果( 1 1 3 ) 中的等式成立蕴含，= 0 ( 口) 对某个d p l ， 则称p 具有秩i 上的唯一性如果p 在每一秩集只上都具有秩i 上的唯性，则称 它具有交族极值结构的唯一性设，是秩为n 的偏序集尸中的任意一条交反链 对1 n ，令九= i ，n p k i ，n k = m a p l i p k ( 酬) 如果：】惫s1 ，则称p 满足秩i 上的l y m - 型不等式( 注：本段的概念是为了论文内容叙述的方便而定义 的，对于一般的偏序集可能不适用) ， 1 2 历史背景 有限集合上的组合结构的计数和枚举是组合数学的主要研究方向之一，有限或 局部有限偏序集在组合计数中具有重要的统一作用( s t a n l e y 在他的著作e n u m e r - a t i v ec o m b i n a t o r i c s 第一卷【7 6 】第三章中详细地介绍了这方面的内容) ，它们的结构 性质也是组合数学中内容丰富的研究课题本文主要研究局部有限偏序集的m s b i u s 函数和有限偏序集的交性质 ( 一) 正如我们在上一节看到的，偏序集的m s b i u s 函数是数论中经典的m b b i u s 函数的推广，它现在的这种形式是权威的组合数学家r o t a 于1 9 6 4 年在他著名的系 4 大连理工大学博士学位论文 列文章组合论基础”中的第一篇“m s b i u s 函数理论”【6 8 】中引进的，这样一来，各种 经典的反演问题都可以纳入偏序集的m s b i u s 反演的框架由于偏序集p 的m s b i u s 函数可看作是p 的序复形的一个欧拉示性数，这就使得m 6 b i u s 反演与代数拓扑这 个强有力的工具联系起来因此，偏序集的m s b i u s 函数的计算和应用一直是组合 学家非常感兴趣的课题 为了实现m 5 b i u s 反演理论在组合计数方面的强大功能，计算偏序集的m s b i u s 函数就显得至关重要了 自r o t a 【6 8 于1 9 6 4 年给出几何格的m 6 b i u s 函数以后，s a g a n 6 9 】于1 9 9 5 年将 r o t a 的结果推广到一类更大的格；紧接着b l a s s 和s a g a n ( 1 9 9 7 ) 1 0 又将其推广到 任意格；b o g a r t ，b r y l a w s k i ，g r e e n e 1 1 ，1 5 ，3 8 给出主导序下整数分拆格的m 6 b i u s 函 数；g r e e n e 3 7 给出s h u f f l e 偏序集的m 6 b i u s 函数；b j 5 r n e r 9 ，8 先后给出子字序的 m s b i u s 函数，确定出因子序m s b i u s 函数的取值范围并给出递推原则；p t k ( 1 9 9 6 ) 【6 5 】给出移位和极值算子的m s b i u s 函数；p u t c h a ( 2 0 0 4 ) 6 6 1 给出c r o s s - s e c t i o n 格的 m 5 b i u s 函数 尽管我们已经知道了许多具体的偏序集的m s b i u s 函数，但是对于一般的偏序 集目前还没有一种简单的方法来计算它的m 5 b i u s 函数，有些偏序集的m 6 b i u s 函数 的计算是非常困难的 作者对m 6 b i u s 函数的研究始于w i l f 【8 3 于2 0 0 2 年提出的问题令& 表示集合 m 上的全体置换构成的对称群，s = u 。1 对于z = ”( 1 ) w ( 2 ) ( n ) ，口= 口( 1 ) 口( 2 ) a ( m ) s 。，如果有指标i 1 i 2 。使得子序列7 r ( i l ) 7 r ( i 2 ) 7 r a 。) 和一( 1 ) 一( 2 ) ，( m ) 有相同的大小关系，则称”包含一个，模式，记为”a ，这个 子序列称为口中的一个口复制例如；3 1 2 2 4 1 5 3 因为2 4 1 5 3 申有一个3 1 2 复制 4 1 3 这个模式包含关系是定义在s 上的一个偏序( 置换模式是一个迅速发展的研 究课题，关于置换模式的综合评述读者可参考 1 4 】图l 1 给出在模式包含序下置换 区间 1 ，3 1 5 2 4 的h a s s o 图) w f l f 的问题是；这个偏序集的m s b i u s 函数是什么? 为了解决w i l l 提出的问题，s a g a n 和v a t t e r 7 0 】在2 0 0 6 年给出了整数有序分 拆在模式包含关系下的m s b i u s 函数令p 表示正整数的集合，p + 是字母取自p 中元素的字的集合，即 p = 伽= w ( a ) w ( 2 ) ( n ) jn 0 ，对所有的 满足( ) p ， 用表示”的长度n 在p 中定义一个偏序：“”如果”有一个长度为f _ “i 的子字 ( l 灿( i 2 ) ( f ) 使得u ) ( 略) ，j = 1 ，2 ，f 例如，4 4 2 s5 3 4 1 2 ，因为 后者有子字5 4 2 实际上，整数有序分拆上的模式包含序与b j s r n e r 【9 】的子字序是 5 偏序集上的组合学中的几个问题 3 l5 2 4 ln 1 4 2 3 2 4 1 33 1 2 4 2 1 4 3 3 1 4 2 1 图1 1 在模式包含序下置换区间【1 ，3 1 5 2 4 的h a s s e 图 非常相似的，文献 7 0 】给出了详细的锯释下面给出整数有序分拆偏序集的m s b i u s 函数 定理1 1 ：( s a g a n 和v a t t e r ) 令p 4 表示整数有序分拆在模式包含关系下构成的偏序 集如果“，w p ，则 p ( “， ) = ( 一1 ) 8 ， 钆 这里的和取遍所有的u 到w 的正规嵌入钆( 详见【7 0 1 ) 我们知道整数有序分拆和分层置换之间是一一对应的给定两个置换w & ，一 s _ 。，它们的直和是一个长为m + n 的置换，它的前m 个元素构成了一，后n 个元 素是一个霄复制7 r ”) - ，( 2 ) r ( n ) ，这里”俅) = ”( ) 十m ，i = 1 ，2 ，竹例如， 1 3 2o3 2 1 4 5 = 1 3 2 6 5 4 7 8 如果一个置换能表示成几个递减置换的直和，则称它为分 层置换熟知，一个置换是分层置换当且仅当它既不包含2 3 1 一模式也不包含3 1 2 - 模式易见前面的例子是分层的，因为1 3 2 6 5 4 7 8 = 1 02 1 03 2 1 01 0 1 明显地， 长为n 的分层置换的集合与n 的有序分拆的集合存在一一对应，如1 3 2 6 5 4 7 8 对应 8 = i + 2 + 3 + 1 + 1 显然，这个双射把置换上的模式包含序传递给了整数有序分 拆，从这个角度上来讲，s a g a n 和v a t t e r 的结论部分地解决了w i l f 的问题 子字序与整数有序分拆偏序集的m s b i u s 函数的相似性使得s a g a n 和v a t t e r 提 出了一个更一般的序一扩展子字序令( p ，p ) 是任意一个偏序集p + 上的扩展 子字序是这样一种偏序；p w ，如果w 包含一个子序列w ( i i ) ，w ( i 2 ) ，w ( i 。) 6 3 大连理工大学博士学位论文 使得u ( j ) - v ( 0 ) ，1 j m = m 显然，b j s r n e r 的子字序及s a g a n 和v a t t e r 的 整数有序分拆序都是一种扩展子字序文献 7 0 】也给出了扩展子字序的m s b i u s 函 数，即； 定理1 2 ：( s a g a n 和v a t t e r ) 令p 是一个带根的森林，则扩展子字序p 的m s b i u s 函 数为 u ( u ，t ，) = ( 一1 ) 8 ( 毗) ， 咖 这里的和取遍所有的u 到w 的正规嵌入钆( 详见【7 叫) ， 与置换、整数有序分拆密切相关的组合对象之一就是d y c k 路半长为n 的d y c k 路是一条起始于原点( 0 ，o ) ，由升步( 1 ，1 ) 和降步( 1 ，一1 ) 组成，终止于点( 执，o ) ，并只 在第一象限的格路，简称d y c kn 一路众所周知d y c km 路与集合m 上避免三个数 字的置换( 如避免3 1 2 的置换s n ( 3 1 2 ) ) 之间有一一对应关系( 可参考文献【5 】) ，而不 含外对的d y c km 路又与n 的有序分拆之间存在一一对应关系置换，整数有序分 拆、d y c k 路三者之间的关系使我们很自然地想到：在d y c k 路上如何定义模式包含 序来得到类似定理1 1 ，1 2 的结论一旦给出这样的结果，它会带给我们哪些应用 呢? 论文的第二章回答了这些问题 ， ( 二) 在介绍e r d s s - k o - r a d o ( e k r ) 定理之前，我们先来介绍s p e r n e r 7 4 于1 9 2 8 年给出的一个著名结果，现在称之为s p e r n e r 定理：设s 是n 个元素的集合，是 s 的个子集族使得其中任意两个子集互不包含，则 旧( m t i , 】) ， 等号成立当且仅当，由所有i n 2 一子集构成l u b e u ，y a m a m o t o 和m e s c h a l k i n 分 别给出了一个比s p e r n e r 定理更强的结果一l y m 不等式( 可参阅文献【2 5 】了解更 详细的介绍) 它讲述的是如果，是n 元集合的子集的反链，那么有趋。裔s1 ， 这里 表示在，中阶为k 的子集的个数该不等式给出了s p e r n e r 定理的一个简 单证明s p e r n e r 的这个结果建立了布尔格b 托的s p e r n e r 性质然面这个看起来很 简单的结果却引起了数学家极大的兴趣，并被不断地推广，以至于形成了组合数学 中一个独立的分支 与s p e r n e r 定理类似，e r d s s ，k o ( 柯召) 和r a d o 进一步给出；若，是s 的一个 k 子集族使得其中任意两个子集交非空，其中k n 2 ，则 旧s ( 一k - ；) ， 7 偏序集上的组合学中的几个问题 并且这个界可以达到这就是与s p e r n e r 定理同样著名的e r d s s - k o - r a d o 定理，简 称e k r 定理根据文献 2 6 介绍，他们在1 9 3 8 年就已经证明了这个定理，但直到 1 9 6 1 年才发表( 2 9 1 e k r 定理是研究有限集的交族的最早结果，也是组合极值理论 中最著名的结论之一h i l t o n 和m i l n e r 4 2 】于1 9 6 7 年给出了e k r 定理中极值结构 的描述，即当k 号时，= 似：a cs ，i a i = k ，z a ) ，其中2 是s 中的一个固 定元 类似于l 不等式，b o l l o b 缸f 1 2 】于1 9 7 3 年建立了一个比e k r 定理更强的 结果一交族的l y m - 型不等式；当k n 2 时，如果，是n 元集合的子集的交反 链，那么有k ，7 ；1 ，这里 表示在，中阶为的子集的个数由这个不等 式我们可以直接得到e k r 定理1 9 7 6 年g r e e n e k a t o n a 和k l e i t m a n 3 9 】采用圈序 的方法给出这个定理的简单证明最近，w a n g 和z h a n g 8 2 采用移位算子的方法 给出这个不等式的新证明 在过去的四十多年里，e k r 定理不断被推广、模拟和加细，文献 2 2 ，2 8 】对 此散了较为全面的介绍值得一提的是a h i s w e d e 和k h a c h a t r i a n1 2 ) 于1 9 9 6 年证明 了集合系的完全非平凡交定理后又于1 9 9 7 年 1 】彻底解决了f r a n k l 关于极大亡- 交 族结构的著名猜想；m u b a y i 和v e r s t r a t e 【6 4 1 于2 0 0 5 年彻底解决了e r d & 关于集 合系里三角形的猜想除了在集合系中研究交性质外，许多学者给出了e k r 定理 的模拟和极值结构的刻画：h s i e h ( 1 9 7 5 ) 4 5 】证明了有限向量空间的子空间模拟； l i v i n g s t o n ( 1 9 7 9 ) 1 5 4 证明了有序集合的模拟；l a n k l 和f i i r e d i ( 1 9 8 0 ) 【3 4 】，f r a n l d 和t o k u s h i g e ( 1 9 9 9 ) 3 5 】证明了整数序列的模拟；m o o n ( 1 9 8 2 ) 6 2 证明了h a m m i n g s c h e m e s 的模拟；r a n & ( 1 9 8 2 ) 6 7 j 证明了 设计的模拟；a h l s w e d e ，a y d m i a n 和 k h a c h a t r i a n ( 1 9 9 8 ) 3 证明了直积的交定理；b e y 分别在文献( 1 9 9 9 ) 6 j 和( 2 0 0 1 ) f 7 j 中证明了函数格的模拟和加权集合的模拟；e r d s s ，s e r e s s 和s z k e l y ( 2 0 0 0 ) 3 1 l 证明 了偏序集中交链的模拟；k u ( 2 0 0 4 ) 5 0 研究了置换和部分置换的模拟； m e a g h e r 和m o u r a ( 2 0 0 5 ) f 5 z 证明了集合分拆系的模拟；m u b a y i ( 2 0 0 5 ) 6 3 证明了三集合的 模拟；h o l r o y d 和t a l b o t ( 2 0 0 5 ) 【4 3 研究了具有交性质的图 e k r 定理的原始证明用的是移位( s h i f t ) 方法，k a t o n af 4 6 】于1 9 7 2 年给出该 定理的一个漂亮的证明，该证明中引进圈序方法，通过该方法一般可以建立交族的 l y m - 型不等式有关方法的具体介绍可参考文献| 4 0 1 k a t o n a 的圈序方法以它特有的魅力吸引着众多学者去探寻各类组合对象交性 质的k a t o n a ，型证明例如b o h o b 缸和l e a d e r ( 1 9 9 7 ) ( 1 3 】证明口一符号集合交族的 e k r 定理；k a t o n a ( 1 9 9 s ) 1 4 7 1 证明m i l n e r 定理( 1 9 6 s ) 1 6 1 ) ；以及h o w a r d k 宣r d l y i 和 s z d k e l y ( 2 0 0 1 ) 【4 4 】证明二交的e k r 定理 8 大连理工大学博士学位论文 本文研究着色布尔格( 一种有限偏序集) 的交性质这项研究始于d e z a 和f r a n k l ( 1 9 7 7 ) 【2 3 关于置换交族以及k u 和l e a d e r ( 2 0 0 6 ) 4 9 关于部分置换( p a r t i a lp e r m u - t a t i o n s ) 交族所做的工作 用& 表示 n 上的对称群称岛的一个子集s 是相交的，如果对任意两个置 换g ，h s ，集合 z ：9 ( z ) = ( z ) ) 定理1 3 ：( d e z a 和f r a n k l 【2 3 ) 令s 晶是一个交族，则i s l 一1 ) ! ，且这个界是 可以达到的 该定理没有进一步刻画最大交族的结构大约二十六年以后，c a m e r o n 和k u ( 2 0 0 3 ) 1 6 】以及l a r o s e 和m a l v e n u t o ( 2 0 0 4 ) 5 3 】分别解决了这个问题 定理1 4 ：( c a m e r o n 和k u 1 6 ，l a r o s e 和m a l v e n u t o 5 3 ) 定理1 3 中的等式成立当且 仅当s 是某一点的稳定子的一个陪集 事实上，采用文献 1 6 】和 5 3 中所使用的点传递图的方法可以很容易地证明定 理1 3 ，然而定理1 4 的证明是较困难的在证明定理1 4 时，c a m e r o n 和k u 采用 了固定算子这个递归技巧最近，w a n g 和z h a u g 【8 1 给出定理1 4 一个非常简单 的证明 作为置换交族的一个推广，k u 和l e a d e r 【4 9 】考虑了部分置换的交性质m 上 的一个一部分置换是一个对( a ，) ，这里a ，j a i = k ，：a m 是一个单射 注意m 上的一个m 部分置换恰好就是上的个置换部分置换构成的族，是 相交的，如果对任意的( a ，) ，( b ，g ) ，存在一个z a nb 使得，p ) = g ( z ) 定理l 5 ：( k u 和l e a d e r ) 固定k ，n ，这里k n 一1 令，是一部分置换构成的交 族。则 旧( 一k - ：) 矧 k u 和l e a d e r 采用圈序与固定算子相结合的办法证明了定理1 5 ，并且刻画了部 分交族的极值结构 定理1 6 ：( k u 和l e a d e r ) 当8 墨n 一3 时，定理1 5 中的等式成立当且仅当，由 所有这样的k 一部分置换( 月，) 构成，x 0 a 且，( x o ) = 5 0 对某一固定的岳me 0 川 同时他们提出 9 偏序集上的组合学中的几个同题 猜想1 1 ：( k u 和l e a d e r ) 定理1 6 对所有的1 k 曼一1 均成立 促使k u 和l e a d e r 研究部分置换交族的一个主要因素是b o l l o b 6 s 和l e a d e r ( 1 9 9 7 ) 1 3 】给出的q - 符号集合( q - s i g n e ds e t s ) 交族的e k r 定理一个q 一符号k 一集 合是一个对( a ，) ，这里a m 是一个k 一集合，是一个从4 到【g 】的映射q 一 符号k 集合构成的族，是相交的，如果对任意的( a ，) ，( b ，9 ) ，存在。a n b 使得( x ) = 9 ( z ) 定理1 7 ：( b o l l o b a s 和l e a d e r ) 固定一个正整数k 令，是m 上的一个q 一符号 k 一集合交族，这里q22 ，则i ，l ( k n 一- - 1 1 ) g 除了q = 2 且k = n 的情况外，等式成 立当且仅当芦由所有这样的q 符号k - 集合( a ，) 构成，x o a 且f ( x o ) = 5 0 对某 个固定的x o ，e o m 本文作者注意到对于部分置换交族的e k r 定理可以用圈序方法建立一个更强 的结果一交反链的l y m - 型不等式，并解决猜想1 1 此外，作者引进者色布尔 格”的概念，并在论文的三四章考虑各种着色的交性质为方便理解，这里给出 k a t o n a 的证明的主要步骤； 将数字1 ，2 ，n 按自然顺序排在一个圈中，令a = ( a l ，a 2 ，如) 是一个有序 族，这里a 为圈中k 个连续数字构成的段( 显然有n 个) 将m 上的一个置换 ”作蓐在n 上我们将得到一个新的有序族z ( a ) 令5 ( o ) 表示所有有序族的集 合，f s ( n ) i = n ! 令，是m 的k 一子集的交族，则 ( i ) s ( a ) 包含n 州个k 一子集； ( i i ) 州的每个k 一子集出现在5 ( o ) 中的n 女! m 一女) ! 个有序族中( 通过对称 性可得到) ； ( i i i ) 任何一个o z 5 ( a ) 最多包含，中的k 个成员 定义x ( a n ) = 。1 莩蠡4 那么有 x ( a ，a ) 曼心。 口s ( a ) a ， ( x ( a ，a ) _ 旧以协叫! ，q s ( q ) 比较两式即得i ，| s ( n 一- 1 1 ) 大连理工大学博士学位论文 1 3 主要工作 论文主要分为两大部分，第一部分由第二章构成，主要研究两类d y c k 路偏序 集的m s b i u s 函数计算及其应用，以及偏序集上的一些相关性质，如h a s s e 图的构 造、s p e r n e r 性质、单峰性第二部分由三、四章构成，主要研究着色布尔格的交性 质，包括e r d s s - k o - r a d o 性质，交族极值结构的唯一性以及交反链的l y m - 型不等 式 第一部分以d y c km 路偏序集d 1 ( n ) 开始，即由所有d y c kn 路在包含关系下 构成的有限偏序集，这里的包含关系是指对任意两条d y e k7 , 一路a ，p ，as l 卢当且仅 当不穿过卢文中从d y c kn 一路峰和谷的角度详细地阐释了d 1 ( n ) 的结构f c r r a r i 和p i n z