The PIs propose to investigate the structure of sets of integers without long arithmetic progressions and to extend these questions to cosets of subspaces in finite fields. They also propose to find sharp estimates for the size of sum-sets in various sets and for sum-product estimates (both 2-fold and k-fold) for integers and prime fields, as well as to describe the structure of sum-free sets. The graph theory part of the proposal contains questions about triangle-free graphs, the Burr-Erdos Conjecture, and the Komlos-Sos Conjecture.
The PIs propose to develop new tools to deal with some challenging and important classical problems of Discrete Mathematics. The PIs have extensive background and experience related to these questions, some of the advanced tools used today in Discrete Mathematics were originally developed by the PIs. The proposed topics in additive numbers theory and in graph theory are applicable in mathematics and the sciences, especially in Fourier analysis and in practical algorithms, in number theory, in geometry, in graph theory and combinatorics, and in designing and analysing efficient computer algorithms (complexity theory). The subject of Discrete Mathematics is the investigation of finite mathematical objects and their structures. Discrete Mathematics is a rapidly growing area of mathematics with many theoretical and practical applications. Arithmetic Combinatorics is a field investigating the interplay between Number Theory and Discrete Mathematics, using deep combinatorial and Fourier analytic methods to understand additive structures of sets of positive integers. Graph Theory is the study of networks, modelling connection patterns in various mathematical and applied settings.
Analyzing complex networks became a central aspect of modern science. It involves a large number of mathematical disciplines from graph theory to combinatorics, probability theory, mathematical statistics, number theory, statistical physics, and many more. The work the Principle Investigators (PIs) conducted under the grant were mostly on the fields of graph theory and additive number theory. The grant proposed a theoretical investigation of several graph models. Important tools were developed by the co-PI, and then by the PI and the co-PI in cooperation with other researchers. Together they introduced new tools to model certain classes of random graphs as well as to approximate deterministic networks with randomly behaving ones. These tools turned out to be useful in discrete mathematics, computer theory, and number theory. Through these fields they also had an impact on the general theory of networks, adding to the intellectual merit of the work. The PIs also investigated problems in extremal graph theory and number theory, questions of the following type: Do various density conditions on large discrete structures or large sets of integers guarantee the existence of certain substructures in them. In some ways these results complement as well as extend the so-called Ramsey Theory, which roughly speaking states that even in very chaotic systems of various kinds there are some smaller very strictly ordered subsystems. The project had broader impact on education in two ways. 1: the co-PI had graduate students supported by the grant and published a number of papers with them, as well as invited them to conferences where they presented the material to wider audiences. 2: the PI has been running for many years a successful REU program (Research Experiences for Undergraduates). This prepared undergraduates for substantial scientific research; some students already achieved publishable results. The REU program strongly promotes women and minorities.
