# Guangzhou Discrete Mathematics Seminar

### Talks in 2019

2019.15

26 December 2019 (Thursday), 3-4pm, *room 519*

Xueliang Li (Nankai University, Tianjin, China) Graphs with flow indices less than 3 Poster

It was showed that for a simple graph G with |V(G)| ≥ 44, if min{δ(G), δ(Gc)} ≥ 4, then either G or its complementary graph Gc has a nowhere-zero 3-flow. We will improve this result by showing that if |V(G)| ≥ 32 and min{δ(G), δ(Gc)} ≥ 4, then either G or Gc has a flow index strictly less than 3. Our result is proved by a newly developed closure operation and contraction method.

Besides this, we also consider the flow-property of graphs with spanning triangle-trees. A well-known classical theorem of Jaeger (1979) says that every graph with two edge-disjoint spanning trees admits a nowhere-zero 4-flow. We will prove that every graph with two edge-disjoint spanning triangle-trees has a flow strictly less than 3. We also show that all graphs with spanning triangle trees but without nowhere-zero 3-flow can be constructed from a K4 by a so-called bull-growing operation. This generalizes a previous result on triangularly-connected graphs.

This is a joint work with Jiaao Li and Meiling Wang.

2019.14

10 December 2019 (Tuesday), 4-5pm, room 415

Salvatore Tringali (Hebei Normal University, Shijiazhuang, China) Additive decompositions of sets of integers into irreducible sets Poster

Let Z be the ring of integers. A set AZ is called irreducible if |A| ≠ 1 and AX + Y for all X, YZ such that neither X nor Y is a singleton. Accordingly, if XZ and |X| ≥ 2, we denote by L(X) the set of all integers n ≥ 1 for which there exist irreducible sets A1, ... , AnZ such that

X = A1 + ... + An := {a1 + ... + an : a1A1, ... , anAn}.

It was conjectured in [1, §5] that, for every non-empty finite set LZ≥2, there exists a set XZ such that L(X) = L. I will survey what (little) is known about this conjecture and frame the problem within the broader context of factorization theory.

Reference:  Y. Fan, S. Tringali, Power monoids: A bridge between factorization theory and arithmetic combinatorics, J. Algebra 512 (2018) 252-294.

2019.13

10 December 2019 (Tuesday), 3-4pm, room 415

Yanbo Zhang (Hebei Normal University, Shijiazhuang, China) Some new results on Ramsey numbers Poster

Given two graphs F and H, the Ramsey number R(F,H) is the smallest integer n such that, for any graph G on n vertices, either F is a subgraph of G, or H is a subgraph of the complement of G.

In this talk, I will present some new results on Ramsey numbers.

2019.12

3 December 2019 (Tuesday), 3-4pm, room 415

Xing Peng (Tianjin University, Tianjin, China) Large book-cycle Ramsey numbers Poster

A book Bn(k) is a graph which consists of n copies of Kk+1 all sharing a common Kk. In this talk, we will discuss our recent results on the Ramsey numbers of book versus cycles. Moreover, we will talk about methods used in our proofs. Joint work with Qizhong Lin.

2019.11

21 November 2019 (Thursday), 3-4pm, room 416

Jingmei Zhang (Southern University of Science and Technology, Shenzhen, China) On the size of (Kt, Tk)-co-critical graphs Poster

Given an integer r ≥ 1 and graphs G, H1, ... , Hr, we write G → (H1, ... , Hr) if every r-coloring of the edges of G contains a monochromatic copy of Hi in color i for some i ∈ {1, ... , r}. A non-complete graph G is (H1, ... , Hr)-co-critical if G -/-> (H1, ... , Hr), but G+e → (H1, ... , Hr) for every edge e in the complement of G. Motivated by Hanson and Toft’s conjecture [Edge-colored saturated graphs, J. Graph Theory 11 (1987), 191-196], we study the minimum number of edges over all (Kt, Tk)-co-critical graphs on n vertices, where Tk denotes the family of all trees on k vertices. Following Day [Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017), 201-207], we apply graph bootstrap percolation on a not necessary Kt-saturated graph to prove that for all t ≥ 4 and k ≥ max{6, t}, there exists a constant c(t, k) such that, for all n ≥ (t - 1)(k - 1) + 1, if G is a (Kt, Tk)-co-critical graph on n vertices, then

