Random Graphs, Random Matrices and Subset sums

Yale University, New Haven CT

Investigators

Abstract

ABSTRACT Principal Investigator: Vu, Van Proposal Number: DMS - 0901216 Institution: Rutgers University New Brunswick Title: Random Graphs, Random Matrices and Subset sums The 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.