主讲人：马杰 教授（中国科学技术大学）

主持人：吕长虹 教授

报告时间：2019年12月19日 10：30-11:30

报告地点：闵行数学楼401室

主办单位：数学科学学院 科技处

报告人简介：马杰，中国科学技术大学，教授。2007年在中国科学技术大学数学科学学院获得学士学位，2011年在佐治亚理工学院获得博士学位。曾在卡内基梅隆大学数据科学学院担任博士后研究员，在加利福利亚洛杉矶分校数学学院担任Hedrick助理教授。2016年获得国家自然科学基金委优秀青年基金。2018年起担任SIAM期刊离散数学版块（SIAM Journal on Discrete Mathematics）的副编辑。2018年获中国工业与应用数学学会应用数学青年科技奖。2018年获得霍英东教育基金会第十六届高等院校青年教师奖。

报告内容简介：In this paper, we investigate extremal problems on the subject of the 4-cycle C4, which has played a heuristic important role in the development of extremal graph theory. As a milestone Furedi proved that the extremal number ex(q^2+q+1,C_4)≦1/2 〖q(q+1)〗^2 holds for q ≧14. This matches with the fundamental construction of Erdos-Renyi-Sos and Brown from finite geometry for prime powers q, thus providing one of the very rare exact results in the field.

Our first result is a stability of Furedi's theorem. We prove that for all even q, every (q^2+q+1)-vertex C_4-free graph with at least  1/2 〖q(q+1)〗^2-1/2 q+o(q) edges must be a spanning subgraph of a unique polarity graph, which is constructed from a finite projective plane. Among others, this gives an immediate improvement on the upper bound of ex(n,C_4) for infinite many integers n.

A longstanding conjecture of Erdos and Simonovits states that every n-vertex graph with ex(n,C_4 )+1 edges contains at least (1+o(1))√n  copies of  C_4. Building on the above stability, we obtain an exact result in this direction and thus confirm Erdos-Simonovits conjecture for an infinite sequence of integers n. In fact our result implies a stronger assertion that generally speaking, whenever  n?l  in these circumstances,we can characterize the graphs achieving the lth least number  C_4's. This can be extended to more general settings, which provide enhancements on the supersaturation problem of  C_4.

We also discuss related problems and formalize a conjecture on ex(n,C_4), whose affirmation would disprove Erdos-Simonovits conjecture for general n.