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.

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