Extremal and Probabilistic Combinatorics via Regularity and Graph Limits

通过正则性和图极限的极值和概率组合

• 批准号: 1100215
• 负责人: Tom Bohman
• 金额: $ 24.66万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2015-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1100215&HistoricalAwards=false
• 关键词: Extremal; Probabilistic; Combinatorics; via; Regularity

The PI will continue his research in combinatorics and graph theory concentrating on probabilistic and extremal questions. Random structures and processes, while being an important object of study of their own, are also very effective in solving problems of discrete mathematics including those whose statement is purely deterministic. An important area of their successful application is extremal combinatorics where, broadly speaking, one has to maximize or minimize a certain parameter given some combinatorial restrictions. One example of an extremal question is the Turan function, the maximum size of a hypergraph without some fixed forbidden subgraph. This is a fundamental and key question that asks how local restrictions can affect the global structure. Despite decades of active attempts, most Turan-type questions remain wide open, such as the famous tetrahedron conjecture made by Paul Turan back in 1941. During attacks on these difficult problems mathematicians developed a number of useful and general techniques such as, for example, the Regularity Lemma. The more recent concepts of (hyper)graph limits and flag algebras seem to be very powerful tools for studying finite structures and for providing new methods of operating with large discrete objects. The PI will work on a number of combinatorial questions, in particular seeking new ways of applying these techniques. Some promising directions include the Turan function, the stability property, inequalities between subgraph densities (for example, minimizing the number of F-subgraphs in a graph of given order and size), hypergraph jumps, quantitative Ramsey-type questions, and graph embedding problems. Since both graph limits and flag algebras deal with an approximation to the studied problem, one important aspect is to develop methods for obtaining exact results from asymptotic calculations (for example, via the stability approach).Extremal and probabilistic combinatorics impacts not only mathematics but many other areas such as operations research, information theory, codes, complexity and algorithms. Random graphs and processes have been providing successful models for various complex systems (such as the Internet or social networks). Such models can be used, for example, for estimating parameters that are impossible or impractical to be determined directly and for predicting their future behavior. Graph limits (and graph regularity) provide a method of approximating large-scale objects by those of bounded complexity; this approach has already been explored in the context of parameter and property testing in computer science. The PI will research new ways of applying randomness, regularity, and graph limits to combinatorial problems. Theoretical developments in these areas may have significant practical implications.

PI将继续他的研究组合学和图论集中在概率和极值问题。随机结构和过程，虽然是一个重要的研究对象，他们自己，也是非常有效的解决问题的离散数学，包括那些陈述是纯粹确定性的。他们成功应用的一个重要领域是极值组合学，广义上说，人们必须最大化或最小化给定的某些组合限制的某个参数。一个极值问题的例子是图兰函数，一个没有固定禁止子图的超图的最大尺寸。这是一个根本和关键的问题，它询问地方限制如何影响全球结构。尽管经过几十年的积极尝试，大多数图兰类型的问题仍然是开放的，例如保罗·图兰在1941年提出的著名的四面体猜想。在攻击这些困难的问题数学家制定了一些有用的和一般的技术，如，例如，正则引理。最近的概念（超）图限制和标志代数似乎是非常强大的工具，研究有限的结构，并提供新的方法来操作大型离散对象。PI将研究一些组合问题，特别是寻求应用这些技术的新方法。一些有前途的方向包括Turan函数，稳定性，子图密度之间的不等式（例如，最小化给定阶和大小的图中的F-子图的数量），超图跳跃，定量Ramsey型问题和图嵌入问题。由于图极限和标志代数都是处理所研究问题的近似，因此一个重要的方面是发展从渐近计算中获得精确结果的方法（例如，通过稳定性方法）。极值和概率组合学不仅影响数学，还影响许多其他领域，如运筹学，信息论，代码，复杂性和算法。随机图和过程已经为各种复杂系统（如互联网或社交网络）提供了成功的模型。这样的模型可以用于，例如，估计不可能或不切实际的直接确定的参数，并预测其未来的行为。图极限（和图正则性）提供了一种通过有限复杂性来近似大规模对象的方法;这种方法已经在计算机科学中的参数和属性测试中进行了探索。PI将研究将随机性、规律性和图形极限应用于组合问题的新方法。这些领域的理论发展可能具有重大的实际意义。