报告题目： Sparse hypergraphs: from Theory to applications
报告人： 葛根年 首都师范大学 (杰青) 报告时间: 2018年6月1日下午16:00 报告地点: 维格堂113教室 报告摘要: More than forty years ago, Brown, Erdös and Sós introduced the function fr(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: nk-o(1) < fr(n,e(r-k) +k + 1; e) = o(nk) 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édi'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 had been open for ten years and traditional methods seem to have limited e_ect 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..