Discrete Random Structures and Additive Number Theory

该提案的研究部分涉及两个整体主题，其中P.I.在过去的几年里一直在调查。首先是随机对象的研究，如随机图，随机矩阵和随机游动。该研究是现代组合学的中心课题之一，与理论计算机科学和统计物理等几个快速发展的领域有着重要的联系.私家侦探和他的同事们讨论了几个关于随机图的各种模型的开放性问题，主要集中在随机正则图上。他们还攻击图上的随机游动和随机矩阵的谱的几个问题。其中一些问题在实践中具有很高的潜力，从计算机科学的角度来看非常令人兴奋。例如，该提案的关键问题之一是找到一种快速算法来生成随机图。该提案的第二个主题是添加剂理论。这是私家侦探讨论了各种和集上最长等差数列的长度问题。例如，一个典型的问题是：给定m个从1到n的整数，由这些整数的部分和得到的最长算术级数的长度是多少。他还研究了一个关于薄基的基本问题，这可以追溯到六十多年前西顿提出的一个问题。下面是一个示例问题：什么是素数集合P的最小密度，使得每个自然数都可以表示为P的最多100个元素的和？随机对象，如随机图和随机漫步，长期以来一直被广泛用于模拟现实生活中的过程（例如，考虑粒子的运动）。 最新的，也许是最令人兴奋的例子是互联网图，它被建模为一个随机图，其中每个节点（站点）的连接数量满足某些定律。因此，随机对象的研究不仅在理论上具有挑战性，而且在实际应用中具有很大的潜力。很大一部分私家侦探。的工作是更好地理解随机图，以回答非常基本的问题，如“图如何扩展？或者“如果添加更多的边（连接），图形会如何变化？“或“如何用计算机模拟一个随机图”。尽管这些问题很简单，但多年来一直是悬而未决的，它们的答案可能需要发展全新的思想和方法。P.I.的第二部分的工作涉及数论中的经典问题，动机是伟大的数学家，如华林，鄂尔多斯，弗赖曼和西顿的结果和问题。这一部分的工作将有助于对自然数的可加性有更好的理解.

The research component of this proposal involves two overalltopics, which the P.I. has been investigating in the past fewyears. The first is the study of random objects such as randomgraphs, random matrices and random walks. This study is one of thecentral topics in modern combinatorics with vital connectionsseveral fast developing areas such as theoretical computer scienceand statistical physics. The P.I. and his colleagues considerseveral 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. considersquestions 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 beenwidely used to model real-life processes for a long time (think ofthe 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 bycomputers". Despite their simplicity, these questions have beenopen for many years and their answers might require the developmentof entirely new ideas and methods. The second part of the P.I.'swork deals with classical questions in number theory, motivated byresults and questions of great mathematicians such as Waring,Erdos, Freiman and Sidon. The work in this part would lead to abetter understanding of the additive properties of naturalnumbers.