Extremal and Probabilistic Combinatorics with Applications

在其他学科各种问题的推动下，以及离散数学的内部发展，人们对了解离散数学中的“最优”极端结构和“典型”随机结构的需求稳步增加。本项目将研究有关结构的基本组合问题，并将寻找离散数学在计算机科学、生物和工程中的各种应用。主要研究人员在极值图、超图和偏序集理论、图形可视化和图形绘制、随机图模型和概率组合学等领域的组合学和图论方面的先前工作的基础上，研究极值集论、极值图论及其密切相关领域的基本问题。这些基本问题包括已有70年历史的图兰问题，这是极端组合学中最棘手的问题之一；排除子集问题，其结果刚刚固化为理论；以及建立连接上述两个领域的图兰超图理论，为这两个领域提供了新的见解。尽管谱方法在图论中的有效性及其对超图的不同类似物，但至今还没有一个连贯的谱超图理论。卢和鹏试图统一拉普拉斯超图的不同版本。该项目的一个关键方向是进一步建立基于拉普拉斯的一致超图的谱分析。40年来，洛瓦兹局部引理一直是大海捞针的工具。主要研究人员介绍了一种使用Lovasz局部引理的不平衡形式对组合对象进行渐近计数的技术。该项目将通过寻找应用不平衡Lovasz局部引理的新的问题类来扩展该方法应用的渐近计数问题的范围。图的交叉数和广义Sperner族的结构的研究也是该项目的目标之一。该项目的应用范围预计将对其他科学产生影响。特别是，研究序列进化和系统发育重建的模型与生物信息学的数学基础相关，研究树指数的极值和结构性质与数理化学相关，研究不同绘图模型中的图形的交叉数与计算机科学相关。该项目的一些概率和光谱结果将与网络科学相关。主要研究人员继续与工程学、生物学、统计学和计算机科学的同事进行跨学科合作，并继续培训成功的研究生。

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.