Eigenvectors of random graphs & diffusions on simplices

PI在他的概率论研究中提出了两个长期的方向。第一部分涉及稀疏随机图的谱和特征向量性质的研究。这是与Ioana Dumitriu合作的作品。图邻接矩阵或拉普拉斯矩阵的特征向量作为组合优化问题的解具有天然的意义。然而，关于随机图的特征向量的理论结果却很少。我们正在进行的研究结合了随机矩阵理论和图组合学的方法和直觉。到目前为止，我们已经成功地获得了随机正则图的有趣结果，我们表明，当度随着阶数多对数增长时，邻接矩阵显示出高斯正交集合的一些性质。最终，我们计划研究“真实世界”的图，特别是具有给定度分布的图。第二个方向是构建和研究连续统树空间上的扩散，其可逆测度为David Aldous猜想的布朗CRT。这表现为有限系统发育树上自然离散马尔可夫链的极限。连续体树是几种随机树族和随机平面图（通过Schaeffer双射）的极限状态空间，具有重要的意义。从我们正在进行的研究中可以看出，这种极限扩散是这种树空间上的一种新的测量值过程，让人想起经典的弗莱明-维奥模型。所提出的方法是PI在最近相关工作中发展的思想的延续。随机图和网络在社交网络、互联网模型、计算机视觉和数论等各个领域都很流行。图上的一些自然优化问题（例如，计算聚类，或排序算法，如b谷歌PageRank）涉及图的特征向量。如果网络是随机增长的，那么它的特征向量是随机的，研究它的性质是有意义的。这些性质的研究被列为我们的主要研究领域之一。另一个主要领域涉及系统发生（或进化）树的结构。最近对生物学和相关数学的很多兴趣都集中在所有可能的进化树的集合结构上。这是一个巨大的空间，与通常的欧几里得空间（比如三维空间）非常不同。探索这个集合的一种方法是让马尔可夫链以一种“漂亮”的方式随机地从一棵树跳到另一棵树。文献中已经提出了一些这样的模型。我们开始研究其中一个与其他概率论领域有关的问题。分析和结果预计将是相当新颖的学科领域。

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.