Lecture Series of Department of Mathematics of College of Information Science and Technology/ College of Cyber Security (No. 39 & No.40)

Topic：The Non-deterministic Constraint Logic on Digraphs and Its Applications in Computational Complexity

Lecture | November 16, 2017 | 2:00 p.m. | Room 224 in Nanhai Building

Speaker: Yang Chao, Sun Yat-sen University

ABOUT YANG CHAO

Yang Chao, doctor, associate research fellow, obtained his doctoral degree from the University of Science and Technology of China in 2007. He worked as a visiting researcher in Texas State University from 2009 to 2010. His research interests are combinatorics and graph theory and theoretical computer science. He have directed Tianyuan Special Fund Project and Young Scientist Fund Project of National Natural Science Foundation. 

ABSTRACT

This talk will be divided into two parts. In the first part, we will review some results on the computational complexity of combinatorial puzzles. In the second part, we will introduce the the Non-deterministic Constraint Logic (Ncl). Ncl is a decision problem defined on a special type of directed graphs. The Ncl problem is PSPACE-complete, and it can be used to determine the computational complexity of several combinatorial puzzles.

The uniform method and polar diagram of spectral radius ordering

Lecture | November 16, 2017 | 3:30 p.m. | Room 224 in Naihai Building 

Speaker: Liu Mu-huo, South China Agricultural University

ABOUT LIU MU-HUO

Liu Mu-huo is an associate professor and master supervisor at South China Agricultural University, a commentator of Mathematical Reviews, young council of Combinatorics and Graph Theory Branch, Operations Research Society of China. His main research interests include graph partition and algebraic graph theory. He has published more than 70 papers in mathematics journals including Science in China, Acta Mathematica Sinica, The Electronic Journal of Combinatorics, Discrete Mathematics, Linear Algebra and its Applications, Discrete Applied Mathematics, of which more than 60 papers are published in or accepted by SCI. The book The polar theory of the spectrum published by him as the first author was funded by Guangdong Foundation for Excellent Scientific and Technical Monograph Publishing. He has directed many projects such as projects of National Natural Science Foundation, Excellent Youth Innovation Talent Training Program in Guangdong Colleges and Universities, and Training Program of Excellent Young Teachers in Guangdong colleges and universities. He won National Scholarship for doctoral students in 2013, and he was selected as one of the eighth university-level training objects of “Ten-Hundred-Thousand” program in Guangdong colleges and universities in 2014 and one of the training orojects of Excellent Young Teachers Training Program in Guangdong colleges and universities. 

ABSTRACT

Graph spectral expert D.M. Cvetkovic pointed out 12 directions of graph spectral research in his paper Algebra Methods in Graph Theory (D.M. Cvetkovic,Algebra Methods in Graph Theory, Amsterdam, 1981, 47-67) , of which one direction is classification and ordination according to the spectra of graphs. Since then a great deal of study on the ordination of spectral radius or (unsigned) Laplace spectral radius according to the spectra of graphs has been made by later generations. In this report, we will introduce the research findings on the uniform method and polar diagram of spectral radius ordering.