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.