湖南大学彭岳建教授 ;中国科技大学马杰教授 学术报告

时间:2020-10-26浏览:16设置

图与组合系列前沿讲座:

报告题目:On Ramsey Goodness

报 告 人:彭岳建 湖南大学 教授

报告时间:2020年10月28日 15:00-16:00

报告地点:腾讯会议ID:265 798 483

摘要:Given two graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum integer $N$ such that  any coloring of the edges of $K_N$ in red or blue yields a red $G$ or a blue $H$. Let $\Delta(G)$ be the maximum degree of $G$, and $\chi(G)$ be the chromatic number of $G$. Let $s(G)$ denote the chromatic surplus of $G$, the minimum cardinality of a color class taken over all proper colorings of $G$ with $\chi(G)$ colors. Burr  showed that for a connected graph $G$ and a graph $H$ with $v(G)\geq s(H)$, $R(G,H) \geq (v(G)-1)(\chi(H)-1)+s(H)$.

A connected graph $G$ of order $n$ is called $H$-good if R(G,H)=(n-1)(\chi(H)-1)+s(H)$. We will give some results related to Ramsey-goodness in this talk.

报告人简介:彭岳建,湖南大学数学学院教授,博士生导师。2001年博士毕业于美国埃默里大学。2001-2002在美国查塔姆大学数学系任助理教授。2002-2012在美国印第安纳州立大学数学和计算机系任职,历任助理教授,副教授,教授 (终身)。2012年作为“湖南省百人计划”特聘教授回到湖南大学。目前,彭岳建教授已经在极值组合与图论及相关领域做出了许多出色的工作,在国际组合图论权威刊物JCTB、JCTA、CPC、JNT(数论杂志)等发表论文40多篇。一直得到国家自然科学基金的资助。

 

 

报告题目:Counting critical subgraphs in k-critical graphs

报 告 人:马杰 中国科技大学 教授

报告时间:2020年10月28日 16:00-17:00

报告地点:腾讯会议ID: 265 798 483

摘要:Gallai asked in 1984 if any $k$-critical graph on $n$ vertices contains at least $n$ distinct $(k-1)$-critical subgraphs.The answer is trivial for $k\leq 3$. Improving a result of Stiebitz,Abbott and Zhou proved in 1995 that for all $k\geq 4$, any $k$-critical graph contains $\Omega(n^{1/(k-1)})$ distinct $(k-1)$-critical subgraphs.Since then no progress had been made until very recently, Hare resolved the case $k=4$ by showing that any $4$-critical graph on $n$ vertices contains at least $(8n-29)/3$ odd cycles. In this talk, we mainly focus on 4-critical graphs and develop some novel tools for counting cycles of specified parity. Our main result shows that any $4$-critical graph on $n$ vertices contains $\Omega(n^2)$ odd cycles, which is tight up to a constant factor by infinitely many graphs.As a crucial step, we prove the same bound for 3-connected non-bipartite graphs, which may be of independent interest. Using the tools, we also give a short solution to Gallai's problem when $k=4$. Moreover, we improve the longstanding lower bound of Abbott and Zhou to $\Omega(n^{1/(k-2)})$  for the general case $k\geq 5$. We will also discuss related problems on $k$-critical graphs. This is joint with Tianchi Yang。

A connected graph $G$ of order $n$ is called $H$-good if R(G,H)=(n-1)(\chi(H)-1)+s(H)$. We will give some results related to Ramsey-goodness in this talk. 

报告人简介: 马杰,中国科技大学教授、博士生导师,2013年入选中组部****计划,2014年开始在中国科技大学担任“****”教授,2016年获基金委“优秀青年项目”资助。已在JCTB,Combinatorica,RSA等组合学国际顶级学术刊物接受发表学术论文多篇。 

邀请人:金泽民


浙江师范大学离散数学研究中心版权所有 © 2018-2028
地址:浙江省金华市迎宾大道688号21幢 邮政编码:321004
联系电话:0579-82282629   电子邮箱:jcsx@zjnu.cn    管理登陆