Extremal and Probabilistic Combinatorics with Applications

由于其他学科的各种问题以及离散数学的内部发展，对离散数学中“最优”极端结构和“典型”随机结构的理解需求不断增加。这个项目将研究关于结构的基本组合问题，并寻找离散数学在计算机科学、生物学和工程学中的各种应用。主要研究人员建立在他们之前在极值图、超图和偏置理论、图可视化和图绘制、随机图模型和概率组合领域的组合学和图论方面的工作基础上，以解决极值集理论、极值图论以及与之密切相关的领域的基本问题。这些基本问题包括70年前的图兰问题，极值组合学中最难的问题之一；被排除的传讯问题，其结果刚刚形成一个理论；并建立图兰超图理论，将上述两个领域连接起来，为两者提供新的见解。尽管谱方法在图论及其对超图的不同类似物中很有效，但目前还没有一个连贯的谱超图理论。Lu和Peng试图统一不同版本的超图拉普拉斯算子。该项目的一个关键方向是进一步建立基于拉普拉斯的均匀超图的谱分析。40年来，Lovasz Local引理一直是大海捞针的工具。主要研究人员介绍了一种使用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.