Discrete Random Structures and Additive Number Theory

University Of California-San Diego, La Jolla CA

Investigators

Abstract

The research component of this proposal involves two overall topics, which the P.I. has been investigating in the past few years. The first is the study of random objects such as random graphs, random matrices and random walks. This study is one of the central topics in modern combinatorics with vital connections several fast developing areas such as theoretical computer science and statistical physics. The P.I. and his colleagues consider several open questions about various models of random graphs, with the main focus on random regular graphs. They also attack several problems on random walks on graphs and the spectra of random matrices. Some of these questions have high potential in practice and are very exciting from the computer science point of view. For instance, one of the key questions of the proposal is to find a fast algorithm to generate a random graph. The second topic of the proposal is additive theory. Here the P.I. considers questions about the length of the longest arithmetic progression in various sum sets. For instance, a typical question is the following: Given m integers from 1 to n, what is the length of the longest arithmetic progression obtained by the partial sums of these integers. He also studies a fundamental problem about thin basis, which went back to a problem posed by Sidon more than sixty years ago. Here is a sample question: What is the smallest density of a set P of primes so that every natural number can be represented as a sum of at most 100 elements of P ? Random objects such as random graphs and random walks have been widely used to model real-life processes for a long time (think of the movement of a particle, for instance). The newest and perhaps most exciting example is the Internet graph, which has been modelled as a random graph where the number of connections to each node (site) satisfies certain laws. Therefore, the study of random objects is not only theoretically challenging but also has high potential in practical applications. A large part of the P.I.'s work is to develop a better understanding of random graphs to answer very fundamental questions such as "how does the graph expand ?" or "how does the graph change if more edges (connections) are added ?" or "how to simulate a random graph by computers". Despite their simplicity, these questions have been open for many years and their answers might require the development of entirely new ideas and methods. The second part of the P.I.'s work deals with classical questions in number theory, motivated by results and questions of great mathematicians such as Waring, Erdos, Freiman and Sidon. The work in this part would lead to a better understanding of the additive properties of natural numbers.