管理员登录 / English
Sparse hypergraphs: from theory to applications
发布时间: 2017-12-24     19:36   【返回上一页】 发布人:葛根年


 

北京师范大学数学科学学院

 

周五公众报告

 

报告题目:Sparse hypergraphs: from theory to applications

 

报告人:葛根年(首都师范大学)

 

时间地点:1229日,16:00-17:00,后主楼1223

 

邀请人:王恺顺

 

报告摘要:

More than forty years ago, Brown, Erdös and Sós 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/geq 2, e/geq 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 /geq k + 1 /geq  e /geq  3$. On the other hand, we use tools from additive number theory to show that the lower bound is true for $r/geq 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 improved from exponential to sub-exponential.

 

报告人简介:葛根年,首都师范大学特聘教授,教育部长江特聘教授、国家杰青、国家百千万人才、北京学者。研究方向:组合数学与信息交叉科学。在国际组合数学及信息学领域内顶尖刊物《组合论杂志》、《SIAM离散数学》、《IEEE信息论汇刊》、《IEEE信号处理汇刊》等期刊上发表SCI论文180余篇,并被SCI引用1500余次。现任中国组合数学与图论学会副理事长、国际组合数学及其应用协会FellowCouncil Member。目前受邀担任国际组合设计界权威SCI期刊《Journal of Combinatorial Designs》、国际代数组合界权威SCI期刊《Journal of Algebraic Combinatorics》、国内权威SCI期刊《中国科学:数学》、国内SCI期刊《高校应用数学学报》的编委。

 

周五学院公众报告主旨:讲解现代数学中的基本概念、重要结果及其数学思想的起源、方法的创新等,扩展我们的年青教师和研究生的视野、提高数学修养以及增强学院的学术氛围。邀请各方向的专家用通俗易懂的报告内容、自由互动的讲解方式展现现代数学中重要的基本概念和深刻原理,让听众可以领略到现代数学理论其实是来源于一些大学或研究生阶段就熟知的古典数学中的想法和结论。希望这些报告有助于高年级的本科生、研究生和年青教师更全面的认识现代数学、享受数学之美。欢迎大家踊跃参与!