Extremal and Probabilistic Combinatorics with Applications

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

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

This research project investigates basic combinatorial questions about discrete structures and explores applications of discrete mathematics in computer science, biology, and engineering. The investigators continue their work on extremal graph, set, and hypergraph theory and forbidden configurations. They investigate connections between graph theory and geometry, on the one hand studying Ricci curvature on graphs, on the other hand studying crossing numbers of graphs and related incidence problems. The project will study graph and tree indices originating in chemical graph theory and will apply combinatorial and probabilistic techniques to phylogenetics and to the theory of complex networks. Results of the project will contribute to the better understanding of key phenomena in network science, of discretization of geometric space, of phylogenetics, and of other fields. The investigators will continue the training of Ph.D. students through involvement in the research, introducing them to interdisciplinary and international research collaboration.The project will contribute to the understanding of "optimal" extreme structures and "typical" random structures in discrete mathematics. This area is referred to broadly as extremal combinatorics, and some of the main open questions in the area will be studied, including various instances of the Turan problem for graphs, hypergraphs and posets, problems in combinatorial geometry, in the vein of the Erdos unit distance problem and crossing and incidence problems, and combinatorial questions on trees such as the Maximum Agreement Subtree problem as well as topics related to chemistry. This project will build upon sophisticated methods that have been developed to attack these problems, such as the approach via crossing numbers and incidences, the Guth-Katz low degree polynomial method, and the generalization of the notion of Ricci Curvature from differential geometry to graphs, which allows, to some extent, functional analytic tools to be brought to bear.

该研究项目研究了有关离散结构的基本组合问题，并探讨了计算机科学，生物学和工程学中离散数学的应用。研究人员继续在极端图，集合和超图理论以及禁止配置上进行工作。他们研究了图理论与几何形状之间的联系，一方面研究了图形上的RICCI曲率，另一方面研究了图形的交叉数和相关发病率问题。该项目将研究源自化学图理论的图形和树指数，并将将组合和概率技术应用于系统发育和复杂网络理论。该项目的结果将有助于更好地理解网络科学中的关键现象，系统发育学和其他领域的几何空间的离散化。调查人员将继续培训博士学位。学生通过参与研究，将他们介绍给跨学科和国际研究合作。该项目将有助于理解离散数学中的“最佳”极端结构和“典型”随机结构。该领域被广泛地称为极端组合主义，该领域的一些主要问题将被研究，包括图形，超图和posets的图兰问题的各种实例，组合几何学的问题，在ERDOS单位距离问题的静脉中，交叉问题和交叉问题，交叉问题，以及在树木上的结合问题，以及最大程度地相关的室外问题。该项目将建立在已经开发出来攻击这些问题的复杂方法的基础上，例如通过交叉数和事件，Guth-Katz低度多项式方法的方法以及RICCI曲率从微分几何形状到图的概念的概括，这在某种程度上允许带来携带的函数分析工具。