稀疏超图_从理论到应用_上官冲.pdf

中国科学:数学2023年第53卷第2期:187216SCIENTIA SINICA Mathematica综述英文引用格式:Shangguan C,Ge G N.Sparse hypergraphs:From theory to applications(in Chinese).Sci Sin Math,2023,53:187216,doi:10.1360/SSM-2022-0008c 2022中国科学 杂志社稀疏超图:从理论到应用献给朱烈教授80华诞上官冲1,葛根年21.山东大学数学与交叉科学研究中心,青岛 266237;2.首都师范大学数学科学学院,北京 100048E-mail:,收稿日期:2022-01-14;接受日期:2022-03-18;网络出版日期:2022-07-28;*通信作者国家重点研发计划(批准号:2020YFA0712100 和 2018YFA0704703)、国家自然科学基金(批准号:12101364 和 11971325)、山东省自然科学基金(批准号:ZR2021QA005)和北京学者计划资助项目摘要给定正整数r、e和v,如果某个r-一致超图的任意e条不同边的并都包含至少v+1个顶点,则称其是(v,e)-自由(free)或者(v,e)-稀疏的.稀疏超图的概念由Brown、Erd os和S os在20世纪70年代提出.目前,研究给定顶点数的稀疏超图所能包含最大边数的上下界已成为极值组合学研究领域内的核心问题之一.该问题的研究方法丰富多变,涉及组合、概率、代数和数论等多个领域.本文介绍Brown、Erd os和S os关于稀疏超图的两个重要猜想的最新研究进展以及稀疏超图在极值组合与信息科学中的若干应用,包括朱烈曾作出突出贡献的完美哈希(Hash)矩阵、可分哈希矩阵等几类信息安全中的研究问题.此外,本文在某些参数下给出完美哈希矩阵与求并-自由(union-free)超图的新构造.本文的构造改进了相应问题的已知最优下界.关键词稀疏超图Brown-Erd os-S os 猜想完美哈希矩阵可消去(cancellative)超图求并-自由超图集中式编码缓存组合列表译码局部可修复码MSC(2020)主题分类05B20,05B40,05C65,05D05,05D40,11B30,60A86,68P30,94B251稀疏超图的起源、历史与发展1.1简介稀疏超图(sparse hypergraphs)问题是Brown等12和S os等71在20世纪70年代提出的一类经典的Tur an型问题(Tur an-type problem).该问题受到了多位著名领袖组合学家的重视,目前已成为极值组合学研究领域内的核心问题之一.与之相关的研究方法丰富多变,涉及组合、概率、代数和数论等多个领域.特别地,人们对稀疏超图的研究极大地推动了正则性方法(regularity method)的发上官冲等:稀疏超图:从理论到应用展.这一强有力的方法已成为离散数学的重要研究工具,其创始人Szemer edi也获得了2012年的Abel奖(Abel prize).除此之外,作为一种拥有优美性质的组合构型,稀疏超图有着众多令人意想不到的应用.多种不同参数的稀疏超图被广泛应用于极值组合、编码理论、信息安全与理论计算机科学等诸多领域,为相关研究带来了新的思想和工具.本文回顾稀疏超图研究的理论成果以及丰富应用,着重介绍其主要研究方法.在该领域内依然有众多困难的未解之谜,吸引着人们不断尝试.1.2Tur an型问题超图(hypergraph)H=(V(H),E(H)由点集V(H)和边集E(H)所构成,其中,V(H)是一个给定的有限集,E(H)是V(H)的幂集的一个子集.为了叙述方便,通常认为H=E(H).如果存在正整数r,使得对于任意A H都有|A|=r,则称超图H为r-一致的(r-uniform).也简称r-一致超图为r-超图.设F和H均为r-超图,如果H的任何子超图(subhypergraph)都不同构于F,则称H为F-自由的;反之,H总是包含F的至少一个拷贝(copy).设F为一族r-超图构成的非空有限集合,如果对于任意F F,H都是F-自由的,则称H是F-自由的.F的Tur an数exr(n,F)被定义为具有n个顶点的F-自由r-超图所能含有的最大边数.当|F|=1即F=F时,简记exr(n,F)=exr(n,F).人们将研究函数exr(n,F)上下界的问题称为Tur an型问题(Tur an-type problems),这是因为这类问题源于匈牙利数学家Tur an81在20世纪40年代的开创性工作.本文所涉及的超图都是r-超图,且有如下约定:(1)r总是给定的正整数,而n可以趋于无穷大;(2)在本文研究的F-自由Tur an型问题中,F总是给定的,其定义不依赖于n.显然,对于任意F都有0 6 exr(n,F)6(nr).Katona等43证明了,对于任意给定的F,极限limnexr(n,F)(nr)总是存在的.称该极限为F的Tur an密度(Tur an density).如果存在实数0 6 6 r,使得当n趋于无穷大时有exr(n,F)=(n),则称为F的Tur an指数(Tur an exponent).如果F的Tur an指数小于r(即其Tur an密度为0),则称对应的Tur an型问题是退化的(degenerate).对于退化型Tur an问题,如果极限limnexr(n,F)n存在,则称该极限为F的退化型Tur an密度(degenerate Tur an density).Katona等43实际上证明了任意给定的F都存在Tur an密度,那么,任意给定的F是否都存在Tur an指数?实际上,稀疏超图与该问题密切相关.当r=2时,人们通常称2-超图也为图(graph).对于图的Tur an数,人们已有丰富的研究成果.1907年,Mantel49证明了对有3个顶点的完全图(complete graph)K3有ex2(n,K3)=n24.1941年,Tur an81将Mantel的结果推广到一般的完全图Kt(t 3),并对于任意正整数n都确定了ex2(n,Kt)的精确值.我们一般认为Tur an的这篇文献开创了极值图论这个研究领域.随后,Erd os和Stone25及Erd os和Simonovits24证明了极值图论的奠基性定理,即Erd os-Stone-Simonovits定理:定理1.124,25设F为一族图构成的有限集,则当n充分大时,ex2(n,F)=(F)2(F)1n22+o(n2),其中,(F)=min(F):F F,这里(F)为图F的染色数(chromatic number),即所需最少的颜色数,使得F存在任意相邻顶点都不同色的点染色.188中国科学:数学第 53 卷第 2 期当r=2时,定理1.1给出了所有有限集F的Tur an密度.如果(F)3,则定理1.1还给出了ex2(n,F)的近似值.例如,ex2(n,Kt)=t2t1n22+o(n2).然而,如果(F)=2,则由定理1.1仅可知ex2(n,F)=o(n2)人们并不能得出F确切的Tur an指数.对此情形,Erd os19有如下著名的有理指数存在性猜想(rational exponents conjecture):猜想1.1(参见文献19,公式(1)设F为一族图构成的有限集,若(F)=2,则存在有理数 0,1)和实数c 0,使得limnex2(n,F)n1+=c.要对所有的(F)=2完全解决上述猜想是一个非常困难的问题,感兴趣的读者可参见文献31的综述.接下来,会看到人们对稀疏超图的研究说明猜想1.1对超图来说(r 3)是不成立的.1.3稀疏超图的Tur an型问题给定正整数r、e和v,称r-超图H是(v,e)-自由的,如果它的任意e条不同边的并都包含至少v+1个顶点,即对于任意A1,.,Ae H,都有ei=1Ai v+1.用函数fr(n,v,e)表示n个顶点的(v,e)-自由r-超图所能包含的最大边数.记Gr(v,e)=F(vr):|F|=e,|V(F)|6 v,则根据定义有fr(n,v,e)=exr(n,Gr(v,e).因此关于fr(n,v,e)的研究是典型的超图Tur an型问题.由于其所含边数的稀疏性,人们也称(v,e)-自由的r-超图为稀疏超图30.不难看出,当v 6 r时,fr(n,v,e)=(nr);当v er时,fr(n,v,e)=0;当v=er 1时,fr(n,v,e)=nr.此外,当e=2时,r-超图H是(v,2)-自由的当且仅当对于任意不同的A,B H都有|A B|6 2r v 1.此时R odl56利用巧妙的“R odl针法”证明了limnfr(n,v,2)(n2r v)/(r2r v)1=1.事实上,fr(n,v,2)的研究也是组合设计的重要课题(参见文献13).近期,Keevash45在相关问题的研究中取得了重大突破,他证明了对于任意满足某些必要整除性条件的参数都有fr(n,v,2)=(n2r v)/(r2r v).由于上述结果,在下面的讨论中总是假设r 2,e 3,r+1 6 v 6 er 2.在这个参数范围内,Brown等12得到了fr(n,v,e)的一般上下界:C1nerve16 fr(n,v,e)6 C2nerve1,(1.1)其中C1和C2是与n无关且仅依赖于r、e和v的两个常数.由(1.1)不难看出,当erve1为正整数时,fr(n,v,e)=(nerve1).人们由此知道了函数fr(n,v,e)的渐近阶,并称erve1为fr(n,v,e)的Tur an指数;而当e 1 er v时,(1.1)并不能给出函数fr(n,v,e)的渐近阶.上述两种情形导致人们作出如下两个猜想.189上官冲等:稀疏超图:从理论到应用猜想1.2(Brown-Erd os-S os第一猜想)对于任意给定的正整数r k 2和e 3,都有nko(1)0,都有limnfr(n,er (e 1)k+1,e)nk=0,limnfr(n,er (e 1)k+1,e)nk=.猜想1.3(Brown-Erd os-S os第二猜想)对于任意给定的正整数r k 2和e 3,极限limnfr(n,er (e 1)k,e)nk总是存在.上述两个猜想是稀疏超图研究中的两个核心问题.事实上,在Brown等最初的文献12中,他们仅提到了猜想1.2和1.3的部分情形:他们认为,猜想1.2对r=3、k=2和e=3成立,猜想1.3对r=3、k=2和e 3成立.经过后来研究者的不断补充与发展(如文献4,22,32,63等),这两个猜想才有了如今的形式.为了叙述方便,又由于Brown等是这类问题的最早研究者,本文还是称这两个猜想为“Brown-Erd os-S os第一猜想”和“Brown-Erd os-S os第二猜想”.下面分别介绍猜想1.2和1.3的研究进展.1.3.1Brown-Erd os-S os第一猜想首先,根据(1.1)有(nk1e1)=fr(n,er (e 1)k+1,e)=O(nk).(1.2)显然,(1.2)未能解决猜想1.2的任何一种情形.实际上,猜想1.2的第一种情形(即r=3,k=2,e=3)由Ruzsa和Szemer edi59在1976年解决,他们证明了著名的(6,3)-定理:n2o(1)3)是不正确的,因为f3(n,6,3)显然没有Tur an指数.1986年,Erd os等22将(1.3)的上下界推广到一般的r 3,他们证明了n2o(1)k 2都有nko(1)4,人们都不能同时证明猜想1.2的上下界.2005年,S ark ozy和Selkow61对于k 3证明了fr(n,4r 3k+1,4)=o(nk).(1.6)Nagle等51对于所有r k+1=e证明了fr(n,(k+1)r k2+1,k+1)=o(nk).(1.7)2021年,Ge和Shangguan32证明了猜想1.2的上界对于所有r k+1 e都成立,下界对于所有r 3、k=2和e 4,5,7,8都成立.在所有其他参数下,猜想1.2的上界和下界都未能被证明,人们只知道一些弱化的结果.例如,对于上界,S ark ozy和Selkow60利用图正则引理证明了,对于所有给定的r k 2和e 3都有fr(n,er (e 1)k+loge,e)=o(nk).(1.8)Conlon等15利用超图正则引理(hypergraph regularity lemma)将上述结果改进为fr(n,er (e 1)k+O(logelogloge),e)=o(nk).(1.9)对于下界,Shangguan和Tamo64利用概率方法将(1.2)中的结果改进为fr(n,er (e 1)k+1,e)=(nk1e1(logn)1e1).(1.10)上述fr(n,er(e1)k+1,e)的新下界与猜想值仍然有很大距离,尤其是人们不知道是否存在一个常数 0,使得对所有r k 2和e 3都有fr(n,er (e 1)k+1,e)=(nk1e1+).综上所述,目前已知猜想1.2的上界对于所有r k+1 e都成立,下界对于所有r k 2、e=3与r k=2、e 4,5,7,8都成立.猜想1.2上界的第一个未解决情形是研究是否有f3(n,7,4)=o(n2),即所谓的(7,4)问题.目前,对于猜想1.2上界的研究,人们多采用正则性方法;对于猜想1.2下界的研究,人们多采用加法数论与概率方法.第3节将举例说明人们是如何利用这些方法来解决Brown-Erd os-S os第一猜想的若干子情形.表1总结了Brown-Erd os-S os第一猜想的研究情况.表1Brown-Erd os-S os 第一猜想的研究情况已解决情形部分进展上界r k+1 e 34,22,32,51,59,61(1.1)12、(1.8)60、(1.9)15下界r k+1 3,e=34,22,59;r 3,k=2,e 4,5,7,832(1.10)64191上官冲等:稀疏超图:从理论到应用1.3.2Brown-Erd os-S os第二猜想与猜想1.2不同,直到2019年才由Glock34证明了猜想1.3的第一种情形(即r=3,k=2,e=3):limnf3(n,5,3)n2=15.(1.11)Glock的证明利用了某个特殊图的图填充(graph packing)53.Shangguan和Tamo63利用诱导图填充(induced graph packing)28和递归构造(recursive construction)将Glock的结果从r=3推广到一般的r 4,得到了limnfr(n,3r 4,3)n2=1r2 r 1.(1.12)对于所有其他情形,猜想1.3都是完全公开的.目前,人们只知道函数fr(n,er (e 1)k,e)的一些上下界.例如,Shangguan和Tamo63利用多项式方法证明了1rk r6 liminfnfr(n,3r 2k,3)nk6 limsupnfr(n,3r 2k,3)nk61k!(rk)k!2.(1.13)最近,Sidorenko69证明了fr(n,r+2,3)(1r o(1)(nr 1),(1.14)这改进了(1.13)在k=r 1时下界的结果.此外,Bohman和Warnke10以及Glock等35分别独立地证明了,对于任意给定的e 4都有f3(n,e+2,e)(16 o(1)n2.(1.15)注意到猜想1.3只要求证明极限limnfr(n,er(e1)k,e)nk的存在性,并不要求计算出其精确值.表2总结了Brown-Erd os-S os第二猜想的研究情况.1.4稀疏超图的应用作为组合数学的重要研究对象之一,稀疏超图被广泛应用于极值组合、编码理论、信息安全与理论计算机科学等诸多领域.人们将相关领域的问题转化为某类稀疏超图的存在与构造问题,再对其加以研究.这些转化往往都不是直截了当的,而是具有相当的技巧性.对于这些应用,本文选取“完美与可分哈希矩阵”“可消去与求并-自由超图”“集中式编码缓存”“组合列表译码”“局部可修复码”等课题展开较为详细的阐述.我们也在前两个课题的研究中取得了一些新进展,详细内容见定理5.4和5.6.表3总结了不同参数下稀疏超图的应用情况.表2Brown-Erd os-S os 第二猜想的研究情况已解决情形部分进展r 3,k=2,e=334,63(1.13)63、(1.14)69、(1.15)10,35192中国科学:数学第 53 卷第 2 期表3不同参数下稀疏超图的应用情况应用名称对应稀疏超图参数参考文献完美哈希矩阵(er r,e)-自由r-超图62,定理7.1t-可消去超图(tr+2rt1t+2,t+2)-自由+(2r 2rt1t+2 1,2)-自由r-超图65,引理2.32-可消去超图(2r,3)-自由r-超图,2 r65,引理2.4t-求并-自由超图(tr r,t)-自由+(tr,2t)-自由r-部r-超图65,引理2.5集中式编码缓存(6,3)-自由3-部3-超图67,定理10具有(,L)-列表译码性质的r长q元纠错码(r+(L+1)r,L+1)-自由r-部r-超图每部都含q个顶点36,引理4.5局部可修复码(ir i,i)-自由r-超图,对于所有1 6 i 6 e84,定理3.146,定理V.8和V.91.5一些记号对于正整数n,记n:=1,.,n.若超图H的顶点集大小为n,则不失一般性记V(H)=n.如果没有特别指出,我们一般认为n趋于无穷大.对于有限集X,用(Xr):=A X:|A|=r表示由X的所有r-元子集所构成的集合.对于正整数1 6 k 6 r,用Kkr表示具有r个顶点的完全k-超图,即E(Kkr)=(rk).如果集合A满足|A|=r,则用Kkr(A)表示顶点集为A的完全k-超图.设f:=f(n)和g:=g(n)为依赖于n的函数,如果limnfg=0,则记f=o(g);如果存在某个不依赖于n的常数C使得f 6 Cg,则记f=O(g);如果存在C使得f Cg,则记f=(g);如果f=O(g)和f=(g)同时成立,则记f=(g).将多次用到多部超图与矩阵的等价关系.称一个r-超图H是r-部的(r-partite),如果V(H)可以被划分为r个两两互不相交的子集,V(H)=ri=1Vi,使得对于任意A H和1 6 i 6 r都有|A Vi|=1.如果对于任意1 6 i 6 r都有|Vi|=q,则不失一般性,假设Vi=(i,a):1 6 a 6 q.此时,对于每一条边A=(i,xi):1 6 i 6 r,1 6 xi6 q H,定义映射:H qr,A (A)=(x1,.,xr).以下观察是显然的.声明1.1依据映射,以Vi:1 6 i 6 r为顶点集划分的r-部r-超图H=A1,.,Am可以被等价地表示为一个r m的q元矩阵MH=(A1)T,.,(Am)T),使得对于1 6 i 6 m,该矩阵的第i列为(Ai)T.1.6文章结构第2节介绍一般参数下稀疏超图的理论界.第2.1小节介绍Brown-Erd os-S os的经典上下界(参见定理2.1)及其证明,第2.2小节叙述Shangguan-Tamo的改进型下界(参见定理2.2)及其证明概要.第3节介绍猜想1.2的研究进展.第3.1小节讨论猜想1.2的上界与超图移除引理的关系,并给出猜想上界对于所有r k+1 e都成立的证明(参见定理3.1);第3.2小节讨论猜想1.2的下界与加法数论的关系,并给出(1.3)的下界的证明(参见定理3.2).193上官冲等:稀疏超图:从理论到应用第4节介绍猜想1.3的研究进展.第4.1小节讨论猜想1.3的上界,并给出(1.13)的上界的证明(参见定理4.1);第4.2小节讨论猜想1.2的下界与近似最优图填充的关系,并给出(1.11)的证明(参见定理4.2).第5节介绍稀疏超图在极值组合中的两个应用.第5.1小节介绍如何利用稀疏超图来构造可分与完美哈希矩阵,第5.2小节介绍如何利用稀疏超图来构造可消去超图和求并-自由超图.本文也在与这两小节相关的课题上取得了一些新进展,参见定理5.4和5.6.第6介绍稀疏超图在信息科学中的3个应用.第6.1小节讨论(6,3)-自由3-超图与集中式编码缓存方案的关系,第6.2小节讨论如何利用稀疏超图来构造具有优异组合列表译码性质的纠错码,第6.3小节介绍如何利用稀疏超图构造在存储编码领域发挥着重要作用的局部可修复码.第7节总结全文,并给出一些值得研究的公开问题.2一般参数下稀疏超图的理论界本节主要讨论一般参数下函数fr(n,v,e)的上下界.第2.1小节给出(1.1)的具体证明,第2.2小节叙述(1.10)的证明思路.本节的主要目的是说明fr(n,v,e)的值实际上等于某个超图的最大独立集大小,因而在研究中可以利用图论与概率方法的相关知识.2.1Brown-Erd os-S os的经典上下界我们将利用“算两次”(double counting)这一组合技巧来证明(1.1)的上界,并利用超图独立集的一个简单下界来证明(1.1)的下界.给定r-超图H,若点集S V(H)中不包含H的任意一条边,即(Sr)H=,则称S为H的独立集(independent set).称H的独立数(independence number)(H)为V(H)所包含的最大独立集的大小,即(H):=max|S|:S V(H)是H的一个独立集.对于每个顶点v V(H),定义v在H中的度数(degree)dH(v)为H中包含v的边的数目,即dH(v):=|v A:A H|.当不会引起混淆时,我们将省略下标H.定义H的最大度(maximumdegree)和平均度(average degree)分别为(H):=maxd(v):v V(H)和d(H):=vV(H)d(v)|V(H)|.显然,(H)d(H).下面的引理给出了r-超图最大独立数的一个简单下界.引理2.172给定正整数r 2,则存在一个仅依赖于r的常数C:=C(r),使得对于任意r-超图H都有(H)C|V(H)|d(H)1r1.本小节的目标是证明如下定理(即(1.1).定理2.1(参见文献12,第4节)对于任意给定的正整数r 2,e 2,r+1 6 v 6 er 2,都有C1nerve16 fr(n,v,e)6 C2nerve1,其中,C1和C2是与n无关且仅依赖于r、e和v的数.194中国科学:数学第 53 卷第 2 期证明对于上界,设H为(v,e)-自由的r-超图,V(H)=n,并记erve1=t.不难看出,n的任何一个t-元子集最多被H的e 1条边所包含.这是因为,如果存在T(nt)和两两不同的A1,.,Ae H,使得T ei=1Ai,则ei=1Ai6|T|+ei=1|Ai T|=t+e(r t)=er (e 1)er ve 16 v,与H的(v,e)-自由性质相矛盾.通过用两种方法计算|(T,A):T(nt),A H,T A|可以得到下面的不等式:|H|(rt)6(nt)(e 1).为了证明下界,我们构造如下的辅助e-超图F,其中,V(F)=(nr),e个不同的点A1,.,Ae(nr)构成F的一条边当且仅当|ei=1Ai|6 v.根据定义不难看出(F)=fr(n,v,e)和d(F)6(F)6(n rv r)(vr)e1.因此,由引理2.1可知fr(n,v,e)=(H)C(nr)(n rv r)1e1(vr)1=(nerve1).证毕.2.2Shangguan-Tamo的改进型下界由定理2.1下界的证明可知,计算fr(n,v,e)的值等价于计算e-超图F的独立数.引理2.1给出了任意一致超图独立数的下界,那么对这个特殊的超图F而言,其独立数是否存在一个更好的下界?这个问题的答案是肯定的.称一个超图为线性的(linear),如果其任意两条不同边最多包含一个公共顶点.在Ajtai等1的工作基础上,Duke等16证明了如下结论:引理2.2(参见文献16,定理2)给定正整数r 3,则存在一个仅依赖于r的常数C:=C(r),使得对于任意线性r-超图H都有(H)C|V(H)|(logd(H)d(H)1r1.利用引理2.2,Shangguan和Tamo64证明了如下结论:定理2.2(参见文献64,定理3)对于任意给定的正整数r 2,e 2,r+1 6 v 6 er 2,若gcd(e 1,er v)=1,则存在一个具有(nerve1(logn)1e1)条边的r-超图,使得其对于所有2 6 i 6 e都是(ir (i1)(erv)e1,i)-自由的.特别地,令i=e,则fr(n,v,e)=(nerve1(logn)1e1).定理2.2有如下的推论:195上官冲等:稀疏超图:从理论到应用命题2.1(参见文献65,引理2.1)给定正整数s 1、r 3和(vi,ei)(1 6 i 6 s),使得vi r+1,ei 2.(a)令h:=mineirviei1:1 6 i 6 s,则存在r-超图,其具有(nh)条边,且对于任意1 6 i 6 s都是(vi,ei)-自由的.(b)进一步地,如果有e1 3、gcd(e1 1,e1r v1)=1以及对于任意2 6 i 6 s都有e1r v1e1 1 k+1 e 3都成立.注意到(1.3)(1.7)中的上界都是上述结论的特殊情形.事实上,这有其必然原因:这些上界的证明分别利用了三角形移除引理(triangle removal lemma)、图移除引理(graph removal lemma)以及某个特殊超图的移除引理,而本节介绍的证明利用了最近才被证明的、完全版本的超图移除引理(hypergraphremoval lemma).图移除引理与超图移除引理分别是图正则引理(graph regularity lemma)与超图正则引理(hypergraph regularity lemma)的推论,相关内容是组合数学与图论的核心研究领域之一,感兴趣的读者可参见文献14.引理3.1(超图移除引理,参见文献14,定理1.2)给定正整数r 2与r-超图F,对于任意 0,都存在:=()0,使得对于任意r-超图H,如果其仅包含不超过|V(H)|V(F)|个F的拷贝,则可以从H中删去最多|V(H)|r条边,得到H的一个F-自由的子超图.通过超图移除引理,容易推导出如下结论:引理3.2给定正整数r 2与r-超图F,对于任意 0,都存在:=()0使得如下结论成立:如果需要删去至少|V(H)|r条边才能使某个r-超图H成为F-自由的,则H一定至少包含|V(H)|V(F)|个F的拷贝.下面将利用引理3.2证明猜想1.2的上界对于所有给定的正整数r k+1 e 3都成立.定理3.1(参见文献32,定理1.3)对于所有给定正整数r k+1 e 3都有fr(n,er (e 1)k+1,e)=o(nk).证明设r、k和e满足定理条件,H是具有n个顶点的(er (e 1)k+1,e)-自由r-超图.若存在某个常数 0使得|H|nk,以下将利用引理3.2推导出矛盾.196中国科学:数学第 53 卷第 2 期首先,不难看出,对于任意A H,仅存在H A的最多e 2条边,使得它们分别与A有至少k个交点.否则,存在e1条不同边A1,.,Ae1使得对于任意1 6 i 6 e1都有|AAi|k,则有e1i=1Ai A6 er (e 1)k,与假设矛盾.因此,存在H的子超图H满足|H|e1nk以及对于任意不同的A,B H都有|A B|6 k 1.接下来,通过H构造如下的k-超图H来辅助定理的证明:顶点集V(H)满足V(H)V(H)V(H);边集E(H)定义如下:对于每条边A H,都构造一个k-超图Kkr(A):=(Ak),并令H=AHKkr(A).容易看出,A H与Kkr(A)H之间是一一对应的,而H由所有Kkr(A)的边的并形成.此外,对任意不同的A,B H,k-超图Kkr(A)与Kkr(B)是边不交的,这是因为对于不同的A,B H有|A B|6 k 1.我们构造了一个k-超图H,它包含Kkr的至少|H|e1nk个边不交的拷贝.因此,需要删去至少e1nk条边才能使H变为Kkr-自由的.由引理3.2可知,H包含至少nr个与Kkr同构的子超图.接下来,估计H中如下Kkr拷贝的数量:它至少有两条边是同一个A H的k-子集.注意到以下观察:A H有至多O(nk)种选择;Kkr的两条边决定了其至少k+1个顶点;选定上面的k+1个顶点之后,其余的r k 1个顶点有最多nrk1种选择.因此,上述Kkr拷贝的数量至多为|H|(rk)2)nrk1=O(nr1),在n充分大时远小于nr.综上所述,一定存在一个Kkr H,它的(rk)条k-边来自于H的(rk)条不同的r-边.特别地,对于r k+1 e,总是存在Kkk+1 Kkr.取任意这样一个Kkk+1的e条不同边,记作B1,.,Be.设A1,.,Ae为H中与它们对应的e条边,满足Bi Ai(1 6 i 6 e).则由|ei=1Bi|6 k+1可知,ei=1Ai6 re (ek (k+1)=e(r k)+k+1,这与H的(er (e 1)k+1,e)-自由性质矛盾.证毕.3.2猜想1.2的下界与加法数论本小节首先介绍加法数论中重要的sum-free(求和-自由)集;再介绍利用求和-自由集构造稀疏超图的一般思想(实际上,利用该方法求和-自由集也可以被用来构造不含其他禁止构型的超图);最后以Ruzsa和Szemer edi59的经典构造为例,具体给出(1.3)下界的证明.197上官冲等:稀疏超图:从理论到应用设s为正整数,考虑线性方程si=1aixi=0,其中系数a1,.,as与未知数x1,.,xs均为整数.如果si=1ai=0,则称该方程为齐次线性方程.此时,不难看出x1=xs为方程的一组解,称这组解为平凡解.对于集合M n,如果对于任意满足si=1aimi=0的m1,.,ms M都有m1=ms,则称M不含上述方程的非平凡解.关于非平凡解的定义实际上是Ruzsa58原始定义的一个简化版本.1947年,Behrend6考虑了不含方程x1+x2=2x3非平凡解的集合,这类集合也被称为是不含3长等差数列的集合(3-term-arithmetic-progression-free),这是由于上述方程的非平凡解实际上构成3长等差数列x1、x3和x2.记rk(n)为n的不含k长等差数列的最大子集的大小.Behrend6证明了r3(n)n2O(log n)=n1o(1).(3.1)目前,rk(n)上下界的估计是加法数论的核心问题,相关研究利用了多种数学工具.如何利用求和-自由集来构造稀疏超图?给定正整数r 3和求和-自由集合M n,可以按如下方式构造一个r-部r-超图H,它的顶点集为V(H)=ri=1Vi,每个Vi都是正整数集,边集为H=A(y,m):A(y,m)=(y+b1m,.,y+brm),y n,m M,其中,A(y,m)是一个有序的r-元组,使得对于每个1 6 i 6 r都有y+bim Vi,B:=b1,.,br n是一个r-元整数集合,它是依据集合M n的求和-自由性质来设计的.容易验证如下结论:引理3.3如果对于任意i=j都有bi=bj,则按照上面的方式构造的超图H是一个有n|M|条边的线性超图.证明不难看出|H|=n|M|,只需证明其任意两条不同边最多有一个公共点.如若不然,假设对(y,m)=(y,m)有|A(y,m)A(y,m)|2,则存在1 6 i,j 6 r(i=j)使得y+bim=y+bim,y+bjm=y+bjm.则y y=bi(m m)=bj(m m),这意味着(y,m)=(y,m),与假设矛盾.下面给出Ruzsa和Szemer edi59利用不含3长等差数列的正整数集合来构造(6,3)-自由3-超图的经典证明.定理3.259f3(n,6,3)=(n r3(n)n2o(1).证明设M n不含3长的等差数列.按照如下方式构造一个3-部3-超图H,它的顶点集为V(H)=3i=1Vi,其中对于每个Vi=i n(1 6 i 6 3),它的边集为H=A(y,m):A(y,m)=(y,y+m,y+2m),y n,m M,并且满足对于1 6 i 6 3有y+(i 1)m Vi.由(3.1)可知,要证明上述命题,只需证明H是(6,3)-自由的.如若不然,则存在3条不同边A1=A(y1,m1),A2=A(y2,m2),A3=A(y3,m3)H使得3i=1Ai6 6.(3.2)由引理3.3可知,对于任意i=j有|Ai Aj|6 1.因此(3.2)成立当且仅当对于任意i=j有|Ai Aj|=1.由于H是3-部超图,不失一般性,假设A1 A2 V1,A2 A3 V2,A1 A3 V3,198中国科学:数学第 53 卷第 2 期则有y1=y2,y2+m2=y3+m3,y3+2m3=y1+2m1,将3个等式左右两边分别相加再消去y1、y2和y3,可得m2+m3=2m1.根据假设可知,M不含3长等差数列,因而有m1=m2=m3,代入上述方程组可得(y1,m1)=(y2,m2)=(y3,m3),与假设矛盾.综上所述,H确实是(6,3)-自由的.证毕.为了利用求和-自由集构造不含其他禁止构型的组合结构,人们从多个角度对Behrend6的构造进行了推广.例如,利用Behrend的构造方法,容易证明如下更为一般的结果:引理3.4(参见文献32,引理3.4)设s 2,a1,.,as,n全为正整数,其中s是固定的,而a1,.,as可以随n变动,则存在一个集合M n满足|M|n2O(log n logli=1al),且不含下述方程的非平凡解:si=1aixi=(si=1ai)xs+1.我们还可以证明,存在一个充分大的集合M n,使得其不含多个方程的非平凡解.引理3.5(参见文献32,引理3.7)令0 a n2O(logan)且其不含第j个方程的非平凡解,则存在一个集合M n,使得|M|n2O(logan)且其不含上述任意一个方程的非平凡解.更多的相关推广可参见文献2,4,30,32,58,62.正是利用各种不同的求和-自由集及其构造,Alon和Shapira4证明了对于所有r k 2和e=3都有fr(n,3r 2k+1,3)nko(1).Ge和Shangguan32证明了对于所有r k=2和e 4,5,7,8都有fr(n,r 2e+3,e)n2o(1).文献32实际上证明了如下更强的结论:定理3.3(参见文献32,定理1.6,1.7)对于任意给定正整数r 3和n ,存在一个线性的r-部r-超图H,使得|H|n2o(1),并且对于所有e 3,4,5,7,8,H都是(er 2e+3,e)-自由的.4Brown-Erd os-S os 第二猜想本节主要介绍猜想1.3的研究进展.第4.1小节给出(1.13)上界的证明,注意到,该上界蕴含了(1.11)和(1.12)的上界;第4.2小节给出(1.11)下界的证明,并讨论证明(1.12)下界的一些主要想法.199上官冲等:稀疏超图:从理论到应用4.1猜想1.3的上界本小节证明(1.13)的上界部分,注意到,(1.11)和(1.12)的上界部分都是其简单的推论.定理4.1(参见文献63,定理6)对于给定的正整数r k 2,有limsupnfr(n,3r 2k,3)nk61k!(rk)k!2.我们需要如下引理.令H(nr)为一个r-超图,T n是一个子集,T在H中的度数dH(T)为H中包含T的边数,即dH(T)=|A H:T A|.引理4.1(参见文献63,引理12)任给一个r-超图H,我们都可以删去它的最多(nk1)条边,得到一个子超图F H,使得F不含度数为1的(k 1)-子集.定理4.1的证明令H为任意(3r 2k,3)-自由的r-超图,F为H的子超图,并满足引理4.1的结论.因此,|H|6|F|+(nk1).要证明定理4.1,只需要证明|F|62(rk)2(rk)1(nk)(rk).由于F是(3r 2k,3)-自由的,所以n的任意k-子集在F中的度数最多为2.对于i 1,2,令Ki(nk)为n中度数为i的k-子集构成的集合,即Ki=K(nk):dF(