（应用数学专业论文）有限集族的上界问题.pdf

摘要 摘要 至今所知，集合论中多数成果是有关无限集的问题。然而这些结果，对涉及 图论，组合设计，r a m s e y 理论，计数理论以及超图等现代急速发展着的这些有限离 散数学来说，用处不大。因此在此论文中我们仅仅对集合领域中所必不可少的 有限集合进行讨论。即，对含有n 个元素的集合的子集合族厂，在已满足性质p 时， 考察决定尸阶数的有关问题。所谓已知的性质，即属于集合族厂的任两个集合的 交含有t 个以上的共同元素，等等。这个领域是由e r d 6 s ，s p e r n e r 等人开拓，而后 由d a y k i n ，f o r e d i ，k a t o n a ，k l e i t m a n ，l o v f i s z ，r m w i l s o n 等人推动了这方面的研 究。本领域主要的研究方法是代数学中的矩阵以及多项式方法还包括图论中的超 图等知识。本文首先应用线性代数中的多项式的方法分析和总结了扎一元集h 1 上的 双集族的极值情况，得出了一系列的相关结果。比如s n e v i l v s 猜想的二元集合族 情况，f r a n k l w i l s o n 定理的二元集合族情况等。 其次，我们分析了集合族极值情况的可取性，总结了一些特殊集族的上界。并 特殊的研究了f f a j l l 【1 r a y c h a u d h u r i w i l s o n 定理的上界问题，得到了一些小结果。 论文的最后我们又将此定理进一步推广到差集情况，并将它与交集情形作了一定 程度的统一。 关键词：集合体系约束性相交包含矩阵e r d o s k o r a d o 定理素数多项式半格 a b s t r a c t 一_ - _ _ _ 一 a b s t r a c t u p t on o w , m o s tr e s u l t si ns e tt h e o r ya r ea b o u tt h eu n l i m i t e ds e t b u tt h e s er e s u l t s a r el e s su s e f u lf o rg r a p ht h e o r y , c o m b i n a t o r i c a ld e s i g n ，r a m s e yt h e o r ya n dh y p e r - g r a p h s oi nt h i sp a p e r , w eo n l yd i s c u s st h ef i n i t es e t s ，i ti si n d i s p e n s a b l ei nt h es e t t h e o r y f o raf a m i l y 厂o na s e to f 几e l e m e n t s ，w h e ni ts a t i s f i e st h en a t u r eew ed e c i d e t h eo r d e ro f 7 r t h en a t u r ei st h ei n t e r s e c t i o no fa n yt w os e t si nt h ef a m i l yh a v em o r e t h a n 亡c o m m o ne l e m e n t se t c t h i sf i e l di sd e v e l o p e db ye r d s s ，s p e r n e r l a t e r , d a y k i n ， f t i r e d i ，k a t o n a ，k l e i t m a n ，l o v 缸z ，r m w i l s o np r o m o t ei t sr e s e a r c hi nt h i sf i e l d t h e m a i n m e t h o d si nt h i sf i e l da r et h em a t r i x ，p o l y n o m i a l sa n dh y p e r g r a p hi ng r a p ht h e o r y i nt h i sp a p e r , f i r s t l yw i t hl i n e a r l y - p o l y n o m i a l sm e t h o dw ea n a l y z ea n dg e n e r a l i z e s o m er e s u l t so nt w oi n t e r s e c t i o nf a m i l i e so fs u b s e t so fi n i ti sn a m e l yw ee x t e n d t h ec o n d i t i o no fs i m p l ef a m i l yt ot h ec o n d i t i o no ft w of a m i l i e s w ea l s op r e s e n to t h e r r e s u l t so ns e t s y s t e m sa b o u tt w of a m i l i e s f o re x a m p l es n e v i l y st h e o r e ma n d f r a n k l - w i l s o nt h e o r e m s e c o n d l y , w ea n a l y z ea n dg e n e r a l i z es o m et i g h tb o u n d so ni n t e r s e c t i o nv e r s i o n o fs e ts y s t e m s e s p e c i a l l y , w ed os o m er e s e a r c ho nt h ef i g h tb o u n do ff r a n k l r a y 。 c h a u d h u r i w i l s o nt h e o r e ma n dg e ts o m es m a l lr e s u l t s a tl a s tw ep u tt h i st h e o r e m i n t od i f f e r e n c ev e r s i o na n dd os o m eu n i t yb e t w e e nt h ed i f f e r e n c ev e r s i o na n d t h ei n t e r - s e c t i o nv e r s i o n k e yw o r d s ：s e ts y s t e m s ，r e s t r i c t e di n t e r s e c t i o n s ，i n c l u s i o nm a t r i c e s ，s n e v i l y sc o n j e c - t u r e ，p r i m en u m b e r , p o l y n o m i a ls e m i l a t t i c e s l l 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：翊建琴 2oo 分年f 月蚜日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时 间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：刘建篝 ) o0 8 年与月2 8 日 j l ljhz ( 】il c h a p t e r1i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n a l a r g ev a r i e t yo fp r o b l e m sa n dr e s u l t si ne x t r e m a ls e tt h e o r yd e a lw i t he s t i m a t e s o nt h es i z eo fa f a m i l yo fs e t sw i t hs o m e r e s t r i c t i o n so nt h ei n t e r s e c t i o n so fi t sm e m b e r s n o t a b l ee x a m p l e so fs u c hr e s u l t s ，a m o n go t h e r s ，a r et h e c e l e b r a t e dt h e o r e m so ff i s h e r , r a y c h a u d h u r ia n dw i l s o no n s e ts y s t e m sw i t hr e s t r i c t e dp a i r w i s ei n t e r s e c t i o n s t h e s e a l s oc a nb ec o n s i d e r e da se s t i m a t e so nb i n a r yc o d e sw i t hg i v e nd i s t a n c e s p r o b l e m sa n d r e s u l t sc o n c e r n i n gt h em a x i m u mc a r d i n a l i t yo fs e ts y s t e m sw i t hc e r t a i nr e s t r i c t i o n so n t h ei n t e r s e c t i o n so f i t sm e m b e r sa l ea tt h eh e a r to f e x t r e m a ls e tt h e o r y t h e s ep r o b l e m s h a v eb e e ns t u d i e di n t e n s i v e l yd u r i n gt h el a s th a l fc e n t u r y , w i t hm a n yp a p e r s ，a n da n e x c e l l e n tm o n o g r a p hb yb a b a ia n df r a n k l 【2 d e v o t e dt ot h es u b j e c ta n di t sd i v e r s e a p p l i c a t i o n s o n er a t h e rg e n e r a lp r o b l e mo ft h i st y p ec a n b ed e s c r i b e da sf o l l o w s l e t 歹b ea f a m i l yo fs u b s e t so fa n 扎一e l e m e n ts e ta n dl e t b ea s e to fn o n - n e g a t i v e i n t e g e r s t h ef a m i l y 子i sc a l l e du n i f o r mi fa l li t sm e m b e r sh a v et h es a t l l es i z e i nt h i s c h a p t e r , l e tx d e n o t et h es e tm = 1 ，2 ，佗) a f a m i l y 厂o fs u b s e t so f xi sc a l l e d i n t e r s e c t i n gi fe v e r yp a i ro fd i s t i n c ts u b s e t se f 厂h a v ean o n e m p t yi n t e r s e c t i o n l e tc = 1 1 ，1 2 ，f s ) b eas e to f8n o n n e g a t i v ei n t e g e r s af a m i l y 厂o fs u b s e t so f xi sc a l l e dc i n t e r s e c t i n gi fi enf j cf o re v e r yp a i ro fd i s t i n c ts u b s e t se ，f 厂 af a m i l y 手i sk - u n i f o r mi fi ti sac o l l e c t i o no fk - s u b s e t so fx 。t h u s ，ak u n i f o r m i n t e r s e c t i n gf a m i l yi s - i n t e r s e c t i n gf o rc = 1 ，2 ，k 一1 ) f o ra ni n t e g e rk 2 ，w ea l s os a yt h a t 厂i sk w i s ec i n t e r s e c t i n gi ft h ec a r d i n a l i t y o ft h ei n t e r s e c t i o no fa n ykd i s t i n c tm e m b e r si n 子b e l o n g st o g i v e nap a r t i c u l a r s e tc ，w h a ti st h em a x i m u mn u m b e ro fm e m b e r so fa 七一w i s ec i n t e r s e c t i n gf a m i l y ? n og e n e r a la n s w e rt ot h i sp r o b l e mh a sb e e nf o u n do rc o n j e c t u r e d ，b u tan u m b e ro f a p p e a l i n gp a r t i a lr e s u l t sa r ek n o w n h e r ew el i s ts o m eo ft h e m ，s t a r t i n gw i t ht h em o s t s t u d i e dc a s e ，w h e nk = 2 o n eo ft h ef i r s ts u c hr e s u l t sw a so b t a i n e db ym a j u m d a r 【1 7 】a n dr e d i s c o v e r e db y i s b e l l 16 e x t e n d i n gs o m ee a r l i e rr e s u l t so ff i s h e r , m e yp r o v e dt h a ti f 户i saf a m i l yo f s u b s e t so fa n 佗一e l e m e n ts e ts u c ht h a tt h ei n t e r s e c t i o no fa n yt w om e m b e r so f 厂h a st h e 1 ， c h a p t e r1i n t r o d u c t i o n s a m en o n z e r oc a r d i n a l i t y , t h e ni 厂i 礼r a y c h a u d h u r ia n dw i l s o n 【2 0 】a n df r a n k l a n dw i l s o n 【1 0 】g e n e r a l i z e dt h i sr e s u l ta n do b t a i n e dt i g h tb o u n d so nu n i f o r ma n dn o n - u n i f o r mp a i r w i s ec i n t e r s e c t i n gf a m i l i e s i np a r t i c u l a r , i n 10 】i tw a sp r o v e dt h a ti f i c i = st h e nt h es i z eo fa2 - w i s ec i n t e r s e c t i n gf a m i l yi sb o u n d e db yl 歹i ( ：) f r a n k la n dw i l s o n 1 0 】a l s os h o w e dt h a tt h es a m eb o u n dr e m a i n st r u ei fci sas e to f r e s i d u e sm o d u l oap r i m e p ，a n dw ea s s u m e t h a tt h ec a r d i n a l i t yo fp a i r w i s ei n t e r s e c t i o n s o fm e m b e r so f 7 rm o d u l opi si n 。b u tt h es i z eo fe v e r ym e m b e ro f 孑m o d u l opi sn o t i nc i nt h ef o l l o w i n gp a p e r , w ew i l lf i r s t l yi n t r o d u c es o m ec l a s s i c a lt h e o r e m sa n d s o m et o o l si no u rp r o o f s s e c o n d l y , w ei n t r o d u c es o m es e ts y s t e m sw i t hr e s t r i c t e d 一i n t e r s e c t i o n s 1 1e r d i i s k b r a d ot h e o r e ma n ds o m et o o l s t h ee r d o s - k o - - r a d ot h e o r e mi sac e n t r a lr e s u ko fc o m b i n a t o r i c sw h i c ho p e n e d t h ew a yf o rt h er a p i dd e v e l o p m e n to fe x t r e m a ls e tt h e o r y i nt h ef o l l o w i n gw ew i l l i n t r o d u c et h em e t h o d sa n dt o o l si ne x t r e m a ls e tt h e o r yb yt h ep r o o f so fi t f o ras u r v e y o fr e s u l t sr e l a t e dt ot h ee r d o s - k o r a d ot h e o r e ms e e 7 】 t h e o r e m1 1l 于c2 xt si n t e r s e c t i n gt h e n 厂i 2 礼h o l d s ( 1 1 ) p r o o f t h e r ea r e2 舻1p a i r s c ，x c ) o fc o m p l e m e n t a r ys u b s e t so fx s i n c e c q ( x c ) = 仍，i 厂n c ，x g ) l 1h o l d sf o re a c ho f t h e m 口 e r d o s ，k oa n dr a d o 【8 】w e r et h ef i r s tt oo b s e r v et h ev a l i d i t yo f ( 1 1 ) a n dt h e y p r o v e dt h a tt h e r ea r ev e r ym a n yf a m i l i e s 厂，a c h i e v i n ge q u a l i t yi n ( 1 1 ) m o r ee x a c t l y , t h e yp r o v e dt h a tf o re v e r yi n t e r s e c t i n gf a m i l y9c2 爿t h e r ee x i s t sa n o t h e ri n t e r s e c t i n g f a m i l y 厂，9c 厂c2 x ，s u c ht h a tl 厂l = 2 俨1h o l d s t h ee r d o s k o r a d ot h e o r e md e a l sw i t ht h em u c hm o r ed i f f i c u l tc a s ew h e n if = ki sa s s u m e df o ra l lf 兀i e ，厂i sak - g r a p h i n1 9 6 1 ，e r d o s - k o r a d o 8 p r o v e d t h ec 1 a s s i c a lr e s u l ta sf 0 1 l o w s ： 2 c h a p t e r1 i n t r o d u c t i o n t h e o r e m1 2s u p p o s e ，b eak - u n i f o 册i n t e r s e c t i n g f a m i l yo f s u b s e t so fmw i t h 佗 2 k t h e n 吲( n 奄一- - 1 1 ) a n d f o r 他 2 k , e q u a l i t yh o l d s 矿厂c o n s i s t so f a l lk - s u b s e t s c o n t a i n i n gac o m m o ne l e m e n t f o ra ni n t e g e rt 1 ，af a m i l yj ri sc a l l e dt - i n t e r s e c t i n gi ff nf i th o l d sf o r a l lff j r t oc l o s et h i ss e c t i o nl e tu ss t a t et h eg e n e r a lc a s eo ft h ee r d s s k o r a d ot h e o r e m t h e o r e m1 2 + ( e r d 6 s k o r a d ot h e o r e m , g e n e r a lc a s e ) s u p p o s et h a t 厂c ( x 惫) i s t - i n t e r s e c t i n ga n dn n o ( k ，亡) t h e n l y l ( ：二：) b yn o w i ti sk n o w nt h a tt h eb e s tp o s s i b l ev a l u eo f n o ( k ，t ) i s ( k - t + 1 ) ( t + 1 ) ( c f 2 7 】) n o ww ei n t r o d u c et h et o o ls h i f t i n g i th a sb e c o m eo n eo ft h em o s tp o w e r f u lt o o l s i ne x t r e m a ls e tt h e o r y d e f i n i t i o n1 1t h e ( i ，歹) s h i f t f o raf a m i l y 歹c2 xa n d1 i j n ，d e f i n e ( 厂) = ( f ) ：f 尸) w h e r e 嘞( 耻 暑叫卜d u 计黧篇e 甲舢名f p r o p o s i t i o n1 2 ( i ) l ( f ) i = l e l ；( i i ) l 勖( 厂) l = i y l ；( i i i ) i f 厂i si n t e r s e c t i n gt h e ns o i s 勘( 厂) p r o o f ( i ) a n d ( i i ) a r ei m m e d i a t ef r o mt h ed e f i n i t i o n t op r o v e ( i i i ) ，s u p p o s eb yc o n t r a - d i c t i o nt h a tt h e r ee x i s ts e t sf gi nt h ei n t e r s e c t i n gf a m i l y 手s u c ht h a t s i j ( f ) as , j ( a ) = 函h o l d s ( 1 2 ) s i n c ef ng 仍b ya s s u m p t i o n ，a n dt h eo n l ye l e m e n tw h i c h c a nb ed e l e t e di sj ， i t f o l l o w s t h a tf n g = d i f b o t hfa n dg c h a n g e db yt h e ( i ，歹) - s h i f t ，t h e ni ( f ) n ( g ) w o u l dh o l d ， c o n t r a d i c t i n g ( 1 2 ) t h u sw em a ya s s u m et h a t ( f ) = f ( g ) = ( g d ) ) u 吐 s i m i l a r l y , i fw o u l dc o n t r a d i c t ( 1 2 ) t h u st h eo n l yr e a s o nn o tt or e p l a c e f b yf = ( f d ) ) u ) d u r i n gt h e ( i ，歹) 一s h i f ti sb e c a u s ef 。fh o w e v e r , f n g = f n ( g ) = s 0 ( f ) n ( g ) = 仍，a c o n t r a d i c t i o n 口 3 c h a p t e r1i n t r o d u c t i o n w ec a nn o w p r o v et l l et h e o r e m p r o o fb yi n d u c t i o no nn w h e n 礼= 2 k ，( x f ) 隹厂f o re a c hf 厂s ow eh a v e i 厂l 丢( ：) = ( 瑟二三) s u p p o s et h et h e o r e mt r u ef o rxl = 礼一1 ，a n dl e t 厂b eak - u n i f o r mi n t e r s e c t i n g f a m i l yo fs u b s e t so f 钆】a p p l y i n gt h es h i f t i n go p e r a t i o n & ，n ( 1 i 佗一1 ) o r d e r l y j _ t o2 - ，w eol x a l nas e n e so i 尼一u m l o r mi n t e r s e c t l n gi a m l l m s ： 蜀= y - ，五+ 1= & + 1 ，n ( 兀) ( i = 0 ，1 ，礼一2 ) i ti se a s yt os e et h a ti 五l = l 厂1 s ow ec a nc o n s i d e r 兀一1i n s t e a do f 厂 l e ta = f 兀一1 ：佗f ) a n d 召= f 兀一1 ：佗譬f ) t h e n 召i sa k - u n i f o r mi n t e r s e c t i n gf a m i l yo fs u b s e t so f 佗一1 】l e tc = f 礼) ：f 4 ) c l e a r l y 吲= 1 4 ia n di ti s ( k 一1 ) - u n i f o r m w ec l a i mt h a tci si n t e r s e c t i n g f o r g c ，c ：ct o n ) a 兀一1a n dg t o n ) 厂( i = 1 ，2 ) s i n c el c li + lqi = 2 ( k 一1 ) ( 凳二；) + ( 俨k 1 ) = ( 2 ) h o l d s c o n s e q u e n t l yt h e r ei ss o m ef 厂n 仃庇( 9 ) s i n c ef o k ( g ) ，fcx f f o r s o m ef 。厂t h i si m p l i e sf nf = 仍，i e ，厂i sn o ti n t e r s e c t i n g 口 1 2s e ts y s t e m sw i t hr e s t r i c t e dc - i n t e r s e c t i o n s i nt h i sp a r t e r , w ei n t r o d u c es o m et h e o r e m sa n dr e s u l t sw i t hr e s t r i c t e dc i n t e r s e c t i o n i ti su s e f u lf o ro u rp r o o f si nt h ec h a p t e r2 t h ef i r s tt h e o r e mi sa b o u tt h eu p p e rb o u n df o rak - u n i f o r mc - i n t e r s e c t i n gf a m - i l y i n19 7 5 ，r a y c h a u d h u r ia n dw i l s o n 2 0 m a d et h i sg r e a tp r o g r e s si ne x t r e m a ls e t t h e o r y t h e o r e m1 3l e tc = 1 1 ，1 2 ，z s ) b eas e to f8n o n n e g a t i v ei n t e g e r s i f 厂i sa k - u n i f o r mc - i n t e r s e c t i n gf a m i l yo fs u b s e t so fi n ，t h e n 旧( ：) t h i si n e q u a l i t yi sb e s tp o s s i b l e ，j u s tt a k i n ga l ls s u b s e t so fmw i t hc = o ，1 ，s 一 1 ) a sf o rn o n u n i f o r mc i n t e r s e c t i n gf a m i l i e s ，f r a n k la n dw i l s o n 10 o b t a i n e dt h e f o l l o w i n gu p p e rb o u n di n19 8 1 t h e o r e m1 4l e tc = l l ，1 2 ，2 s ) b eas e to fsn o n n e g a t i v ei n t e g e r s i f 厂i sa n c - i n t e r s e c t i n g f a m i l yo f s u b s e t so fi n ，t h e n 旧：o ( ：) t h i sb o u n di st i g h t ，w h i c hi si l l u s t r a t e db yt h ee x a m p l et h a tt a k ea l ls u b s e t so f s i z ea tm o s t8o f 叫a n dc = o ，1 ，s 一1 ) j q i a na n dr a y c h a u d h u r i 18 h a d c h a r a c t e r i z e dt h ee x t r e m a lc a s eo ft h i st h e o r e m i n1 9 9 1 ，a l o n ，b a b a ia n ds u z u k i 1 c o n s i d e r e dt h es e ts y s t e m sw h i c hh a v es p e c i f i cs u b s e ts i z e sa n di n t e r s e c t i o ns i z e s ，a n dm e yo b t a i n e dt h ef o l l o w i n gr e s u l tw h i c hi s ag e n e r a l i z a t i o nt ob o t ht h e o r e m1 3a n d1 4 5 c h a p t e r1 i n t r o d u c t i o n t h e o r e m1 5l e tc = 1 1 ，1 2 ，z s ) b eas e to f8n o n n e g a t i v ei n t e g e r sa n dk = k l ，也，辟) b ea s e to f i n t e g e r ss a t i s f y i n g 8 一r f o re v e r yi s u p p o s e ，i s a n 一i n t e r s e c t i n gf a m i l yo fs u b s e t so f n 】s u c ht h a t1 只l kf o re a c h 鼠zt h e n 旧e ：。一小( ：) o nt - w i s es e t - i n t e r s e c t i n gf a m i l y , g r o l m u s za n ds u d a k o v 1 4 】p r o v e dt h ef o l l o w i n gt h e o r e mi n2 0 0 2 t h e o r e m1 6l e tpb eap r i m ea n dcb eas u b s e to f o ，1 ，p 一1 ) o f s i z e8 l e t t 2b ea ni n t e g e ra n dl e t 厂b ea f a m i l yo f s u b s e t so f n 】s u c ht h a ti f i ( r o o dp ) 仁c 扣re v e r yf 尸b u ti f ln nr l ( r o o dp ) c f o 厂a n yc o l l e c t i o no f td i s t i n c ts e t s f r o m 子t h e n 旧邬一) 善( 孑) i f i na d d i t i o nt h e r ee x i s tr 8i n t e g e r s 尼1 ，辟 o ，1 ，p 一1 ) s ot h a t 8 一r 如，e a c hia n dj f i ( m o dp ) k l ，辟) 声，e v e r yf ft h e n 厂l ( t 一1 ) i = s - r + 1( ：) n o t et h a ti na l la b o v er e s u l t st h es e tc m a y c o n t m n0 w h e nr e s t r i c t i n g t ob ea s e to fp o s i t i v ei n t e g e r s ，s t r o n g e rb o u n dc a nb eo b t a i n e d i n2 0 0 3 ，s n e v i l y 2 5 】o b t m n e d t h ef o l l o w i n ge l e g a n tt h e o r e m t h e o r e m1 7z fc = l l ，1 2 。，2 8 ) i sas e to fsp o s i t i v ei n t e g e r sa n d 厂i sa nc - i n t e r s e c t i n g f a m i l yo f s u b s e t so fi n ，t h e n 旧：o ( 他了1 ) i nh i se a r l yw o r k