为了加强组合数学与图论领域的学术交流，促进同行之间学术研究水平的提升，加深我校与相关领域专家的合作，上海理工大学理学院拟举办“组合数学与图论前沿研讨会”。会议将围绕组合数学和图论等领域的重要问题，分享和探讨国际相关前沿热点问题、最新研究成果及理论、方法，为广大师生提供一个交流和学习的平台，欢迎届时参加。
会议时间：2022年11月12日-13日
会议地点：上海理工大学卓越楼810；腾讯会议：722-7997-6788
会议联系人：
何常香(Email:changxiang-he@163.com)
刘乐乐(Email: ahhylau@163.com)
李燕 (Email:li_yan0919@usst.edu.cn)
朱艳(Email: zhuyan@usst.edu.cn)
张萍 (Email: mathzhangping@126.com)
会议日程安排表
11月12日（星期六） | |||
上午 | 09:00-09:10 | 开幕式 | 宇振盛 |
学术报告 | |||
主持人：方新贵 | |||
09:10-09:50 | 王 毅 | Inertia indices and eigenvalue inequalities for Hermitian matrices | |
09:50-10:30 | 陈耀俊 | The maximum number of triangles in -free graphs | |
主持人：许宝刚 | |||
10:40-11:20 | 季利均 | Constructions of column-orthogonal strong orthogonal arrays | |
主持人：闫桂英 | |||
11:20-12:00 | 康丽英 | Some new results on spectral Turán-type problems | |
会间休息 | |||
下午 | 主持人：冯荣权 | ||
14:00-14:40 | 彭岳建 | Turán densities and hypergraph lagrangian methods | |
14:40-15:20 | 曹海涛 | New results on three-dimensional orthogonal complete large sets of incomplete Latin squares | |
主持人：吕长虹 | |||
15:30-16:10 | 吴河辉 | Orientations of graphs with forbidden out-degree lists | |
16:10-16:50 | 宁 博 | Substructures and eigenvalues of graphs: Triangles and quadrilaterals |
11月13日（星期日） | |||
上午 | 学术报告 | ||
主持人：束金龙 | |||
09:00-09:40 | 王恺顺 | An introduction to Erdős-Ko-Rado theorems and Hilton-Milner theorems | |
09:40-10:20 | 郭曙光 | Ordering graphs by their largest (least) Aα -eigenvalue | |
主持人：李学良 | |||
10:30-11:10 | 华洪波 | Mixed metric dimension of graphs | |
主持人：苗正科 | |||
11:10-11:50 | 林辉球 | Spectral radius and edge-disjoint spanning trees | |
会间休息 | |||
下午 | 主持人：王 军 | ||
14:00-14:40 | 陆 玫 | On the -hull number of graphs | |
14:40-15:20 | 张晓东 | The signless Laplacian spectral radius of graphs without intersecting odd cycles | |
主持人：李雨生 | |||
15:30-16:10 | 史永堂 | Some bounds of the spectral radius in H-saturated graphs | |
16:10-16:50 | 祝宝宣 | Unimodality of independence polynomials of graphs | |
主持人：邵嘉裕 | |||
16:50-17:30 | 潘 颢 | 关于 q-Delannoy 数的 Lucas 型同余式 |
报告摘要
Inertia indices and eigenvalue inequalities for Hermitian matrices
王 毅
大连理工大学
We present a characterization of eigenvalue inequalities between two Her-mitian matrices by means of inertia indices. As applications, we deal with some classical eigenvalue inequalities for Hermitian matrices, including the Cauchy interlacing theorem and the Weyl inequality, in a simple and unified approach. We also give a common generalization of eigenvalue inequalities for (Hermitian) normalized Laplacian matrices of simple (signed, weighted, directed) graphs.
The maximum number of triangles in -free graphs
陈耀俊
南京大学
The generalized Turán number is the maximum number of complete graph in an -free graph on n vertices. Let Fk be the friendship graph consisting of triangles. Erdős and Sós (1976) determined the value of . Alon and Shikhelman (2016) proved that . In this talk, we will report our new result on the exact value of and the extremal graph for any when .
Constructions of column-orthogonal strong orthogonal arrays
季利均
苏州大学
Strong orthogonal arrays have better space-filling properties than ordinary orthogonal arrays for computer experiments. Strong orthogonal arrays of strengths two plus, two star and three minus can improve the space-filling properties in low dimensions and column orthogonality plays a vital role in computer experiments. In this talk, we present several constructions of column- orthogonal strong orthogonal arrays of strengths two plus, two star, three minus and t based on difference matrices and generator matrices. Our constructions can provide larger numbers of factors of column-orthogonal strong orthogonal arrays of strengths two plus, two star, three minus and t than those in the existing literature, enjoy flexible run sizes.
This is joint work with Jingjun Bao, Yuanyao Pan and Juanjuan Xu.
Some new results on spectral Turán-type problems
康丽英
上海大学
For a simple graph , let ) and denote set of graphs with the maximum number of edges and the set of graphs with the maximum spectral radius in an -vertex graph without any copy of the graph , respectively. The Turán graph is the complete -partite graph on vertices where its part sizes are as equal as possible. Cioabă, Desai and Tait [The spectral radius of graphs with no odd wheels, European J. Combin., 99 (2022) 103420] posed the following conjecture: Let be any graph such that the graphs in are Turán graphs plus edges. Then for sufficiently large . In this talk, we consider the graph such that the graphs in are obtained from by adding edges, and prove that if has the maximum spectral radius among all n-vertex graphs not containing , then is a member of for large enough. Thus Cioabă, Desai and Tait’s conjecture is completely solved. We also give the spectral extremal graphs for (-fan and the unique spectral extremal graph for .
Turán densities and hypergraph lagrangian methods
彭岳建
湖南大学
Given a positive integer and an -uniform hypergraph , the Turán number is the maximum number of edges in an -free -uniform hypergraph on vertices. The Turán density of is defined as . Let be an -graph on and let .
Define the Lagrangian function
.
The Lagrangian of , denoted by , is defined as , where The Lagrangian density of an -uniform graph is , where ) is the Lagrangian of . The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. The Lagrangian density of an -uniform hypergraph is the same as the Turán density of the extension of . We present some results on hypergraph Turán densities via hypergraph Lagrangian methods and some related questions.
New results on three-dimensional orthogonal complete
large sets of incomplete Latin squares
曹海涛
南京师范大学
Three-dimensional orthogonal complete large sets of incomplete Latin squares play an important role in the study of orthogonal arrays with strength 3 and maximum distance separable codes. In this talk, we will report the existence of two infinite classes of three-dimensional orthogonal complete large sets of incomplete Latin squares.
Orientations of graphs with forbidden out-degree lists
吴河辉
上海数学中心
Let be a graph and be a mapping. The graph G is said to be F-avoidable if there exists an orientation of such that for each vertex , the out-degree It was conjectured by Akbari, Dalirrooyfard, Ehsani, Ozeki and Sherkati that if for each vertex , then is -avoiding, and they showed that suffices. By using Combinatorial Nullestellensatz theorem, we improve the bound to. Furthermore, if the maximum degree is sub-exponential of the minimum degree , then if for each vertex , then is -avoidable.
This is joint work with Peter Bradshaw, Bojan Mohar in Simon Fraser University, and my students Yaobin Chen, Hao Ma in Fudan University.
Substructures and eigenvalues of graphs:
Triangles and quadrilaterals
宁 博
南开大学
Our talk will mainly focus on the relationship between substructures and eigenvalues of graphs. We will briefly survey recent developments on a classical result of Nosal on triangles and a theorem of Nikiforov on . In particular, we shall present counting results for previous spectral theorems on triangles and quadrilaterals.
An introduction to Erdős-Ko-Rado theorems and
Hilton-Milner theorems
王恺顺
北京师范大学
Erdős-Ko-Rado theorem and Hilton-Milner theorem are two fundamental results in combinatorics, which are closely related to graph theory, association schemes, codes, designs and so on. In this talk, I will give a preliminary introduction to the two theorems.
Ordering graphs by their largest (least) -eigenvalue
郭曙光
盐城师范大学
In 2017, Nikiforov defined the -matrix of a graph as , where , and are the diagonal matrix of degrees and the adjacency matrix respectively. The largest eigenvalue of is called the -spectral radius of , denoted by . The -spectral radius of a graph has been studied widely. In 1981, Cvetković proposed twelve directions for further research in the theory of graph spectra, one of which is “classifying and ordering graphs”. From then on, ordering graphs with various properties by their spectra, specially by their largest eigenvalues, becomes an attractive topic. In this talk, we show that (i) for and connected and with vertices and edges, if the maximum degree and , then ；(ii) for and two connected graphs and with size if and , then ; (iii) for and two graphs and , if the minimum degree and , then , where denotes the least eigenvalue of .
Mixed metric dimension of graphs
华洪波
淮阴工学院
Let be a graph with vertex set and edge set . The mixed metric dimension of a connected graph , denoted by , is the minimum cardinality of a subset such that for any two , there exists a so that the distance between and is not equal to the distance between and . In this talk, we introduce some new results on the mixed metric dimension.
Spectral radius and edge-disjoint spanning trees
林辉球
华东理工大学
The spanning tree packing number of a graph , denoted by , is the maximum number of edge-disjoint spanning trees contained in . The study of is one of the classic problems in graph theory. Cioabă and Wong initiated to investigate from spectral perspectives in 2012 and since then, has been well studied using the second largest eigenvalue of the adjacency matrix in the past decade. In this paper, we further extend the results in terms of the number of edges and the spectral radius, respectively; and prove tight sufficient conditions to guarantee with extremal graphs characterized. Moreover, we confirm a conjecture of Ning, Lu and Wang on characterizing graphs with the maximum spectral radius among all graphs with a given order as well as fixed minimum degree and fixed edge connectivity. Our results have important applications in rigidity and nowhere-zero flows. We conclude with some open problems in the end.
On the -hull number of graphs
陆 玫
清华大学
Let be a graph with vertex set and edge set . Let . The -interval is the union of and the vertices with at least two neighbors in . is said to be -convex if . Set and . Then is the -convex hull of , and it is the smallest -convex set containing . is said to be a -hull set of G if , and the -hull number, denoted by ), of G is the cardinality of a minimum -hull set of G. In this talk, I will present our result on the -hull number of -Kneser graphs and Grassmann graphs, respectively.
This work is joint with Jiaqi Liao and Mengyu Cao.
The signless Laplacian spectral radius of graphs
without intersecting odd cycles
张晓东
上海交通大学
Let be a graph consisting of cycles of odd length , respectively, which intersect in exactly a common vertex, where and . In this paper, we present a sharp upper bound for the signless Laplacian spectral radius of all -free graphs and characterize all extremal graphs which attain the bound. The stability methods and structure of graphs associated with the eigenvalue are adapted for the proof. This talk is joined with Ming-Zhu Chen (陈明珠), A-Ming Liu(刘阿明)(Hainan University).
Some bounds of the spectral radius in H-saturated graphs
史永堂
南开大学
For given graphs and , the graph is -saturated if does not contain as a subgraph but contains for any . In this talk, we presents some results on bounds of the spectral radius in H-saturated graphs.
Unimodality of independence polynomials of graphs
祝宝宣
江苏师范大学
Unimodality problems often arise in many branches of mathematics and have been extensively investigated. In this talk, we will introduce some results for unimodality of independence polynomials of graphs.
关于 -Delannoy 数的 Lucas 型同余式
潘 颢
南京财经大学
我们介绍一个关于 -Delannoy 数的 Lucas 型同余式. 证明的关键在于基于 area 统计量的组合解释以及针对 Delannoy 格路的群作用构造.