2020年组合数学及其应用创新团队系列报告

报告时间：2020年7月26日上午8:30-11:30

报告地点：腾讯会议833495161

报告题目：Rainbow Independent Sets in Cycles

报告摘要：For a given class C of graphs and given integers m \le n, let f_ C(n,m) be the minimal number k such that every k independent n-sets in any graph belonging to C have a (possibly partial) rainbow independent m-set. In this talk, I will give our result about rainbow independent sets on the case C=C_{2s+1}. Our result is a special case of the conjecture (Conjecture 2.9) proposed by Aharoni et al in \cite{Aharoni}. This talk is based on the work jointed with Zequn Lv.

报告人：陆玫教授，博士生导师。 1993年7月在中国科学院数学与系统科学研究院获博士学位，现为清华大学数学科学系教授，博士生导师，主要从事运筹学、图论与组合优化方面的研究，在《Journal of Combinatorial Theory, Series B》、 《Journal of Graph Theory》、 《Linear Algebra and Applications》、《Discrete Applied Mathematics》、《Discrete Mathematics》、《Journal of Combinatorial Optimization》等国际权威学术期刊发表SCI检索论文60余篇。现任清华大学数学科学系计算数学与运筹学研究所所长，中国运筹学会图论组合分会副理事长，中国工业与应用数学学会图论组合及应用专业委员会秘书长，中国组合数学与图论学会理事。

报告题目：Graph Densities and Fractional Edge-Colorings

报告摘要：Given a multigraph G=(V,E) with a positive rational weight w(e) on each edge e, the weighted density problem (WDP) is to find a subset U of V, with |U|\ge 3 and odd, that maximizes \frac{2w(U)}{|U|-1}, where w(U) is the total weight of all edges with both ends in U, and the weighted fractional edge-coloring problem (WFECP) can be formulated as the linear program Minimize Subject to where A is the edge-matching incidence matrix of G. These two problems are closely related to the celebrated

Goldberg-Seymour conjecture on edge-colorings of multigraphs, and have great interests in their own rights. Even when w(e) = 1 for all edges e, determining whether WDP can be solved in polynomial time was posed by Jensen and Toft [Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, 2015, pp. 327--357] and by Stiebitz et al. [Graph Edge Colouring: Vizing's Theorem and Goldberg's Conjecture, John Wiley, New York, 2012] as an open problem. We design strongly polynomial-time algorithms for solving WDP and WFECP exactly, and develop a novel matching removal technique for multigraph edge-coloring. (Joint work with Wenan Zang, Qiulan Zhao.)

报告人：陈旭瑾研究员，博士生导师。2000年东南大学应用数学系获硕士学位, 2004年香港大学数学系获博士学位，现为中国科学院数学与系统科学研究院研究员。从事运筹学及相关领域的研究工作，主要研究兴趣和方向是组合优化的理论和应用，包括算法博弈论、网络优化、多面体组合等。2010年获“中国运筹学会青年科技奖”一等奖，2013年获首届国家优秀青年基金。

报告题目：Degree sums and dominating cycles

报告摘要：A cycle C of a graph G is dominating if any vertex of V(G)\V(C) has at least one neighbor on C and V(G)\V(C) is an independent set. Let G be a k-connected graph of order n≥3 with k≥2. In this talk, we will introduce our new result that every longest cycle of G is dominating if the degree sums is more than (k+1)(n+1)/3 for any k+1 pairwise nonadjacent vertices, and the lower bound is sharp, which generalizes the results due to Bondy for k=2 and Lu et al. for k=3.

报告人：陈耀俊教授，博士生导师。2000年7月在中国科学院数学与系统科学研究院获理学博士学位；2000.7-2002.6在南京大学数学系从事博士后研究工作；2003.9-2005.8在香港理工大学商学院物流系从事博士后研究工作；目前主要从事图中特定子图结构、Ramsey 数以及编码理论、理论计算机与组合图论交叉问题的研究。近些年主持国家自然科学基金多项，在国内外专业学术杂志上发表多篇研究论文，其中50余篇发表在SCI检索源期刊上。

报告题目：On the normalized Laplacian spectra of graphs

报告摘要：In this talk, we introduce some properties of normalized Laplacian spectra of graphs. In particular, we prove that the generalized friendship graph  which is a graph on  vertices obtained by joining a vertex to all vertices of  disjoint copy of complete graph  on  vertices, is determined by its normalized Laplacian spectrum for ，while  is not determined by its normalized Laplacian spectra for . We conclude a conjecture on the normalized Laplacian spectra.

报告人：张晓东教授，博士生导师。1998年6月在中国科学技术大学获得理学博士学位。曾在以色列理工学院(得到Lady Davis Postdoctoral fellowship 资助)和智利大学做博士后、美国加州大学圣地亚哥分校等校做访问学者。多次主持国家自然科学基金项目和参加国家973项目和863项目。曾获得安徽省科技进步二等奖和教育部科学技术进步三等奖。 已经在SCI期刊发表120多篇论文，出版专著一本；曾在华人数学家大会上作邀请报告；担任中国运筹学会图论组合分会副理事长。目前主要研究领域为谱图理论，随机图与复杂网络，组合矩阵论等。