e(G) ≥ [(4t - 9)/2 + ⌈k/2⌉/2]n - c(t, k).

Furthermore, this linear bound is asymptotically best possible when t ∈ {4, 5} and k ≥ 6. The method we developed may shed some light on attacking Hanson and Toft’s conjecture.

Joint work with Zi-Xia Song (University of Central Florida, USA).

2019.10

7 November 2019 (Thursday), 10-11am, room 416

Pinkaew Siriwong (Chulalongkorn University, Thailand) Cops and robbers on certain hypergraphs Poster Slides

A cops and robbers game is a two-player game which is usually played on a finite connected graph. Two players may take an alternative move from a vertex to another vertex along an edge or pass their turn, beginning with a cop. Besides a finite graph, this game can be played on a finite connected hypergraph which is slightly different from playing on a graph by moving from one vertex to another vertex belonging to the same hyperedge. A hypergraph which a cop has a winning strategy is called a cop-win hypergraph and a hypergraph which a robber has a winning strategy is called a robber-win hypergraph. Recently, some authors have investigated the cop-number; that is, the minimum number of cops needed to win, in both graphs and hypergraphs. According to cops and robbers game played on hypergraphs, the cop-number of hyperpaths and hypercycles are one and two cops, respectively. In this talk, we are interested in such a game played on the product of cop-win hypergraphs and characterization of cop-win hypergraphs.

2019.9

8 October 2019 (Tuesday), 3-4pm, room 416

Jianxi Liu (Guangdong University of Foreign Studies, Guangzhou, China) Spectrum distribution of random Hermitian matrices - Concentration of the spectrum and distribution of the largest eigenvalue of random digraphs Poster

The study of the spectrum of random matrices is an important topic in mathematics. It has been widely used in the fields of nuclei physics, quantum gravity, transportation and communication, and stock issues in financial markets, etc. In this lecture, we will use the well-known Talagrand’s concentration inequality to analyze the centralization of the spectrum of Hermitian adjacency matrices of random digraphs, and characterize the distribution of the largest eigenvalue. This work is joint with: Yue Guan, Bo Cheng, Meili Liang, Li Zeng, Jinxun Wang, Minfeng Chen.

2019.8

28 June 2019 (Friday), 3-4pm, *room 519*

Yaping Mao (Qinghai Normal University, Xining, China) Gallai Ramsey number of graphs Poster Slides

In this talk, we introduce the concepts of Ramsey number and Gallai Ramsey number. The progress of Gallai Ramsey number is also given. We also introduce the Ramsey number and Gallai Ramsey number of books, unicyclic graphs, odd cycles, fans, wheels and stars with extra independent edges.

2019.7

26 April 2019 (Friday), 5-6pm, room 416

Shinya Fujita (Yokohama City University, Japan) How to make a connected graph properly connected Poster Slides

An edge-colored graph G is called properly colored if no two adjacent edges share a color in G. An edge-colored connected graph G is called properly connected if between every pair of distinct vertices, there exists a path that is properly colored. In this talk, we discuss how to make a connected graph properly connected efficiently.

2019.6

26 April 2019 (Friday), 4-5pm, room 416

Boram Park (Ajou University, Korea) On sum-free problem and its generalization Poster

One of great interest in the study of sum-free sets is to consider sum-free subsets of a set of integers, which has attracted a significant attention in the literature over the years. In this talk, some recent results on sum-free sets of integers are discussed. Then we present a recent result on k-sum n-solution free set, where n is a 2-dimensional integer vector. This is the first investigation of the non-homogeneous solution-free set problem in higher dimensions. The work is based on joint work with Ilkyoo Choi and Ringi Kim.

2019.5

29 March 2019 (Friday), 3-4pm, *room 409*

