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将继续他在组合学和图理论方面的研究，集中在概率和极端问题上。随机结构和过程是自己研究的重要对象，在解决离散数学问题的问题中也非常有效，包括那些纯粹是确定性的陈述的问题。他们成功应用的一个重要领域是极端组合主义者，从广义上讲，在某些组合限制下，必须最大程度地提高或最小化某个参数。一个极端问题的一个例子是Turan函数，即无固定禁止子图的超图的最大尺寸。这是一个基本的关键问题，询问当地限制如何影响全球结构。尽管进行了数十年的积极尝试，但大多数Turan型问题仍在开放，例如Paul Turan在1941年做出的著名的四面体猜想。在攻击这些困难问题时，数学家开发了许多有用和一般的技术，例如，例如规律性的引理。 （超级）图形限制和国旗代数的最新概念似乎是研究有限结构并提供具有大型离散对象操作的新方法的非常有力的工具。 PI将处理许多组合问题，特别是寻求应用这些技术的新方法。一些有希望的方向包括Turan函数，稳定性，子图密度之间的不平等（例如，在给定的顺序和大小的图中最小化F-Subgraphs的数量），超图跳跃，定量的Ramsey-type问题，以及图形嵌入问题。由于图限制和标志代数都涉及与研究问题的近似值，因此一个重要方面是开发从渐近计算中获得确切结果的方法（例如，通过稳定性方法）。当时和概率的组合术会影响数学不仅要影响数学，而且还会影响许多其他领域，例如操作研究，信息理论，编码，编码，复杂性，复杂性和Algorith和Algorith和Algorith和Algorith。随机图和过程已经为各种复杂系统（例如Internet或社交网络）提供了成功的模型。例如，可以使用此类模型来估计直接确定不可能或不切实际的参数并预测其未来行为。图形限制（和图形规律性）提供了一种通过有界复杂性的方法近似大规模对象的方法；在计算机科学中的参数和属性测试的背景下，已经探索了这种方法。 PI将研究将随机性，规律性和图形限制应用于组合问题的新方法。这些领域的理论发展可能具有重大的实际意义。