Sparse Hypergraphs: from Theory to Applications

发布时间：2019-03-19 作者：浏览次数：

Speaker:	葛根年	DateTime:	2019年3月22日（周五）上午8:20-9:10
Brief Introduction to Speaker: 葛根年，首都师范大学教授。		Place:	六号楼二楼报告厅
Abstract: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. Together with Alon and Shapira, 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 combinatorics 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 conjec...