Henry Liu (SYSU, Guangzhou, China) Degree powers in graphs with a forbidden forest Poster

For a graph G with degree sequence d1,..., dn, and a positive integer p, let ep(G) = d1p +...+ dnp. In 2000, Caro and Yuster [A Turán type problem concerning the powers of the degrees of a graph, Electron. J. Combin. 7 (2000), R47] introduced the following Turán type problem: Given a positive integer p and a graph H, determine the function exp(n, H), which is the maximum value of ep(G) taken over all graphs G on n vertices that do not contain H as a subgraph. Obviously, we have ex1(n, H) = 2ex(n, H), where ex(n, H) denotes the classical Turán function. Previous results on this problem, obtained by various authors, include the determination of the function exp(n, H) when H is a complete graph, a cycle, a path, and a star. In this talk, we shall present some new results for the function exp(n, H) when H is a certain type of forest, namely, a linear forest, a star forest, and a broom (i.e., a path with a star at one end). Joint work with Yongxin Lan (Nankai University), Zhongmei Qin (Chang’an University), and Yongtang Shi (Nankai University).

2019.4

11 March 2019 (Monday), 3-4pm, room 416

Supanut Chaidee (Chiang Mai University, Thailand) Geometrical properties of spherical Laguerre Voronoi diagram with applications Poster Slides

Many natural phenomena display as polygonal patterns on the sphere. Voronoi diagram is one of the candidates to model those patterns for understanding pattern formation. We mainly focused on the spherical Laguerre Voronoi diagram, the generalized Voronoi diagram on the sphere. In this talk, we will investigate the geometrical properties of the diagram which rely on the polyhedra and apply those properties to approximate and generate the real-world tessellations on the sphere. This work is joint work with Prof. Kokichi Sugihara from Meiji University, Japan.

2019.3

25 February 2019 (Monday), 4-5pm, room 416

Yongqi Feng (University of Amsterdam, Netherlands) An introduction to Coxeter graphs and their derivatives

Coxeter graphs stem from Coxeter’s study of reflections in (finite dimensional) Euclidean spaces. It is now known that they can be used to classify many objects appearing in mathematics and physics, for example, the root systems. A root system R in a Euclidean space V is a finite set of nonzero vectors which generate V and satisfy certain combinatorial conditions. Attached to each root vector there is a reflection which negatives this vector. The group generated by these reflections is an important object in combinatorics group theory. We will present the classification of root systems in terms of Coxeter graphs, and discuss some other graphs/diagrams closely relevant to Coxeter graphs.

2019.2

7 January 2019 (Monday), 4-5pm, room 416

Shinya Fujita (Yokohama City University, Japan) Some recent results on edge-colored graphs Poster Slides

An edge-colored graph is called properly colored if no two adjacent edges have the same color. Also, an edge-colored graph is called rainbow if no color repeats on it. Nowadays, properly colored cycles or rainbow cycles in edge-colored graphs are widely studied in graph theory. In this talk, some recent results on properly colored cycles and rainbow cycles will be reviewed. I will also present some open problems in this topic.

2019.1

7 January 2019 (Monday), 3-4pm, room 416

Boram Park (Ajou University, Korea) Unavoidable subgraphs in a graph with large matching number Poster

Given a graph parameter ρ, every graph G with sufficiently large ρ(G) contains a ‘well-structured’ induced subgraph H with large ρ(H). The classical Ramsey’s theorem deals with the case when the graph parameter under consideration is the number of vertices; there is also a Ramsey-type theorem regarding connected graphs. In other words, Ramsey’s theorem is for unavoidable structures in a graph with large number of vertices.

Given a graph G, the matching number and the induced matching number of G is the maximum size of a matching and an induced matching, respectively, of G. In this paper, we formulate Ramsey-type theorems for the matching number and the induced matching number regarding connected graphs. Along the way, we obtain a Ramsey-type theorem for the independence number regarding connected graphs as well. The work is based on joint work with Ilkyoo Choi, Michitaka Furuya, and Ringi Kim.

Talks in 2017 2018 2019

Back to main page