CN EN

【9.19腾讯会议】Sparse Hypergraphs: from Theory to Applications



报告题目:Sparse Hypergraphs: from Theory to Applications

 

报告学者:葛根年教授

 

报告者单位:首都师范大学

 

报告时间:2020年9月19日星期六上午10:00-11:00

 

报告地点腾讯会议ID:433 466 060

 

摘要:

More than forty years ago, Brown, Erdos and Sos 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. Note that for r = 3; e = 3; k = 2, this conjecture was solved by the famous Ruzsa-Szemeredi'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 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 arrays which are useful for centralized coded caching. The complexity of the PDAs is reduced from exponential to sub-exponential.

 

报告人简介:

葛根年,组合数学专家,首都师范大学特聘教授,教育部特聘教授,国家杰出青年科学基金获得者,“新世纪百千万人才工程”国家级人选,科技北京百名领军人才培养工程人选,荣获“全国优秀科技工作者”称号,享受国务院政府特殊津贴,曾获第十一届中国青年科技奖、教育部自然科学二等奖、被国际组合数学及其应用协会授予杰出青年学术成就奖—“Hall Medal”。2017年9月入选北京学者。

  葛根年教授长期从事组合数学与信息交叉科学研究:解决了组合设计中若干理论基石问题,确定了历时百余年的三重惠斯特赛程设计存在谱。首次创立被美国同行誉为“elegant and powerful”、“both elegant and efficient”的“Ge-Zhu Frame构作法”,并提出一类系统高效构造区组设计的新方法。推广了Fields奖得主陶哲轩的多项式方法,将不含直角最大子集问题的上界从已知的指数级别降为多项式级别。统一地给出了Wolf奖得主Erdos,Abel奖得主Szemerédi等著名学者在过去40多年间所得有关稀疏超图猜想上界的证明,解决了多个相关公开问题和猜想。解决了编码密码学中若干最优码类的构造问题,成功地将代数几何方法应用于压缩感知矩阵的构造,显著改进了美国科学院院士DeVore的工作。迄今在国际组合数学及信息学领域内顶尖刊物《Journal of Combinatorial Theory, Series A》、《SIAM Journal on Discrete Mathematics》、《IEEE Transactions on Information Theory》、《IEEE Transactions on Signal Processing》等期刊上发表SCI论文180余篇,并被SCI引用1500余次。自2014年爱思唯尔(Elsevier)发布“中国高被引学者(Most Cited Chinese Researchers)榜单”以来,一直进入榜单。

   葛根年教授现任中国组合数学与图论学会副理事长、国际组合数学及其应用协会Fellow及Council Member。曾任中国运筹学会图论组合分会副理事长。目前受邀担任国际组合设计界权威SCI期刊《J. Combinatorial Designs》、国内权威SCI期刊《中国科学:数学》、国内SCI期刊《高校应用数学学报》的编委。

 

主办教师:周君灵

 

 

欢迎广大同学老师积极踊跃参加!