Theory of graph homomorphisms and extremal combinatorics

图同态和极值组合理论

• 批准号: 408045-2011
• 负责人: Hatami, Hamed
• 金额: $ 1.31万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=573404
• 关键词: Theory; graph; homomorphisms; extremal; combinatorics

Discrete mathematics or combinatorics is a fundamental mathematical discipline which focuses on the study of discrete objects and their properties. This area which is as old as the human ability to count, has attracted many strong mathematicians and is experiencing tremendous growth during the last fifty years. One of the main reasons for this is its intimate connection with computer science, the utility of which is obvious. Moreover combinatorics has applications to probability, set theory, cryptography, communication theory, the geometry of Banach spaces, harmonic analysis, number theory, ... the list goes on and on. However, still many of these applications would fail to impress many mathematicians who regard combinatorics as a large collection of isolated results and problems that can be disregarded as technical part of mathematics. This I believe is mainly due to the fact there has not been much theory developed to connect these results and problems to each other. However, in the last decade, this has started to change, and this change has gained more speed recently. A significant part of modern extremal combinatorics is dedicated to the study of the asymptotic relations between subgraph densities. These relations are usually expressed as algebraic inequalities between subgraph densities. Despite the variety of ingenious and hard results in asymptotic graph theory, surprisingly, there seem to exist only a handful of essentially different techniques in this area, and many known results are proven by clever combinations these techniques and tools. In recent years a new line of researches in the direction of developing theories that explains these similarities in the proofs of various seemingly very different results in this area has emerged. The purpose of this line of research is to develops a general theory that (1) reveals the general nature of this area of mathematics (2) encompasses the main techniques used in this area and provides methods for applying them in an automated manner (3) provides new tools for solving the large collection of open problems in this area. The problems that I am working on are the general problems that reveal the limitations and powers of these theories. These problems if solved will increase our general understanding of the nature of the area of extremal combinatorics. An important result in this area says that many theorems follow from the positive semi-definiteness of a certain infinite matrix. This positive semi-definite characterization is a powerful approach for proving such inequalities. This method is very convenient to program, so that the search for ``right'' relations can be to a large degree computerized. In other words, in this area certain type of problems which were previously solved by tedious work of important mathematics can now be solved by a computer problems. I have already used this method to solve an open problem, and in the future I am planning to combine this method with other auxiliary tools and techniques to attack to various open problems in extremal graph theory.

离散数学或组合数学是一门基础数学学科 它专注于离散对象及其属性的研究。这片区域的历史 人类的计数能力，吸引了许多强大的数学家，并在过去的五十年里经历了巨大的增长。其中一个主要原因是它与计算机科学的密切联系，其实用性是显而易见的。 此外，组合数学的应用概率，集合论，密码学，通信理论，几何的Banach空间，调和分析，数论，...这样的例子不胜枚举。 然而，仍然有许多这些应用程序将无法打动许多数学家谁认为组合数学作为一个大集合的孤立的结果和问题，可以忽略作为技术的一部分数学。我认为这主要是由于没有太多的理论来把这些结果和问题联系起来。然而，在过去十年中，这种情况开始发生变化，最近这种变化的速度更快。 现代极值组合学的一个重要部分是致力于研究子图密度之间的渐近关系。这些关系通常表示为子图密度之间的代数不等式。尽管各种巧妙的和困难的结果在渐近图论，令人惊讶的是，似乎只存在少数本质上不同的技术在这一领域，许多已知的结果证明了这些技术和工具的巧妙组合。 近年来，在发展理论的方向上出现了一条新的研究路线，这些理论在证明这一领域各种看似非常不同的结果时解释了这些相似之处。这条研究路线的目的是开发一个通用理论，（1）揭示数学这一领域的一般性质（2）包括这一领域使用的主要技术，并提供以自动化方式应用它们的方法（3）提供新的工具来解决这一领域的大量开放问题。 我正在研究的问题是揭示这些理论的局限性和力量的一般问题。这些问题的解决将增加我们对极值组合学领域性质的一般理解。 在这方面的一个重要结果说，许多定理遵循的积极半定的某一无限矩阵。这种半正定特征是证明此类不等式的有力方法。这种方法编程非常方便，因此寻找“正确”关系在很大程度上可以计算机化。换句话说，在这方面的某些类型的问题，以前解决了繁琐的工作，重要的数学，现在可以解决的计算机问题。 我已经用这种方法解决了一个开放的问题，在未来，我计划联合收割机这种方法与其他辅助工具和技术，以攻击极端图论中的各种开放问题。