Guangzhou Discrete Mathematics Seminar

The seminars aim to promote the presence of discrete mathematics in Guangzhou, as well as to strengthen the discrete mathematics community there. Everyone is welcome to attend. If anyone is interested in giving a seminar talk, or for general enquiries, please contact one of the organisers.

Organisers
Ping Hu: huping9 AT mail DOT sysu DOT edu DOT cn
Henry Liu: liaozhx5 AT mail DOT sysu DOT edu DOT cn
Chao Yang: yangchao AT gdufs DOT edu DOT cn
Zanbo Zhang: eltonzhang2001 AT gmail DOT com

How to get to School of Mathematics, Sun Yat-sen University

Upcoming talks

TBA

Past talks

27 September 2024 (Friday), 3-4pm Beijing time, room 519 and online, Tencent Meeting ID: 487 608 331

Weicong Li (Great Bay University, Dongguan, China) Intriguing sets in finite classical polar spaces Poster Slides

Intriguing sets in finite classical polar spaces are well-studied geometric objects due to their connections with two-character sets and strongly regular graphs. Over the past two decades, various constructions have been given, but nontrivial examples of intriguing sets in polar spaces of higher rank (rank 4 and above) are relatively rare, especially m-ovoids. In this talk, I will present recent results on the constructions of new intriguing sets in finite classical polar spaces. The novelty of these constructions lies in their reliance on special representations of certain almost simple groups.

2024.3

28 June 2024 (Friday), 4-5pm Beijing time, room 406 and online, Tencent Meeting ID: 118 037 831

Xujun Liu (Xi'an Jiaotong-Liverpool University, Suzhou, China) Every subcubic graph is packing (1, 1, 2, 2, 3)-colorable Poster Slides

For a sequence S = (s₁, ... , s_k) of non-decreasing positive integers, a packing S-coloring of a graph G is a partition of its vertex set V(G) into V₁, ... , V_k such that for every pair of distinct vertices u, v ∈ V_i the distance between u and v is at least s_i + 1, where 1 ≤ i ≤ k. The packing chromatic number, χ_p(G), of a graph G is defined to be the smallest integer k such that G has a packing (1, 2, ... , k)-coloring. Gastineau and Togni asked an open question "Is it true that the 1-subdivision (D(G)) of any subcubic graph G has packing chromatic number at most 5?" and later Brešar, Klavžar, Rall, and Wash conjectured that it is true.

In this paper, we prove that every subcubic graph has a packing (1, 1, 2, 2, 3)-coloring and it is sharp due to the existence of subcubic graphs that are not packing (1, 1, 2, 2)-colorable. As a corollary of our result, χ_p(D(G)) ≤ 6 for every subcubic graph G, improving a previous bound (8) due to Balogh, Kostochka, and Liu in 2019, and we are now just one step away from fully solving the conjecture. Joint work with Xin Zhang and Yanting Zhang.

2024.2

14 June 2024 (Friday), 4-5pm Beijing time, room 406 and online, Tencent Meeting ID: 470 018 171

Zhujun Zhang (Government Data Management Center of Fengxian District of Shanghai, Shanghai, China) An introduction to algorithmic combinatorial game theory Poster Slides

In this talk, we give a brief introduction to algorithmic combinatorial game theory. A combinatorial game is a two-player game with no random elements or hidden information. The computational complexity of games is considered in algorithmic combinatorial game theory which shows the hardness of the games. Burke and Teng [Internet Mathematics 5(4) (2008) 477-492] introduced a two-player combinatorial game Atropos based on Sperner's lemma, and showed that deciding whether one has a winning strategy for Atropos is PSPACE-complete. In the original Atropos game, the players must color a node adjacent to the last colored node. Burke and Teng also mentioned a variant Atropos-k in which each move is at most of the distance k of the previous move. We prove that for any fixed integer k (k > 1), Atropos-k is PSPACE-complete. This is joint work with Chao Yang.

2024.1

5 January 2024 (Friday), 4:30-5:30pm Beijing time, room 519 and online, Tencent Meeting ID: 121 027 368

Rong Wu (Shanghai Jiao Tong University, Shanghai, China) Graphs with girth 9 and without longer odd holes are 3-colorable Poster Slides

For a number l ≥ 2, let G_l denote the family of graphs which have girth 2l + 1 and have no odd hole with length greater than 2l + 1. Wu, Xu and Xu conjectured that every graph in ∪_l≥2 G_l is 3-colorable. Chudnovsky et al., Wu et al., and Chen showed that every graph in G₂, G₃ and ∪_l≥5 G_l is 3-colorable respectively. In this paper, we prove that every graph in G₄ is 3-colorable. This confirms Wu, Xu and Xu's conjecture.

Archive