2018.19
28 December 2018 (Friday), 3-4pm, room 416
Hong-Jian Lai (West Virginia University, USA) Graph eigenvalues and graphical properties Poster Slides
We will present some of the recent progresses in using graph eigenvalues to predict graphical properties. Cioaba and Wong in [LAA, 437 (2012) 630-647] posed a conjecture on using the second largest eigenvalue of a graph to describe the maximum number of edge-disjoint spanning trees. In [Electronic Journal of Linear Algebra, 34 (2018) 428-443] A. Abiad et al proposed an open problem suggesting to use the second largest eigenvalue of a graph to predict the connectivity of the graph. In this talk, we will report the recent progresses towards the above-mentioned conjecture and open problems, as well as other related studies on relating graph eigenvalues to graph structural properties.
2018.18
25 December 2018 (Tuesday), 4-5pm, room 416
Yong Lin (Renmin University of China, Beijing, China) Geometric analysis on graphs Poster
In this talk, we will survey some results and open problems on geometric analysis on graphs.
2018.17
14 December 2018 (Friday), 10:30-11:30am, room 416
Shiping Liu (University of Science and Technology of China, Hefei, China) A discrete curvature approach to strongly spherical graphs Poster Slides
The (strongly) spherical graphs were introduced by Berrachedi, Havel, Mulder in 2003 as an interesting generalization of hypercubes. In this talk we discuss a discrete version of Bonnet-Myers-Cheng theorem, which involves estimate of graph diameter via discrete curvature bounds and the related rigidity results. This theorem justifies the analogies between strongly spherical grpahs and round spheres. This talk is based on joint works with Cushing, Kamtue, Koolen, Muench and Peyerimhoff.
2018.16
30 November 2018 (Friday), 4-5pm, room 416
Kexiang Xu (Nanjing University of Aeronautics and Astronautics, Nanjing, China) On some special eccentricity-based graph Poster
The eccentricity εG(v) of a vertex v in a graph G is the maximum distance from v to other vertices in G. The eccentricity is a fundamental concept in metric graph theory. In this talk we report some results on the mathematical properties of several special eccentricity-based graphs, including almost self-centered (ASC) graphs and almost-peripheral (AP) graphs, and the minimum embedding of general graphs into them.
2018.15
30 November 2018 (Friday), 3-4pm, room 416
Baogang Xu (Nanjing Normal University, Nanjing, China) Partitions of graphs under minimum degree constraints: results and open problems Poster
Stiebitz (1996) confirmed a conjecture of Thomassen and proved that for nonnegative integers s and t, every graph of minimum degree s + t + 1 admits a partition (S, T) such that δ(G[S]) ≥ s and δ(G[T]) ≥ t.
In this talk, we will introduce some results and still open problems on this topic.
2018.14
26 November 2018 (Monday), 3-4pm, room 416
Shuto Nishida (Tokyo University of Science, Japan) Existence of 3-factors in star-free graphs with high connectivity Poster Slides
A graph is called K1,t-free (or t-star-free) if it contains no K1,t (or t-star) as an induced subgraph. We call a spanning r-regular subgraph of a graph an r-factor. Ota and Tokuda gave a minimum degree condition for a K1,t-free graph to have an r-factor [J. Graph Theory 22 (1996), 59-64]. Though their condition is best-possible, their sharpness examples have connectivity one. After that, some researchers have tried to improve the minimum degree condition by assuming larger connectivity. In this talk, we focus on a sufficient degree condition for the existence of 3-factors in star-free graphs with high connectivity.
2018.13
9 November 2018 (Friday), 3-4pm, room 416
Sergey Goryainov (Krasovskii Institute of Mathematics and Mechanics, Russia) On Deza circulants Poster Slides
We consider undirected graphs without loops and multiple edges. A k-regular graph Δ on v vertices is called a Deza graph with parameters (v, k, b, a) (usually a ≤ b), if the number of common neighbours of any two vertices takes precisely two values a or b. In my talk I’m going to discuss Deza graphs that are Cayley graphs of cyclic groups and some related results and open problems. The talk is based on a joint work in progress with Alexander Gavrilyuk and Leonid Shalaginov.
2018.12
15 October 2018 (Monday), 3-4pm, room 416
Pinkaew Siriwong (Chulalongkorn University, Thailand) k-zero-divisor hypergraphs Poster Slides
Graph structures and algebraic structures are related; that is, a zero-divisor graph. In master thesis, we generalized the idea of a zero-divisor graph into a k-zero-divisor hypergraph including the vertex set Z(R, k), the set of all k-zero-divisors of R where k ≥ 2. A subset {a1, a2, a3, ... , ak} of Z(R, k) is an (hyper)edge if and only if (i) a1a2a3 ... ak = 0 and (ii) the products of all elements of any (k − 1)-subsets of {a1, a2, a3, ... , ak} are nonzero. We provided (i) a necessary condition of commutative rings that implies the completeness of their k-zero-divisor hypergraphs; (ii) a necessary condition of commutative rings that implies the ability to partition their set of all k-zero-divisors into k partite sets and the completeness of that k-partite k-zero-divisor hypergraphs; and (iii) a necessary condition of commutative rings that implies the ability to partition their set of all σ-zero-divisors into k partite sets, for some integer σ ≥ k. Moreover, we determined its diameter and minimum length of all cycles. Recently, we have been interested in the vertex-pursuit game played on hypergraphs.
2018.11
14 September 2018 (Friday), 3-4pm, room 416
Yixin Cao (The Hong Kong Polytechnic University, Hong Kong; and Central South University, Changsha, China) Local coloring and its complexity Poster
A k-coloring of a graph is an assignment of integers between 1 and k to vertices in the graph such that the endpoints of each edge receive different numbers. We study a local variation of the coloring problem, which imposes further requirements on three vertices: We are not allowed to use two consecutive numbers for a path on three vertices, or three consecutive numbers for a cycle on three vertices. Given a graph G and a positive integer k, the local coloring problem asks for whether G admits a local k-coloring. We give a characterization of graphs admitting local 3-coloring, which implies a simple polynomial-time algorithm for it. Li et al. [Inf. Proc. Letters 130 (2018)] recently showed it is NP-hard when k is an odd number of at least 5, or k = 4. We show that it is NP-hard when k is even and k > 4, thereby completing the complexity picture of this problem.
2018.10
13 August 2018 (Monday), 9-10am, room 416
Hao Huang (Emory University, USA) Forbidding tight cycles in hypergraphs Poster Slides
A tight k-uniform l-cycle, denoted by TCkl, is a k-uniform hypergraph whose vertex set is v0, ... , vl−1, and the edges are all the k-tuples {vi, vi+1, ... , vi+k−1}, with subscripts modulo l. Motivated by a classic result in graph theory that every n-vertex cycle-free graph has at most n − 1 edges, Sós and, independently, Verstraëte asked whether for every integer k, a k-uniform n-vertex hypergraph without any tight k-uniform cycles has at most n−1Ck−1 edges. In this talk I will present a construction giving negative answer to this question, and discuss some related problems. Joint work with Jie Ma.
2018.9
4 July 2018 (Wednesday), 3-4pm, room 416
Hong-Jian Lai (West Virginia University, USA) Some progresses of studies of group connectivity and modulo orientations of graphs Poster
When investigating the 4-color problem, Bill Tutte in the 1950s introduced the theory of nowhere zero flows, and proposed the most fascinating flow conjectures of graphs. These conjectures are still open as of today. In 1992, Jaeger, Linial, Payan and Tarsi in JCTB proposed the non-homogeneous version of the nowhere zero flow problem, which is now known as the group connectivity problem of graphs. Tutte indicated that the nowhere zero 3-flow problem is equivalent to the modulo 3 orientation problem. The corresponding non homogeneous version of modulo orientation, now known as the strongly group connectivity problem, was proposed in 2007. In this talk, we will introduce these problems and report some of the recent progresses of these problems.
2018.8
22 June 2018 (Friday), 4-5pm, room 416
Tao Jiang (Miami University, OH, USA) Extremal results on cycles in hypergraphs Poster
A cycle of length m in a graph G consists of a cyclic list of m vertices x1, x2, ... , xm together with edges xixi+1 for i = 1, 2, ... , m (subscript mod m). Cycles are fundamental structures in the study of graphs. There are many classic extremal results on the study of cycles such as the Erdős-Gallai theorem on the density condition guaranteeing the existence of cycles of length at least a prescribed number and the Bondy-Simonovits theorem on the density condition guaranteeing cycles of a given exact length.
An r-uniform hypergraph H consists a set V of elements called vertices and a set E of elements called hyperedges (or edges) where each hyperedge is a subset of V of size r. In recent years there has been a lot of successful effort on extending some of the classic extremal results on cycles to uniform hypergraphs, where there are several natural notions of cycles for hypergraphs. In this talk, we discuss some of these results and briefly touch upon the tools employed in such a study.
2018.7
8 June 2018 (Friday), 5-6pm, room 416
Jia Huang (University of Nebraska at Kearney, USA) 0-Hecke algebra actions on quotients of polynomial rings Poster Slides
The representation theory of the symmetric group is fascinating and has rich connections with combinatorics. Many important representations of the symmetric group can be obtained by taking quotients of the polynomial ring. In this talk I will present analogous representations of a deformation of the symmetric group algebra called the 0-Hecke algebra, and discuss the combinatorial properties of these 0-Hecke representations. Part of this work is joint with Brendon Rhoades (University of California San Diego).
2018.6
1 June 2018 (Friday), 3-4pm, room 416
Jun Yan (Jinan University, Guangzhou, China) (Discrete) mathematics behind interactive proof Poster Slides
Interactive proof is an important notion in both complexity theory and cryptography. It incorporates interactiveness and randomness into the canonical mathematical proof, which not only greatly enlarges the scope of what can be proved, but also can achieve a variety of securities. Two inventors of interactive proof (Goldwasser and Micali) were awarded Turing award in 2012 for this great contribution.
In this talk, I will survey interesting (discrete) mathematics behind interactive proof, which includes concepts and techniques from many fields such as number theory, linear/abstract algebra, graph theory, probability theory, mathematical logic, coding theory, and so on. I will also briefly talk about new questions towards interactive proof raised by quantum computation and communication that I have been working on in the past few years.
I will try to avoid going deep into technical details in this talk, while focusing on stating basic results and explaining basic ideas. Nothing is assumed for audiences. All are welcome.
2018.5
11 May 2018 (Friday), 3-4pm, room 416
Weihua He (Guangdong University of Technology, Guangzhou, China) Some recent applications of Szemerédi’s Regularity Lemma Poster Slides
In this talk, I will introduce Szemerédi’s Regularity Lemma and present some applications on solving Hamiltonian problems. In particular, I will focus on the problem of placing specified vertices at precise locations on a Hamiltonian cycle.
2018.4
10 May 2018 (Thursday), 1:20-2:20pm, room 416
Mingji Xia (Institute of Software, Chinese Academy of Sciences, Beijing, China) On variable Lovász local lemma Poster
Lovász local lemma states that given a dependency relation of random events, under which the probabilities are bounded, these events cannot cover the whole space. In applications, the events are related, usually because they share random variables. In a more specific variable-event dependency relation, the events may require higher probabilities to cover the whole space. For some cases we show the new probabilities bounds, and answer whether there is a gap between the two bounds.
2018.3
20 April 2018 (Friday), 3-4pm, room 408
Zanbo Zhang (Guangdong Industry Polytechnic, Guangzhou, China) Triangle string and an augmentation theorem for vertex-disjoint triangle sets Poster
Vertex-disjoint triangle sets (triangle sets for short) have been studied extensively. Many theoretical and computational results have been obtained. While the maximum triangle set problem can be viewed as the generalization of the maximum matching problem, there seems to be no parallel result to Berge’s augmenting path characterization on maximum matching [C. Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 842-844]. In this talk, we describe a class of structures called triangle string, which is equivalent to the class of union of two triangle sets in a graph. Based on the concept of triangle strings, a sufficient and necessary condition that a triangle set can be augmented is given. We develop an algorithm to test whether a graph G with maximum degree 4 is a triangle string, and if G is a triangle string, we compute a maximum triangle set of it.
2018.2
23 March 2018 (Friday), 3-4pm, room 408
Chao Yang (SYSU, Guangzhou, China) The modular coloring of graphs Poster
In this talk, we first introduce the notion of modular coloring and modular chromatic number of graphs. Then we present some results and open problems on the modular chromatic numbers of several families of graphs, including trees, bipartite and Kneser graphs.
2018.1
8 January 2018 (Monday), 3-4pm, room 416
Muhuo Liu (South China Agricultural University, Guangzhou, China) Some results on partition problems of graphs Poster Slides
In this talk, we shall introduce some results on partition problems of simple undirected graphs. We mainly focus on the following problems: Bipartitions of graphs under degree constraints, minimum balanced bipartitions of graphs, and the conjecture of k-partitions of graphs by Bollobás and Scott.
Talks in 2017 2018 2019 2020 2021 2022 2023
Back to main page