管理员登录 / English
Planar anti-Ramsey numbers and Turan numbers for paths and cycles
发布时间: 2018-05-20     22:17   【返回上一页】 发布人:Yongtang Shi


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

 

周五公众报告

 

报告题目: Planar anti-Ramsey numbers and Turan numbers for paths and cycles

 

报告人:Yongtang Shi (南开大学)

 

时间地点: 5月25日下午4:00-5:00 后主楼1124

 

邀请人: 徐敏

 

报告摘要:Motivated by anti-Ramsey numbers introduced by Erdos, Simonovits and Sos in 1975, we study the anti-Ramsey problem when host graphs are plane triangulations. Given a positive integer n and a plane graph H, let Tn(H) be the family of all plane triangulations T on n vertices such that T contains H as a subgraph. The planar anti-Ramsey number of H, denoted arP(n,H), is the maximum number k such that no edge-coloring of any plane triangulation in Tn(H) with k colors contains a rainbow copy of H. The study of arP(n,H) (under the name of rainbow numbers) was initiated by Hornak, Jendrol, Schiermeyer and Sotak [J Graph Theory 78 (2015) 248–257]. We study planar anti-Ramsey numbers for paths and cycles. We first establish lower bounds for arP(n,Pk) when n ≥ k ≥ 8. We then improve the existing lower bound for arP(n,Ck) when k ≥ 5 and n ≥ k2 - k. Finally, using the main ideas in the above- mentioned paper, we obtain upper bounds for arP (n, C6) when n ≥ 8 and arP (n, C7) when n ≥ 13, respectively.

    Turan-type problems was initiated by Mantel (1907) and Turan (1941), which wasgeneralized soon by Erdos et al. Dirac (1964) and Mader (1967) started to investigate extremal problems for Kt-minor-free graphs. The planar Turan number of F, denoted exP(n,F), is the maximum number of edges of any F-free planar graph on n vertices. Dowden [J. Graph Theory 83(2016) 213–230] began the study of planar Turan num- bers exP(n,H) (under the name of “extremal” planar graphs) and determined that exP(n,C4)≤15/7(n-2) for all n≥4 and exP(n,C5)≤(12n-33)/5 for all n≥11,and also proved that both of those bounds are tight. Dowden suggested studying the case of larger cycles and other forbidden subgraphs, such as K4 minus one edge. In this paper, we show that exP(n,C6)≤18/7(n-2) for all n≥6. We also determine exP(n,Θk) for   k = 4, 5, where Θk is the graph obtained from Ck by adding one chord. Finally, we determine the value of exP (n, Pk ) for k ≤ 11 and characterize all the extremal graphs.

    Joint work with Yongxin Lan and Zi-Xia Song.

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