Random Graphs, Random Matrices and Subset sums

摘要项目负责人：Vu， Van，提案编号：DMS - 0901216机构：Rutgers University New brunswick题目：随机图，随机矩阵和子集和PI将研究随机图和随机矩阵的几个基本问题。例如，就随机图而言，他将专注于寻找随机图和超图中因子存在的尖锐阈值问题，其中一个特殊的例子是Shamir关于随机超图中完美匹配猜想的尖锐版本。他还将研究随机提升中的展开，以及Erd\ os-R\ enyi随机图和随机正则图的夹心猜想。对于随机矩阵，他提出研究随机伯努利矩阵的奇点概率、行列式和恒式的分布、特征值和特征向量的性质等问题。其中一些问题与理论计算机科学中的问题有着密切的联系。PI还将继续他在加性组合学中的结构定理的研究，特别是那些与其他领域有密切联系的定理，如数论和概率论。长期以来，科学家们一直使用随机性来模拟自然界中出现的巨大而困难的结构。一个著名的例子是维格纳使用随机矩阵的光谱来模拟原子的能级。另一种是使用随机图来模拟现实生活中的图，比如互联网。PI计划是对随机矩阵和随机图进行系统的研究，并结合数论中的一些问题，令人惊讶的是，这些问题被证明是相关的。他坚信，对提出的问题进行系统的研究，最终将导致新思想和新工具的发展，这些新思想和工具可以用于许多其他主题，并加深对数学各个领域之间关系的理解。

ABSTRACTPrincipal Investigator: Vu, Van Proposal Number: DMS - 0901216 Institution: Rutgers University New BrunswickTitle: Random Graphs, Random Matrices and Subset sumsThe PI is going to work on several basic problems concerning random graphs and random matrices. For example, as far as random graphs are concerned, he will be focusing on the problem of finding sharp thresholds for the existence of factors in random graphs and hypergraphs, a special case of which is the sharp version of Shamir's conjecture on perfect matching in random hypergraphs. He will also study expansion in random lifts and the sandwiching conjecture concerning Erd\"os-R\'enyi random graphs and random regular graphs. For random matrices, he proposes to study many problems concerning random Bernoulli matrices, such as probability of singularity, distributions of determinants and permanents, and properties of eigenvalues and eigenvectors. Several of these problems have strong connection to problems in theoretical computer science. The PI will also continue his study of structural theorems in additive combinatorics, in particular those which have strong links to other fields, such as number theory and probability.For a long time, randomness has been used by scientists to model huge and difficult structures that occur in nature. One famous example is Wigner's use of the spectra of random matrices to model energy levels of atoms. Another is the use of random graphs to model real life graphs such as the Internet. The PI plan is to make a systematic study of random matrices and random graphs, together with some problems in number theory, which, quite surprisingly, have turned out to be related. He strongly believes that a systematic study of the proposed problems will eventually lead to the developments of new ideas and tools, which can be useful in many other topics, and to a deeper understanding of the relations between various fields of mathematics.