Extremal graph theory and Ramsey theory

极值图论和拉姆齐理论

• 批准号: RGPIN-2016-05959
• 负责人: Gunderson, David
• 金额: $ 1.09万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=652673
• 关键词: Extremal; graph; theory; Ramsey

***My proposed research is primarily in two areas of mathematics, Ramsey theory and extremal graph theory.******Ramsey theory is an area of combinatorics that was, in a sense, initiated by work in logic and, independently, geometry early in the 20th century. It now includes results from graph theory and number theory. Basically, a typical "Ramsey-type" result says that for many classes of structures (e.g., the natural numbers, or graphs) any large structure has the property that whenever certain substructures are partitioned, "homogeneous" patterns can be found in one part. To give one example, if the natural numbers are partitioned into two sets, then by a theorem due to van der Waerden, there exist arbitrarily long arithmetic progressions in one of the sets. ******Ramsey theory is now rather well-developed, and has since found application in many fields, from graph theory to geometry. Ramsey type problems have inspired (and contributed to) advanced research in many mathematical fields, including number theory, lattice theory, set theory, topology, theoretical computer science and probability, to name but a few. I intend to concentrate on Ramsey theory in graph theory, and on some interesting connections with numbers, including the primes and additive combinatorics.******In mathematics, an area called "graph theory" does not deal with graphs of functions (like parabolas), but instead deals with "networks" consisting of "vertices" (points) and "edges" (connections) between vertices. Modern graphs can be used to model algorithms, job allocations, transportation, computer networks (including the internet), epidemiology, or even social networks. ******One specialization in graph theory is called "extremal graph theory''. In extremal graph theory, one might ask how "dense" a certain graph must be before a chosen (smaller) graph is guaranteed to appear. For example, if a graph on 100 vertices has more than 2500 edges (about half of the 4950 possible) a triangle is guaranteed to appear. Another central question is to determine which graphs are the densest while still not containing the chosen small graph. Such "extremal graphs" can be used to provide critical examples in complexity, number theory, or geometry. Many results in extremal graph theory arose from questions in combinatorial number theory. For example, in 1938, Erdös asked how many numbers from 1 to n can be chosen whose pairwise products are all different? This was answered by examining certain extremal graphs (that forbid a simple four-cycle graph as a subgraph).******On the other hand, certain examples from finite geometries or number theory are used to provide answers to Ramsey-type problems or extremal graph theory problems. One feature of studying in these two areas is that not only does one get to learn (and use) many fantastic results from various areas of mathematics, but results in these two areas also contribute back to so many other fields of research.*****

***我提出的研究主要在数学，拉姆西理论和极端图理论的两个领域。现在，它包括图理论和数字理论的结果。基本上，一个典型的“拉姆西型”结果表明，对于许多类别的结构（例如自然数或图形），任何大结构都具有每当分配某些子结构时，可以在一个部分中找到“均质”模式。举一个例子，如果将自然数分为两组，则是由于范德沃登（Van der Waerden）引起的定理，则其中一个集合中存在任意长的算术进程。 *****拉姆西理论现在已经相当发达，此后在从图理论到几何形状的许多领域中发现了应用。拉姆西的类型问题激发了许多数学领域的高级研究的启发，包括数字理论，晶格理论，集合理论，拓扑，拓扑，理论计算机科学和概率，仅举几例。我打算专注于图理论中的拉姆西理论，以及一些有趣的数字连接，包括数字和添加剂组合学。现代图可用于建模算法，作业分配，运输，计算机网络（包括互联网），流行病学甚至社交网络。 *****一个图形理论的一种专业称为“极端图理论”。在极端图理论中，人们可能会问一个“密集”某个图表必须在选择（较小的）图表出现之前。 “极端图”可用于在复杂性，数字理论或几何学上的重要示例。有限几何或数字理论的示例用于为拉姆西型问题或极端图理论问题提供答案。在这两个领域学习的一个特征是，不仅可以学习（并使用）各个数学领域的许多出色结果，而且在这两个领域的结果也可以恢复了许多其他研究领域。**** ************