Some problems in Arithmetic Combinatorics and Graph Theory

主要研究人员：Komlos，Janos共同首席研究人员：Endre SzmerediProposal Number：DMS-0902241机构：罗格斯大学新不伦瑞克分校题目：算术组合学和图论中的一些问题PI建议研究没有长算术级数的整数集的结构，并将这些问题推广到有限域中的子空间陪集。他们还建议找到各种集合中和集的大小的精确估计，以及整数和素域的和积估计(2倍和k倍)，以及描述无和集的结构。该提案的图论部分包含关于无三角形图、Burr-Erdos猜想和Komlos-SOS猜想的问题。PI建议开发新的工具来处理一些具有挑战性的和重要的离散数学经典问题。PI在这些问题上有广泛的背景和经验，今天在离散数学中使用的一些高级工具最初是由PI开发的。所提出的加数理论和图论主题适用于数学和科学，特别是傅立叶分析和实用算法、数论、几何、图论和组合学，以及设计和分析有效的计算机算法(复杂性理论)。离散数学的主题是研究有限的数学对象及其结构。离散数学是一个迅速发展的数学领域，有着许多理论和实际应用。算术组合学是一个研究数论和离散数学之间相互作用的领域，它使用深入的组合和傅立叶分析方法来理解正整数集的加法结构。图论是对网络的研究，在各种数学和应用环境中对连接模式进行建模。

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.