科学研究
学术报告
当前位置: 学院主页 > 科学研究 > 学术报告 > 正文

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...