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曲率的图形，另一方面研究交叉数的图形和相关的发病率问题。该项目将研究起源于化学图论的图和树指数，并将组合和概率技术应用于遗传学和复杂网络理论。该项目的结果将有助于更好地理解网络科学中的关键现象，几何空间的离散化，遗传学和其他领域。研究者将继续接受博士培训。通过参与研究，向学生介绍跨学科和国际研究合作。该项目将有助于理解离散数学中的“最佳”极端结构和“典型”随机结构。这一领域被广泛地称为极值组合学，将研究该领域的一些主要开放问题，包括图，超图和偏序集的图兰问题的各种实例，组合几何中的问题，鄂尔多斯单位距离问题以及交叉和关联问题，以及关于树的组合问题，如最大一致性子树问题以及与化学有关的主题。该项目将建立在已经开发的复杂方法来解决这些问题，如通过交叉数和发生率的方法，Guth-Katz低次多项式方法，以及从微分几何到图形的Ricci曲率概念的推广，这在一定程度上允许功能分析工具。