关于3元一致U(s,q)集族的最大基数_向青.pdf

中国科学:数学2023年第53卷第2期:369380SCIENTIA SINICA Mathematica论文英文引用格式:Xiang Q,Zou H.On the maximum size of 3-uniform U(s,q)families(in Chinese).Sci Sin Math,2023,53:369380,doi:10.1360/SSM-2022-0047c 2022中国科学 杂志社关于3元一致U(s,q)集族的最大基数献给朱烈教授80华诞向青1,2,邹翰林31.南方科技大学数学系,深圳 518055;2.南科大杰曼诺夫数学中心,深圳 518055;3.浙江大学数学科学学院,杭州 310027E-mail:,收稿日期:2022-03-21;接受日期:2022-05-10;网络出版日期:2022-08-17;*通信作者国家自然科学基金(批准号:12071206,12131011 和 12150710510)资助项目摘要假设n、k、s和q为正整数,n q k,sk q,s 2.给定一个集族F(nk),如果对于任意F1,.,Fs F,都有|F1 Fs|6 q,则称F是一个U(s,q)集族.这个概念由Frankl和Kupavskii(2021)引入.它是两类常见集族的推广:(1)t-交族;(2)最多有s个成员互不相交的集族.Frankl和Kupavskii(2021)提出如下问题:决定U(s,q)集族的最大基数.本文充分研究k=3的情形,并且在s s0(t)时,确定U(s,2s+t)集族的最大基数.特别地,本文证明Frankl和Kupavskii(2021)提出的一个关于3元一致U(s,q)集族的最大基数的猜想.关键词完全相交定理EKR 定理移位Erd os 匹配猜想MSC(2020)主题分类05D051引言假设n为一个正整数并且记n=1,.,n.用2n表示n的所有子集构成的集合.对于任意正整数k 6 n,用(nk)表示n的所有k元子集构成的集合.一个(n上的)集族F指的是2n的一个子集.一个(n上的)k元一致集族F指的是(nk)的一个子集.假设p和r为非负整数且p r.定义Ap,r:=A(p,r,n,k):=A(nk):|A p|r.在引入本文的研究对象之前,首先回顾极值集合论里的几个重要结果.给定一个集族F(nk),如果F的任意两个成员的交是非空的,则称F为一个交族.关于交族有一个著名的定理,即Erd os-Ko-Rado(EKR)定理.向青等:关于 3 元一致 U(s,q)集族的最大基数定理1.1(EKR定理4)假设n和k为正整数且n 2k.对于任意交族F(nk),有以下结论:|F|6(n 1k 1).(1.1)此外,如果n 2k,则(1.1)中的等式成立当且仅当F由包含n的某一个元素的所有k元子集构成.例如,A1,1是一个交族并且达到了(1.1)中的上界.下面一个定理是EKR定理在t-交族上的推广.这里,一个t-交族指的是任意两个成员的交至少包含t个元素的集族.定理1.2(完全相交定理1)假设F(nk)是一个t-交族,且n 2k t.则|F|6max06i6kt|A2i+t,i+t|.我们还可以从另一个角度来推广EKR定理.一个集族F是交族当且仅当不存在F的2个成员互不相交.一个自然的推广就是把2换成一个参数.这样就得到了一个新的命题,即著名的Erd os匹配猜想(Erd os matching conjecture,EMC).猜想1.1(EMC2)假设n (s+1)k 1.给定一个集族F(nk),假设F最多有(F)个成员互不相交.如果(F)6 s,则有|F|6 max|As,1|,|A(s+1)k1,k|.这个猜想是极值集合论的中心问题之一.迄今为止,人们只能在k 6 3的情形下证明EMC(参见文献3,6).而当k 3时,EMC的证明似乎会非常困难.最近,Frankl和Kupavskii7整合了上述几个命题,进而提出了一个新的概念.定义1.1假设k、s和q是正整数且k,s 2,k 6 q q k 1,sk q,s 2.用m(n,k,s,q)表示n上的k元一致U(s,q)集族的最大基数.如果q=(k r)s+p,且0 2的假设,得到了关于猜想1.2的部分结果.2预备知识2.1一个移位技巧本文把n的任意一个k元子集记为(a1,a2,.,ak),并且要求a1 a2 ak.对于两个子集Fi=(a(i)1,.,a(i)k)(i=1,2),如果a(1)j6 a(2)j对于任意j k成立,则记F1 F2.如果在一个集族F(nk)中,G F F总是能推导出G F,则称F是一个已完全移位集族.在极值集合论中,要证明一个命题对满足某个性质P的所有集族成立,常常只需要证明这个命题对于满足性质P的已完全移位集族成立即可(参见文献5).对于猜想1.2和1.3来说,实际上也只需要证明它们对已完全移位集族成立.通过下面两个命题来说明这一点.假设1 6 i j 6 n,F是n上的一个集族.定义(i,j)-移位Sij如下:Sij(F)=(F j)i,如果i/F,j F,(F j)i/F,F,否则,Sij(F)=Sij(F):F F.命题2.1假设F是n上的一个k元一致U(s,q)集族.则对于任意1 6 i u时,Sij(F)=F.易见,当j/s=u+1F或者i s=u+1F时,|Sij(F1)Sij(Fs)|6|F1Fs|.下面考虑j s=u+1F并且i/s=u+1F的情形.假设存在v u+1,.,s使得j/v=u+1F;而对于每个 v+1,.,s,有j F.对于 v+1,.,s,令F=(F j)i.则Sij(F1)Sij(Fs)=F1 Fv Fv+1 Fs.由Sij的定义知F F.所以|Sij(F1)Sij(Fs)|6 q.命题2.2(参见文献5,第2节)假设F是n上的一个集族.按照一个规则将每一个移位Sij(1 6 i j 6 n)都进行一遍.这个规则是:如果j 2s+t,s t 1.定义n上的3个3元一致U(s,2s+t)集族F1:=A(t,1,n,3),F2:=A(s+t,2,n,3),F3:=A(2s+t,3,n,3).(2.1)371向青等:关于 3 元一致 U(s,q)集族的最大基数易知,|F1|=(n3)(n t3),|F2|=(s+t3)+(s+t2)(n s t),|F3|=(2s+t3).本小节总是假设F(n3)是一个U(s,2s+t)已完全移位集族,且|F|maxi3|Fi|.因此F不能完全包含于任何一个Fi中.从而,(t+1,t+2,t+3)F,(1,s+t+1,s+t+2)F,(1,2,2s+t+1)F.(2.2)引理2.1(F)6 s+t12 6s+t2.证明假设上式不成立,那么必然存在F的s+t12+1个成员,使得它们的并是3(s+t1)2+3.再并上其他st2 1个成员(1,2,3(s+t1)2+4),.,(1,2,2s+t+1)F,则在F里找到了s个成员,而它们的并是2s+t+1.这与F是一个U(s,2s+t)集族矛盾.引言中提到了EMC对3元一致集族成立.根据上面的引理,对F F3使用EMC,从而得到下面的推论.推论2.1如果s t+4,则|F F3|6(2s+t3)(2s+t s+t23),若s st,(3(s+t2+1)13),若s 6 st,其中st:=110(11t+48+321t2+1776t+2464).下面利用F1、F2和F3引入3个辅助性的集族,它们将被用在后面几节的证明当中:G3:=F3 F2,G2:=F2 F3,G1:=F1(F2 F3).我们有如下描述:G1=(a,b,c):a 6 t,b s+t+1,c 2s+t+1,G2=(a,b,c):b 6 s+t,2s+t+1 6 c 6 n,G3=(a,b,c):b s+t+1,c 6 2s+t.断言2.1(t,s+t+2,2s+t+1)/F,从而|FG1|6(t+(t1)(s1)(n2st)+(t1)(n2st2).证明假设(t,s+t+2,2s+t+1)F.下面s个集合都是F的成员:(t,s+t+2,2s+t+1),(t 1,s+t+1,2s+t),.(1,s+3,2s+2),(1,s+2,2s+1),.(1,t+4,s+t+3),372中国科学:数学第 53 卷第 2 期(t+1,t+2,t+3).而这s个成员的并是2s+t+1,这与F是一个U(s,2s+t)集族矛盾.我们已经证明(t,s+t+2,2s+t+1)/F.因此G1的一个成员(a,b,c)属于F的必要条件是a 6 t,b=s+t+1,c 2s+t+1,或者a 6 t 1,b s+t+2,且c 2s+t+1.由此可得第二个结论.引理2.2如果(a,b,c)(n3)不是F的成员,则|F|6(c 13)+(a 1)(c b)+(b 12)(n c+1)+(a 1)(n c+12).证明通过直接计数可得引理成立.33 元一致 U(s,2s+1)集族由EKR定理可知,猜想1.3对s=2成立.文献7证明了猜想1.3对s=3成立.本节证明以下定理,即猜想1.3对s 4成立.定理3.1假设n 2s+2,s 4,F(n3)是一个U(s,2s+1)集族.则|F|6 maxi3|Fi|,其中F1=A(1,1,n,3),F2=A(s+1,2,n,3),F3=A(2s+1,3,n,3).证明假设F(nk)是一个U(s,2s+1)已完全移位集族,而且|F|maxi3|Fi|.在(2.2)中已知(2,3,4),(1,s+2,s+3),(1,2,2s+2)F.断言3.1(2,s+1,2s+2)/F.从而,|F F2|6|F2|(s 1)(n s 1).证明假设(2,s+1,2s+2)F.那么(1,s ,2s+1 )F对所有=0,1,.,s 3成立.再加上(1,s+2,s+3),可得F的s个成员,它们的并是2s+2.这与F的定义矛盾.所以(2,s+1,2s+2)/F.又因为F是已完全移位的,所以,如果a 2,s,且c 2s+2,n,那么F2的成员(a,s+1,c)不属于F.从而|F F2|6|F2|(s 1)(n 2s 1).证毕.断言3.2(2,3,s+3)F.证明假设(2,3,s+3)/F.那么G2的一个成员(a,b,c)属于F的必要条件是a=1,b 2,s+1,且c 2s+2,n.由此可得|F G2|6 s(n 2s 1).类似地,F3的一个成员(a,b,c)属于F的必要条件是a=1,(b,c)(2,2s+12),或者a 2,s,(b,c)(a+1,s+22).因此|F F3|6(2s2)+(s2)+(s12)+(22)=(2s2)+(s+13).由上述两个结论连同断言2.1,可得|F|6(s+1)(n 2s 1)+(2s2)+(s+13).373向青等:关于 3 元一致 U(s,q)集族的最大基数所以,|F|F2|6(s+1)(n 2s 1)+(2s2)(s+12)(n s 1)=12(s 2)(s2+4s+1 (s+1)n)612(s 2)(s2+4s+1 (s+1)(2s+2)=12(s2+1)(s 2)maxi3|Fi|的假设矛盾.推论3.1F G1=.证明如果(1,s+2,2s+2)F,那么(1,s+2 ,2s+2 )F对所有=0,1,.,s 2成立.再加上(2,3,s+3),可找到F的s个成员,它们的并是2s+2.这与F的定义矛盾.所以(1,s+2,2s+2)/F.从而F G1=.考虑以下s 1个集合:(1,3+,2s+2 ),=0,1,.,s 2.再加上(2,s+2,s+3),得到了s个集合,它们的并是2s+2.这意味着它们中至少有一个不在F里.情形1(1,3,2s+2)/F.此时,G2的一个成员(a,b,c)属于F的必要条件是(a,b)=(1,2)且c 2s+2,n.因此|F G2|6 n 2s 1.由推论3.1和2.1可得|F|6(n 2s 1)+(2s+13)(2s+1 s+123),如果s 13,(n 2s 1)+(3(s+12+1)13),如果s 6 1