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.
Much of our modern world depends on large sparse networks. Examples could be a network of computers, network of people according to their geographic location, social networks, or even network of actors working together. These networks all share a few common features: they are large, but every node has at most a hundred or so nodes (called neighbors) with which it shares edges. Moreover, if we draw the histogram the number of neighbors of each node, the resulting shape appears to be independent of the particular network. Several of the projects supported by this grant are devoted to analysis of such networks. We simplify the situation by assuming that every node has the same degree (which in reality could be the average degree). We want to undersand how cycles are formed in this network, how they evolve as the network increases in size and how are they distributed. We also wanted to understand how mathematical objects calles eigenvalues and eigenvectors of these networks behave. Such objects are often useful: the Google page rank algorithm depends on eigenvectors of such a network. A recent burgeoning field in mathematics is called Random Matrix Theory (RMT), which as the name suggests, studies random matrices with surprisingly far-reaching connections. We show how ideas and intutions from RMT extends to the study of large networks, although the mathematics is quite different. Our work is one of the first systematic connection between these two disparate areas. Intituions from RMT allow us to guess the behavior of cycles, eigenvalues, and eigenvectors of large networks. We can verify such guesses by simulation and then build an actual proof based on these intuitions. This gives us surprising and beautiful results on the graph structure far beyond the classical combinatorial study of graphs. Since we are only beginning the field, I have no doubt that many new wonders will await us in the future.
