Extremal and Probabilistic Combinatorics with Applications

极值和概率组合学及其应用

• 批准号: 1300547
• 负责人: Laszlo Szekely
• 金额: $ 18.41万
• 依托单位: University of South Carolina at Columbia
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1300547&HistoricalAwards=false
• 关键词: Extremal; Probabilistic; Combinatorics; Applications

Motivated by various problems from other disciplines and also from the internal development of discrete mathematics, the demand steadily increases to understand "optimal" extreme structures and "typical" random structures in discrete mathematics.This project will investigate basic combinatorial questions about structures and will look for various applications of discrete mathematics in computer science, biology, and engineering. The principal investigators build on their previous work in combinatorics and graph theory in the areas of extremal graph, hypergraph and poset theory, graph visualization and graph drawing, random graph models and probabilistic combinatorics to attack fundamental questions in extremal set theory, extremal graph theory, and in areas closely related to them. These fundamental questions include the 70 years old Turan problem, one of the toughest problems in extremal combinatorics; the excluded subposet problems, results on which are just solidifying into a theory; and building a Turan hypergraph theory bridging the two areas above, offering new insight for both. Notwithstanding the efficacy of spectral methods in graphs theory and different analogues of it for hypergraphs, there is not yet a coherent spectral hypergraph theory. Lu and Peng made an attempt to unify different versions of Laplacians for hypergraphs. A key direction of the project is building further the spectral analysis of uniform hypergraphs based on their Laplacian. For 40 years, the Lovasz Local Lemma has been the tool to find the proverbial needle in the haystack. The principal investigators introduced a technique to use the lopsided version of the Lovasz Local Lemma for asymptotic enumeration of combinatorial objects. The project will extend the range of asymptotic enumeration problems where this method applies, by finding new classes of problems where the lopsided Lovasz Local Lemma applies. The study of crossing numbers of graphs, and of the structure of generalized Sperner families is also among the goals of the project.The applied prong of the project is expected to have an impact on other sciences. In particular, investigating models for sequence evolution and phylogeny reconstruction is relevant for the mathematical foundation of bioinformatics, investigating extremal and structural properties of tree indices has relevance for mathematical chemistry, working on crossing numbers of graphs in different models of drawing is relevant for computer science. Some probabilistic and spectral results of this project will be relevant for network science. The principal investigators continue their interdisciplinary collaborations with colleagues from engineering, biology, statistics, and computer science, and continue the training of successful graduate students.

受到其他学科的各种问题以及离散数学的内部发展的推动，需求稳步增加，以了解离散数学中的“最佳”极端结构和“典型”随机结构。本项目将研究有关结构的基本组合问题，并将寻求分散数学在计算机科学，生物学和工具中的各种应用。主要研究人员以其先前在组合图和图理论为基础的工作中，在极端图，超图和POSET理论，图形可视化和图形图，随机图模型和概率组合学方面，以攻击极端集理论，极端图理论以及与之紧密相关的领域中的基本问题。这些基本问题包括70年历史的Turan问题，这是极端组合学中最棘手的问题之一。排除的子框问题，即将巩固为理论的结果。并建立一个Turan Hypergraph理论，桥接了上面的两个领域，为两者提供了新的见解。尽管光谱方法在图理论及其对超图的不同类似物中具有疗效，但尚无连贯的光谱超图理论。 Lu和Peng试图统一不同版本的Laplacians的超图。该项目的一个关键方向是进一步建立基于其拉普拉斯式的统一超图的光谱分析。 40年来，Lovasz Local Lemma一直是在干草堆中找到众所周知的针头的工具。主要研究人员介绍了一种技术，将Lovasz本地引理的偏斜版本用于组合物体的渐近枚举。该项目将通过在适用于Lovasz Loca的Lovasz本地引理中使用新的问题来扩展该方法适用的渐近枚举问题的范围。该项目的目标也是对图形的交叉数量以及广义孢子家族的结构的研究。预计该项目的插脚有望对其他科学产生影响。特别是，研究序列进化和系统发育重建的模型与生物信息学的数学基础有关，研究树指数的极端和结构特性与数学化学相关，在不同模型的图形中进行交叉数量与计算机科学相关。该项目的一些概率和光谱结果将与网络科学有关。首席研究人员继续与工程，生物学，统计和计算机科学的同事进行跨学科的合作，并继续对成功的研究生进行培训。