题目： Counting rainbow triangles in graphs
报告人：宁博 副教授 (南开大学)
时间：2022年06月09日 下午2：30 开始
地点：腾讯会议 579 457 701
摘要： In this talk, we shall survey our work on rainbow triangles in edge-colored graphs. In particular, we will give a sketch of a recent theorem of ours. This counting result states that the number of rainbow triangles in an edge-colored graph $G$ is at least $\frac{1}{6}\delta^c(G)(2\delta^c(G)-n)n$, which is best possible by considering the rainbow $k$-partite Tur\'an graph, where its order is divisible by $k$. This means that there are $\Omega(n^2)$ rainbow triangles in $G$ if $\delta^c(G)\geq \frac{n+1}{2}$, and $\Omega(n^3)$ rainbow triangles in $G$ if $\delta^c(G)\geq cn$ when $c>\frac{1}{2}$. This can be seen as a counting version of a previous theorem due to Hao Li.
报告人信息：宁博，南开大学计算机学院/网络空间安全学院副教授，硕士生导师。在《Journal of Combinatorial Theory Series B》、《Combinatorica》、《Combinatorics Probability Computing》和《SIAM Journal on Discrete Mathematics》等图论领域权威期刊发表40余篇高质量学术论文。目前主持国家自然科学基金面上项目1项。代表性工作是和李斌龙合作解决了Woodall在1975年提出的一个长圈猜想，该猜想曾被Bondy和Murty作为图论领域50个未解决问题之一收录在著名图论教科书《Graph Theory with Applications》的附录中（见问题7）。
