网站首页  |  实验室概况  |  研究团队  |  新闻中心  |  学术交流  |  学术报告  |  实验室年报  |  联系我们

 
 
  当前位置:首页 -> 学术报告
吴文俊数学重点实验室组合图论系列讲座之一百零四【葛根年】
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.
中国科学院吴文俊数学重点实验室