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将研究将随机性、正则性和图形极限应用于组合问题的新方法。这些领域的理论发展可能具有重大的实践意义。