Some problems in Arithmetic Combinatorics and Graph Theory

点击翻译按钮获取中文摘要

ABSTRACTPrincipal Investigator: Komlos, Janos Co-Principal Investigator: Endre SzemerediProposal Number: DMS - 0902241Institution: Rutgers University New BrunswickTitle: Some problems in Arithmetic Combinatorics and Graph TheoryThe 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.