6-16吴文俊数学重点实验室组合图论系列讲座之一百零三【葛根年】

发布者:系统管理员发布时间:2017-06-06浏览次数:33

Title: Sparse hypergraphs: from Theory to applications

Speaker: Gennian Ge (Capital Normal University,China)

Time: June 16, 14:00-15:00

Venue:1518

Abstract:

More than forty years ago, Brown, Erd˝os and S′os introduced the function f_r (n, v, e) to denote the maximum number of edges in an r-uniform hypergraph on n vertices which does not contain e edges spanned by v vertices. They posed a well-known conjecture: n^{k−o(1)}< f_r(n, e(r − k) +k + 1, e) = o(n^k) holds for all integers r > k 2, e 3. Note that for r = 3, e = 3, k = 2, this conjecture was solved by the famous Ruzsa-Szemer′edi's (6,3)-theorem. We add more evidence for the validity of this conjecture. On one hand, we use the hypergraph removal lemma to prove that the upper bound is true for all fixed integers r k + 1 e 3. On the other hand, we use tools from additive number theory to show that the lower bound is true for r 3, k = 2 and e = 4, 5, 7, 8.

 

We also use the theory of sparse hypergraphs to attack several open problems and conjectures in cryptography and coding theory. For example, we use the (6,3)-theorem to solve a conjecture of Walker and Colbourn on perfect hash families. This conjecture has been open for ten years and traditional methods seem to have limited effect on it. We also use the (6,3)-free hypergraphs to construct two classes of placement delivery arrays which are useful for centralized coded caching. The complexity of the PDAs is improved from exponential to sub-exponential.