2017年春季组合数学、图论和纽结论大讨论班

时间：周四下午3:00

地点：海韵实验楼105

欢迎参加：-）

第三周：3月2日

报告人：陈 寅（博士生）

报告题目：色多项式破圈定理的匹配表示

第四周：3月9日

报告人：张维娟（博士生）

报告题目：Distance in α-orientation lattice of plane graphs I

第五周：3月16日

暂停一次

第六周：3月23日

报告人：张维娟（博士生）

报告题目：Distance in α-orientation lattice of plane graphs II

第七周：3月30日

报告人：罗元勋（助理教授）

Title:On the Routing and Wavelength Assignment Problem

Abstract:We study the routing and wavelength assignment (RWA) problem in wavelength division multiplexing (WDM) networks with no wavelength conversion. Consider an optical network that is represented by a connected, bidirectional graph G. In G adjacent vertices are connected by two fibers (or, directed edges), one for each direction, such that each fiber carries a fixed number \omega of wavelengths. For a given source-destination traffic request, define its ligthpath to be the route and the wavelength used to support this request. Due to the lack of wavelength conversion, a lightpath must use the same wavelength on all fibers along its path from the source to the destination, and all lightpaths using the same fiber must be assigned distinct wavelengths. The goal of (static) RWA problem is to minimize \omega when G and traffic requests are previously given. In this talk, we will give an overview on RWA problem and some new results.

第八周：4月6日

报告人：刘龙城（副教授）

Title: Inverse minimum flow problem under the weighted sum-type Hamming distance

Abstract: The idea of the inverse optimization problem is to adjust the value of the parameters such that the observed feasible solution becomes optimal. The modification cost can be measured by different norms, such as l_1, l_2, l_\infty norms and the Hamming distance, and the goal is to adjust the parameters as little as possible. In this paper, we consider the inverse minimum flow problem under the weighted sum-type Hamming distance, where the lower and upper bounds for the arcs should be changed as little as possible under the weighted sumtype Hamming distance such that a given feasible flow becomes a minimum flow. Two models are considered: the unbounded case and the general bounded case. We present their respective combinatorial algorithms that both run in O(nm) time in terms of the minimum cut method.

第九周：4月13日

报告人：杨维玲（助理教授）

Title: The lattice stick number of knots

Abstract:The lattice stick number of a knot type is defined to be the minimal number of straight line segments required to construct a polygon presentation of the knot type in the cubic lattice. Let S(K) denote the the lattice stick number of knot K. Youngsik Huh and Seungsang Oh prove that S(31 )=12, S(41)=14 and the trefoil knot 31 and in figure 8 knot 41 are the only knot types of lattice stick number less than 15. We find that S(51 )= S(51)=16 and S(K)>15 for any non-trivial knot K whose crossing number is greater than 5.

第十周：4月20日

报告人：叶永南（研究员）

Title: Tutte polynomials and proper Tutte-mappings

Abstract: let G be a ?nite and connected graph with edge set E(G). Let σ be a sequence on the edge set of G and T be a spanning tree of G. We introduce the conceptions of σ-cut tail and σ-cycle tail of T, which are generalizations of the conceptions of internally and externally activities de?ned by Tutte, respectively. Furthermore, we give the de?nitions of proper Tutte mappings and deletion-contraction mappings. Using the deletion-contraction recursion which Tutte polynomials satisfy, we can construct deletion-contraction mappings. It is proven that deletion-contraction mappings are proper Tutte mappings. We give a characterization for deletion-contraction mappings. These results reveal the essence of deletion-contraction recursion of Tutte polynomials. With the beni?t of deletion-contraction mappings, we consider G-parking functions and study a family of bijections between the set of G-parking functions and the set of spanning trees of G. In these bijections, we can naturally express the Tutte polynomial for a general connected graph G in terms of statistics of G-parking functions and read the parameters of G-parking functions on the corresponding spanning trees.

第十一周：4月27日

报告人：金贤安（教授）

报告题目：Zhang-Zhang多项式