稀疏超图:从理论到应用

Sparse hypergraphs: From theory to applications

给定正整数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.