ENGLISH
|
学校主页
学院主页
学院概况
学院简介
现任领导
组织机构
联系方式
师资队伍
教授
副教授
讲师
党委行政
科学研究
研究中心
数苑博雅讲座
学术报告
学术会议
科研项目
科研论文
本科教学
教学动态
精品课程
教学团队
本科生实习
专业介绍与培养方案
研究生培养
研究生培养动态
研究生专业方向
研究生培养方案
党建园地
党建动态
数院党校
学生工作
学工热点
研究生园地
班团快讯
体坛风云
社团采风
学工制度
合作交流
校友动态
校友动态
人才招聘
科学研究
研究中心
数苑博雅讲座
学术报告
学术会议
科研项目
科研论文
学术报告
当前位置:
学院主页
>
科学研究
>
学术报告
> 正文
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...
上一条:
一个基于PKP问题的数字签名方案
下一条:
The stability of circles and lines in the curve shortening flow