Combinatorics Seminar 2017

Speaker: Yizhe Zhu (朱亦哲), University of Washington

Date: Thu, Sep 14, 2017

Time: 16:30 - 17:30

Venue: Middle Meeting Room

Title: A graphon approach to spectral analysis of random matrices and random graphs


Graphons were introduced in 2006 by Lovász and Szegedy as limits of graph sequences. Roughly speaking, the set of finite graphs endowed with the cut metric gives rise to a metric space, and the completion of this space is the space of graphons. These objects may be realized as symmetric, Lebesgue measurable functions from $[0, 1]^2$ to $[0, 1]$. They also characterize the convergence of graph sequences based on graph homomorphism densities.

We will present a graphon approach to the limiting spectral distribution of general Wigner-type matrices. A sufficient condition of the existence of limiting spectral distribution and an asymptotic formula to calculate moments are obtained in terms of homomorphism density from trees to graphons. Moreover, we have a combinatorial interpretation of the quadratic vector equations of limiting measures.

As applications, we will present alternative proofs of several results in random matrix theory with weaker assumptions, and we are able to decide the limiting spectral distributions for new random graph models arising in network modeling and machine learning: sparse W-random graphs and heterogeneous stochastic block models.

This is joint work with Ioana Dumitriu.