Extremal and probabilistic combinatorics

极值和概率组合学

• 批准号: 0701111
• 负责人: Laszlo Szekely
• 金额: $ 10.41万
• 依托单位: University South Carolina Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-08-01 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0701111&HistoricalAwards=false
• 关键词: Extremal; probabilistic; combinatorics

Drs. Lu and Szekely build on their previous work in combinatorics and graph theory and continue their research on problems related to graph visualization and graph drawing; random graph models; tree indices relevant for chemistry; models for biomolecular sequence evolution; and phylogeny reconstruction for species evolution. They also continue their long-running projects on fundamental questions in extremal set theory, extremal graph theory, and discrete geometry. The particular problems on which they work include* the further development of the theory of crossing numbers of graphs and of better graph drawing algorithms;* improving current bounds on Turan type extremal problem on hypergraphs, one of the toughest problems in extremal combinatorics;* improving our knowledge on Property B, where notoriously hard problems provide testing ground for new techniques;* extending current probabilistic tools in combinatorics to be applicable in a new or more general scenario;* work towards the unification of random graph models;* searching for new insights on antichains and on intersecting families of subsets;* reach a much better understanding of the Randic index, a concept of extremal graph theory that has been introduced and widely used in chemistry;* continuing the study of models of biomolecular sequence evolution and phylogenetic trees, of phylogenetic tree reconstruction algorithms, in particular the maximum likelihood method, and investigating the phylogeny problem in the setting of inverting random functions.There is increasing demand to understand ``optimal''extreme structures and ``typical'' random structures in discrete mathematics as this understanding often leads to new algorithms This project will investigate basic combinatorial questions about structures and will look for various applications of discrete mathematics in computer science, biology, and engineering.In addition, the proposers plan to continue their interdisciplinary collaborations with colleagues from engineering, biology, statistics, and computer science, and expect to solve some of their new problems.

Lu和Szekely博士在组合学和图论方面的工作基础上，继续研究与图形可视化和图形绘制相关的问题;随机图模型;与化学相关的树指数;生物分子序列进化模型;物种进化的遗传重建。他们还继续在极值集理论，极值图论和离散几何的基本问题上长期运行的项目。他们工作的具体问题包括：* 进一步发展图的交叉数理论和更好的绘图算法;* 改进超图上Turan型极值问题的当前界限，这是极值组合学中最棘手的问题之一;* 提高我们对性质B的知识，其中众所周知的困难问题为新技术提供了测试基础;* 扩展现时组合数学中的概率工具，使其可应用于新的或更一般的情况;* 致力统一随机图模型;* 寻求对反链和相交子集族的新见解;* 更好地理解Randic指数，这是一个在化学中引入并广泛使用的极值图论概念;* 继续研究生物分子序列进化和系统发生树的模型，系统发生树重建算法，特别是最大似然法，研究了逆随机函数的极值问题，人们越来越需要了解“最优”极值结构和"离散数学中的典型“随机结构，因为这种理解通常会导致新的算法。该项目将研究有关结构的基本组合问题，并将寻找各种应用此外，提议者计划继续与来自工程，生物，统计和计算机科学的同事进行跨学科合作，并期望解决他们的一些新问题。