Random Graphs, Random Matrices and Subset sums

随机图、随机矩阵和子集和

• 批准号: 1212424
• 负责人: Van Vu
• 金额: $ 32.56万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1212424&HistoricalAwards=false
• 关键词: Random; Graphs; Matrices; Subset; sums

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.

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