稀疏超图_从理论到应用_上官冲.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