中国科学:数学2023年第53卷第2期:187∼216SCIENTIASINICAMathematica综述英文引用格式:ShangguanC,GeGN.Sparsehypergraphs:Fromtheorytoapplications(inChinese).SciSinMath,2023,53:187–216,doi:10.1360/SSM-2022-0008c©2022《中国科学》杂志社www.scichina.commathcn.scichina.com稀疏超图:从理论到应用献给朱烈教授80华诞上官冲1∗,葛根年21.山东大学数学与交叉科学研究中心,青岛266237;2.首都师范大学数学科学学院,北京100048E-mail:theoreming@163.com,gnge@zju.edu.cn收稿日期: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简介稀疏超图(sparsehypergraphs)问题是Brown等[12]和S´os等[71]在20世纪70年代提出的一类经典的Tur´an型问题(Tur´an-typeproblem).该问题受到了多位著名领袖组合学家的重视,目前已成为极值组合学研究领域内的核心问题之一.与之相关的研究方法丰富多变,涉及组合、概率、代数和数论等多个领域.特别地,人们对稀疏超图的研究极大地推动了正则性方法(regularitymethod)的发上官冲等:稀疏超图:从理论到应用展.这一强有力的方法已成为离散数学的重要研究工具,其创始人Szemer´edi也获得了2012...
