为了加强组合数学与图论领域的学术交流，促进同行之间学术研究水平的提升，加深我校与相关领域专家的合作，上海理工大学理学院拟举办“组合数学与图论前沿研讨会”。会议将围绕组合数学和图论等领域的重要问题，分享和探讨国际相关前沿热点问题、最新研究成果及理论、方法，为广大师生提供一个交流和学习的平台，欢迎届时参加。

Time：2022-Nov12nd-13th

Location：USST Zhuoyue Building810；Tencent meeting：722-7997-6788

contact Person：

Changxiang He(Email:changxiang-he@163.com)

Lele Liu(Email: ahhylau@163.com)

Yan Li (Email:li_yan0919@usst.edu.cn)

Yan Zhu(Email: zhuyan@usst.edu.cn)

Ping Zhang (Email: mathzhangping@126.com)

Schedual

Abstract:

Inertia indices and eigenvalue inequalities for Hermitian matrices

Yi Wang

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

Yaojun Chen

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

Lijun Ji

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

Liying Kang

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

Yuejian Peng

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

Haitao Cao

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

Hehui Wu

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

Bo Ning

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

Kaishun Wang

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

Shuguang Guo

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

Hongbo Hua

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

Huiqiu Lin

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

Mei Lu

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

Xiaodong Zhang

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

Yongtang Shi

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

Baoxuan Zhu

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.

On Lucas Type Congruence of q Delannoy Numbe

Hao Pan