Extremal graph theory and Ramsey theory

极值图论和拉姆齐理论

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

我建议的研究主要是在两个领域的数学，拉姆齐理论和极值图论。 拉姆齐理论是组合数学的一个领域，从某种意义上说，它是由世纪早期的逻辑学和几何学的工作独立地发起的。 它现在包括图论和数论的结果。基本上，一个典型的“拉姆齐型”结果表明，对于许多类型的结构（例如，自然数或图）任何大的结构都具有这样的性质，即无论何时分割某些子结构，都可以在一个部分中找到“同质”模式。举一个例子，如果自然数被划分为两个集合，那么根据货车德瓦尔登的定理，在其中一个集合中存在任意长的算术级数。 Ramsey理论现在已经相当发达，并且已经在从图论到几何学的许多领域中找到了应用。 Ramsey型问题激发了（并促进了）许多数学领域的高级研究，包括数论，格论，集合论，拓扑学，理论计算机科学和概率，仅举几例。我打算集中在图论中的拉姆齐理论，并在一些有趣的连接数，包括素数和加法组合。 在数学中，一个叫做“图论”的领域并不处理函数的图形（如抛物线），而是处理由“顶点”（点）和顶点之间的“边”（连接）组成的“网络”。现代图可用于建模算法、工作分配、交通、计算机网络（包括互联网）、流行病学甚至社交网络。 图论中的一个专门化称为“极值图论”。 在极值图论中，人们可能会问，在保证出现一个选定的（更小的）图之前，某个图必须有多“密集”。例如，如果一个有100个顶点的图有超过2500条边（大约是4950条边的一半），那么肯定会出现一个三角形。另一个中心问题是确定哪些图是denatrium，同时仍然不包含所选择的小图。这样的“极值图”可以用来提供复杂性、数论或几何学中的关键例子。极图理论中的许多结果都来自于组合数论中的问题。例如，在1938年，埃尔德什问有多少数字从1到n可以选择其成对产品都是不同的？ 这是回答检查某些极值图（禁止一个简单的四圈图作为一个子图）。 另一方面，有限几何或数论中的某些例子被用来提供拉姆齐型问题或极图理论问题的答案。在这两个领域学习的一个特点是，人们不仅可以学习（和使用）来自数学各个领域的许多奇妙的结果，而且这两个领域的结果也有助于许多其他领域的研究。