讲座名称：Sparse Hypergraphs: from Theory to Applications

讲座人：葛根年 教授

讲座时间：8月30日10:00

讲座地点：北校区新科技楼1012学术报告厅

讲座人介绍：

葛根年，首都师范大学特聘教授。长期从事组合数学、编码理论、信息安全、压缩感知、数据科学等数学与信息交叉科学研究。迄今共发表SCI论文200余篇，并被SCI他引1900余次，其中：65篇发表在国际组合数学及信息学领域内顶尖刊物 《Journal of Combinatorial Theory, Series A》、《Journal of Combinatorial Theory, Series B》、《SIAM Journal on Discrete Mathematics》、《IEEE Transactions on Information Theory》及《IEEE Transactions on Signal Processing》上。自2014年爱思唯尔（Elsevier）发布“中国高被引学者（Most Cited Chinese Researchers）”榜单以来，一直进入榜单。同时，入选美国斯坦福大学发布的“2020全球前2%顶尖科学家（World's Top 2% Scientists 2020）”榜单、美国数学会发布的“高被引数学家（Most cited mathematicians）”榜单。现任中国数学会组合数学与图论专业委员会主任、国际组合数学及其应用协会“Medals Committee Member”（全球共3人）。目前受邀担任国际组合数学界顶尖SCI期刊《Journal of Combinatorial Theory, Series A》、国际信息理论界顶尖SCI期刊《IEEE Transactions on Information Theory》、国际编码密码界权威SCI期刊《Designs, Codes and Cryptography》、国际组合设计界权威SCI期刊《Journal of Combinatorial Designs》、国际代数组合界权威SCI期刊《Journal of Algebraic Combinatorics》、国内权威SCI期刊《中国科学：数学》、国内SCI期刊《高校应用数学学报》的编委。曾获国际组合数学及其应用协会颁发的“Hall Medal”、中国青年科技奖、教育部自然科学二等奖、浙江省科学技术二等奖。

讲座内容：

More than forty years ago, Brown etc. 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, which 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. And we use tools from additive combinatorics to show 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 effect on it. We also use the (6,3)-free hypergraphs to construct two classes of placement delivery ar- rays which are useful for centralized coded caching. The complexity of the PDAs is reduced from exponential to sub-exponential.

主办单位：通信工程集团