稀疏超图:从理论到应用  

Sparse hypergraphs: From theory to applications

作　　者：上官冲 葛根年 Chong Shangguan;Gennian Ge

机构地区：[1]山东大学数学与交叉科学研究中心,青岛266237 [2]首都师范大学数学科学学院,北京100048

出　　处：《中国科学：数学》2023年第2期187-216,共30页Scientia Sinica：Mathematica

基　　金：国家重点研发计划(批准号:2020YFA0712100和2018YFA0704703);国家自然科学基金(批准号:12101364和11971325);山东省自然科学基金(批准号:ZR2021QA005);北京学者计划资助项目。

摘　　要：给定正整数r、e和v,如果某个r-一致超图的任意e条不同边的并都包含至少v+1个顶点,则称其是(v, e)-自由(free)或者(v, e)-稀疏的.稀疏超图的概念由Brown、Erd?s和Sós在20世纪70年代提出.目前,研究给定顶点数的稀疏超图所能包含最大边数的上下界已成为极值组合学研究领域内的核心问题之一.该问题的研究方法丰富多变,涉及组合、概率、代数和数论等多个领域.本文介绍Brown、Erd?os和S′os关于稀疏超图的两个重要猜想的最新研究进展以及稀疏超图在极值组合与信息科学中的若干应用,包括朱烈曾作出突出贡献的完美哈希(Hash)矩阵、可分哈希矩阵等几类信息安全中的研究问题.此外,本文在某些参数下给出完美哈希矩阵与求并-自由(union-free)超图的新构造.本文的构造改进了相应问题的已知最优下界.For fixed integers r,e and v,an r-uniform hypergraph is said to be(v,e)-free or(v,e)-sparse if the union of any e distinct edges of it contains at least v+1 vertices.The notion of sparse hyper graphs was initially introduced by Brown,Erdos and Sos in the 1970s.Since then,determining the upper and lower bounds on the maximum number of edges that can be contained in a sparse hypergraph with a given number of vertices has become one of the central problems in extremal combinatorics.A number of powerful methods from several disciplines,including combinatorics,probability theory,algebra,and number theory,have been applied to the study of sparse hyper graphs.In this paper,we introduce the recent developments on two important conjectures of Brown,Erdos and Sos on sparse hypergraphs,and discuss some of the applications of sparse hyper graphs to extremal combinatorics and information sciences.We also provide new constructions for perfect Hash matrices and union-free hyper graphs under certain parameters.Our constructions improve the previously best-known lower bounds for these problems.

关 键 词：稀疏超图 Brown-Erd?s-Sós猜想 完美哈希矩阵 可消去(cancellative)超图 求并-自由超图 集中式编码缓存 组合列表译码 局部可修复码 

分 类 号：O157.5[理学—数学]