Guangzhou Discrete Mathematics Seminar

Talks in 2017

2017.7

18 December 2017 (Monday), 3-4pm, room 416

Ping Hu (SYSU, Guangzhou, China) Flag algebras and its applications (part 2) Poster

Razborov was awarded the 2013 David P. Robbins Prize for introducing a new powerful method, flag algebras, to solve problems in extremal combinatorics. This method has been applied to attack the Caccetta-Häggkvist conjecture, various Turán-type problems, extremal problems in a colored environment, and also to problems in geometry. I will give an introduction to this method and show a few applications.

2017.6

11 December 2017 (Monday), 3-4pm, room 416

Ping Hu (SYSU, Guangzhou, China) Flag algebras and its applications (part 1) Poster

Razborov was awarded the 2013 David P. Robbins Prize for introducing a new powerful method, flag algebras, to solve problems in extremal combinatorics. This method has been applied to attack the Caccetta-Häggkvist conjecture, various Turán-type problems, extremal problems in a colored environment, and also to problems in geometry. I will give an introduction to this method and show a few applications.

2017.5

26 November 2017 (*Sunday*), 3-4pm, room 416

Yongtang Shi (Nankai University, Tianjin, China) Star chromatic index of subcubic multigraphs Poster

The star chromatic index of a multigraph G, denoted χ′_s(G), is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bi-colored. A multigraph G is star k-edge-colorable if χ′_s(G) ≤ k. Dvořák, Mohar and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313-326] proved that every subcubic multigraph is star 7-edge-colorable. They conjectured in the same paper that every subcubic multigraph should be star 6-edge-colorable. In this talk, we will list some results on this conjecture. Joint work with Hui Lei, Zi-Xia Song and Tao Wang.

2017.4

13 November 2017 (Monday), 3-4pm, room 416

Jun Liang (South China Normal University, Guangzhou, China) The algorithms on cyclic vertex (edge) connectivity Poster Slides

This talk will be divided into two main parts. In the first part, we will review some classic algorithms in graph theory. In the second part, some current research on algorithms of cyclic vertex (edge) connectivity will be introduced. The problem of finding a polynomial time algorithm for determining the cyclic vertex (edge) connectivity of a graph has been open for many years. Here, we present some polynomial time algorithms for the cyclic vertex connectivity of regular graphs. We also present a stochastic algorithm for the cyclic edge connectivity, where the graphs satisfy some conditions. In the above two parts, we will mainly focus on introducing the ideas on the algorithms.

2017.3

23 October 2017 (Monday), 3-4pm, room 416

Chao Yang (SYSU, Guangzhou, China) Wang tiles and aperiodic tiling Poster Slides

In order to study the decidability of a fragment of first-order logic, Hao Wang introduced the Wang tiles in 1961. A Wang tile is a square tile with a color on each side. Wang asked whether there exists a set of Wang tiles that can tile the entire plane only non-periodically, with the color constraints. This opened a new research field of aperiodic tiling, which led to the discovery of a set of aperiodic tiles consisting of just two polygonal tiles by Roger Penrose in 1974. In this talk, we survey some recent results and open problems on aperiodic tiling.

2017.2

9 October 2017 (Monday), 3-4pm, room 416

Zanbo Zhang (Guangdong Industry Polytechnic, Guangzhou, China) Cycle problems and path problems in digraphs Poster Slides

Cycle problems and path problems in graphs and digraphs have been studied extensively for more than half a century. They have formed a fruitful research field containing lots of interesting results and challenging problems on graph theory, algorithm design and computational complexity. In this talk, I will mainly focus on theoretical aspect. Firstly, I will give a rough overview on the various conditions and richful structures in this field. Then, due to my personal bias, I will go a little further into several topics on cycles and paths in digraphs, including different forms of degree conditions for hamiltonian cycles, cycles and paths of many lengths, and a special class of digraphs - tournaments.

2017.1

18 September 2017 (Monday), 3-4pm, room 416

Henry Liu (SYSU, Guangzhou, China) Connected subgraphs in edge-coloured graphs Poster Slides

Whenever the edges of a graph G on n vertices are coloured with r colours, on how many vertices can we find a monochromatic, connected subgraph? In this talk, we consider this Ramsey theory type question and its variants, such as replacing “monochromatic” by “s-coloured” (for some s ≤ r); asking for a specific type of connected subgraph; and putting a condition on the r-colouring of G. Many open questions will be presented.

This talk is based on a joint survey with Shinya Fujita (Yokohama City University, Japan) and Colton Magnant (Georgia Southern University, USA).