PhD Defence Dan Hu

The spectral analysis of random graph matrices 

Dan Hu is a PhD student in the Formal Methods and Tools research group her supervisors are prof.dr.ir. H.J. Broersma from the Faculty of Electrical Engineering, Mathematics and Computer Science  and prof.dr. S. Zhang from the University Xi'an China. 

This thesis contains a number of results on the spectra and related spectral properties of several random graph models.

In Chapter 1, we briefly present the background, some history as well as the main ideas behind our work. Apart from the introduction in Chapter 1, the first part of the main body of the thesis is Chapter 2. In this part we estimate the eigenvalues of the Laplacian matrix of random multipartite graphs. We also investigate some spectral properties of random multipartite graphs, such as the Laplacian energy, the Laplacian Estrada index, and the von Neumann entropy.0

The second part consists of Chapters 3, 4, 5 and 6. In [67], Guo and Mohar showed that mixed graphs are equivalent to digraphs if we regard (replace) each undirected edge as (by) two oppositely directed arcs. Motivated by the work of Guo and Mohar, we initially propose a new random graph model – the random mixed graph. Each arc is determined by an in-dependent random variable. The main themes of the second part are the spectra and related spectral properties of random mixed graphs.

In Chapter 3, we prove that the empirical distribution of the eigenvalues of the Hermitian adjacency matrix converges to Wigner’s semicircle law. As an application of the LSD of Hermitian adjacency matrices, we estimate the Hermitian energy of a random mixed graph.

In Chapter 4, we deal with the asymptotic behaviour of the spectrum of the Hermitian adjacency matrix of random mixed graphs. We derive a separation result between the first and the remaining eigenvalues of Hn. As an application of the asymptotic behaviour of the spectrum of the Hermitian adjacency matrix, we estimate the spectral moments of random mixed graphs.

In Chapter 5, we prove that the empirical distribution of the eigenvalues of the normalized Hermitian Laplacian matrix converges to Wigner’s semicircle law.

Moreover, in Chapter 6, we provide several results on the spectra of general random mixed graphs. In particular, we present a new probability inequality for sums of independent, random, self-adjoint matrices, and then apply this probability inequality to matrices arising from the study of random mixed graphs. We prove a concentration result involving the spectral norm of a random matrix and that of its expectation. Assuming that the probabilities of all the arcs of the mixed graph are mutually independent, we write the Hermitian adjacency matrix as a sum of random self-adjoint matrices. Using this, we estimate the spectrum of the Hermitian adjacency matrix, and prove a concentration result involving the spectrum of the normalized Hermitian Laplacian matrix and its expectation.

Finally, in Chapter 7, we estimate upper bounds for the spectral radii of the skew adjacency matrix and skew Randić matrix of random oriented graphs.