Eigenvectors of random graphs & diffusions on simplices

University Of Washington, Seattle WA

Investigators

Abstract

The PI proposes two long term directions in his research in Probability theory. The first one involves study of spectral and eigenvectors properties of sparse random graphs. This is a joint work with Ioana Dumitriu. Eigenvectors of graph adjacency or laplacian matrices have natural significance as solutions of combinatorial optimization problems. However, very little theoretical results are known about eigenvectors of random graphs. Our ongoing investigation combines methods and intuition from the Random Matrix Theory with graph combinatorics. We have so far succeeded in obtaining interesting results for random regular graphs where we show that, when the degree grows poly-logarithmically with the order, the adjacency matrix displays some of the properties of the Gaussian Orthogonal Ensembles. Eventually we plan to study ``real world'' graphs, particularly the ones with a given degree distribution. The second direction is the construction and study of a diffusion on the space of continuum trees whose reversible measure is the Brownian CRT, as conjectured by David Aldous. This appears as a limit of natural discrete Markov chains on finite phylogenetic trees. Continuum trees are of great significance as they appear as the limiting state space of several families of random trees and random planar maps (via Schaeffer bijection). It appears from our ongoing study that this limiting diffusion is a new kind of measure-valued process on the space of such trees, reminiscent of the classical Fleming-Viot model. The proposed method is a continuation of ideas developed by the PI in related recent work. Random graphs and networks are popular in diverse areas such as social networks, models for the internet, computer vision, and number theory. Several natural optimization problems on graphs (e.g., figuring out clusters, or ranking algorithms such as Google PageRank) involve what are called eigenvectors of the graph. If the network grows randomly, its eigenvectors are random, and it is of interest to study its properties. A study of such properties is listed as one of our main research areas. The other main area involves the structure of phylogenetic (or evolutionary) trees. A lot of recent interest in Biology and related mathematics is in the structure of the collection of all possible evolutionary trees. This is an enormous space very different from the usual Euclidean (say, three dimension) space. One way to explore this set is to let a Markov chain jump around from tree to tree randomly in a ``nice'' way. A few such models have been proposed in the literature. We take up the study of one of them which is related to other areas of Probability. The analysis and results are expected to be quite novel in the subject area.