会议地点：腾讯会议室 271-538-596
1.报告题目：Condorcet Stable Sets: Optimizing Decision-making in Facility Location
报告时间：2023年11月17日 15：20-16：00
报告人：陈旭瑾研究员（中国科学院数学与系统科学研究院）
报告摘要：
In a facility location problem, k facilities are to be built to serve spatially distributed customers. But who decide(s) which locations to choose for building the facilities? Different approaches place the decision in the hands of different groups or individuals. In a central planning approach, the central authority enforces a (near) optimal solution according to some system objective. In a market approach, the facilities (i.e., facility managers) play a game for selecting their own locations and return a Nash equilibrium. In a democratic approach, the customers collectively make the decision. We propose a novel solution concept for the democratic approach, called Condorcet stability. A solution, i.e., a set of selected locations, is Condorcet Stable (CS) if no unselected candidate location is more popular than any selected one. Focusing on the setting with customers continuously distributed on a network (undirected graph), we first give a string of existence results on CS solutions. Most notably, when the number k of facilities is large enough, we provide a characterization of CS solutions, which leads to an efficient algorithm for finding such a solution. We measure the efficiency of CS solutions w.r.t. the minimum total cost of all customers, using the standard terms of Price of Anarchy and Price of Stability, both of which we upper bound with small constants. Compared with the market approach, our democratic approach is shown to be more likely to achieve a desirable solution of higher efficiency. Compared with the central planning approach, CS solutions are naturally more stable and fair for the customers, and their efficiency is very close to the optimum, even in the worst case. Therefore, the customers in the scheme of Condorcet stability are better decision-makers for balancing efficiency, stability, fairness, and tractability of facility locations. (Joint work with Changjun Wang and Chenhao Wang)
报告人简介：目前研究兴趣为网络优化设计中的算法博弈研究。
主持人：孙玉芹教授(上海电力大学)
2.报告题目：On the number of subgraphs in a graph
报告时间：2023年11月17日 16：00-16：30
报告人：许克祥教授（南京航空航天大学）
报告摘要：The study on the number of subgraphs in a graph is a hot topic in enumerative combinatorics with some related problems. Extremal problems in this field are much attractive in graph theory. Many results are published on the number of subtrees for trees, but there are few results for the general graphs. In this talk we characterize the extremal graphs with the number of subtrees among all connected graphs of order $n$ with $s$ cut edges, cacti of order $n$ with $s$ cycles, and block graphs of order $n$ with $s$ blocks, respectively. And a partial solution is provided to a conjecture for the mean subtree order of trees posed in 1984. Moreover, several results are proved for the local and global mean orders of sub-$k$-trees of $k$-trees. Furthermore, a complete solution is obtained to a conjecture of the probability that a random subtree of $K_n$ contains a given edge.
报告人简介：许克祥，南京航空航天大学数学学院教授，博士生导师，中国运筹学会图论组合分会理事。研究兴趣为极值图论、度量图论、化学图论及计数组合等。主持完成国家自然科学基金、江苏省自然科学基金、国家科技部国际合作项目及中国博士后基金，获江苏省高等教育成果（高校自然科学类）三等奖。
主持人：杨亦挺副教授(同济大学)
3.报告题目：Directed Steiner tree packing and related topics
报告时间：2023年11月17日 16：30-17：00
报告人：孙跃方副教授（宁波大学）
报告摘要：The famous Steiner tree packing problem in undirected graphs is not only an important theoretical problem, but also has a strong background in applications, especially in VLSI circuit design. It attracts much attention of researchers in the areas of graph theory, combinatorial optimization and theoretical computer science, and has become an well-established area. It is natural to extend this problem to digraphs, and such problems in digraphs are called directed Steiner type packing problems, including directed Steiner tree packing problem and strong subgraph packing problem. In this talk, we introduce known results on directed Steiner tree packing and related topics.
报告人简介：孙跃方，宁波大学数学与统计学院副教授、硕士生导师。当前主要从事有向图理论的研究。主持国家自然科学青年基金和面上基金、浙江省自然科学基金；入选宁波市甬江引才工程。
主持人：田方副教授(上海财经大学)
4.报告题目：Chromatic polynomials of hypergraphs
报告时间：2023年11月17日 17：00-17：30
报告人：张瑞雪 副教授（青岛大学）
报告摘要：In this talk, we present some properties on chromatic polynomials of hypergraphs which do not hold for chromatic polynomials of graphs. We first show that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers. We then prove that for any multigraph $G=(V,E)$, the number of totally cyclic orientations of $G$ is equal to the value of $|P(H_G,−1)|$, where $P(H_G,\lambda)$ is the chromatic polynomial of a hypergraph $H_G$ which is constructed from $G$. Finally we show that the multiplicity of root ”0” of $P(H, \lambda)$ may be at least 2 for some connected hypergraphs $H$, and the multiplicity of root ”1” of $P(H, λ)$ may be 1 for some connected and separable hypergraph $H$ and may be 2 for some connected and non-separable hypergraphs $H$.
报告人简介：张瑞雪，青岛大学，副教授，2020年毕业于新加坡南洋理工大学，主要研究领域：超图及混合超图染色、超图及混合超图色多项式、极值超图等。主持国家自然科学青年基金，山东省自然科学基金，曾获“Singapore Mathematical Society Medal in Mathematical Sciences Academic Year 2019-2020”。
主持人：田方副教授(上海财经大学)