Extremal graphs, hereditary and random structures

极值图、遗传和随机结构

• 批准号: 0600303
• 负责人: Zoltan Furedi
• 金额: $ 35.2万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-05-15 至 2009-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0600303&HistoricalAwards=false
• 关键词: Extremal; graphs; hereditary; random; structures

The PI and the co-PI study how l o c a l properties affect the g l o b a l parameters of various combinatorial structures.This is a very general framework of the so-called Turan number problems. The PI and the co-PI emphasize five different aspects:Turan numbers of triple systems, cardinalities of hereditary families,geometrical/algebraic representations of graphs where Turan numbers naturally emerge, they study more general coding theory problems, and investigate random combinatorial structures, especially the phase transition of various models of bootstrappercolation.Combinatorics, in other words Discrete Mathematics, studies finite, but large structures, many of them arising from computer science.Combinatorics is the theoretical basis of coding theory, computergraphics,computer science, cryptography and communication theory.Combinatorists are looking for economical, fast and reliable ways tostore and search data structures.A wide variety of combinatorial problems deal with l o c a l properties, or use local probabilities in order to determine (or estimate) global parameters to describe the bigger picture.This effect of local properties on global parameters is the subject of this proposal.

PI和Co-PI研究如何 l o c a l属性会影响 g l o B a l参数的各种组合结构。这是一个非常普遍的框架，所谓的图兰数问题。 PI和co-PI强调五个不同的方面：三重系统的图兰数，遗传家族的基数，图兰数自然出现的图形的几何/代数表示，他们研究更一般的编码理论问题，并研究随机组合结构，特别是各种Bootstrap渗流模型的相变。组合数学，换句话说，离散数学，研究有限但大的结构，其中许多来自计算机科学。组合数学是编码理论，计算机图形学，计算机科学，密码学和通信理论的理论基础。组合学家正在寻找经济，快速可靠的方法来存储和搜索数据结构。各种各样的组合问题处理局部属性，或使用局部概率来确定（或估计）全局参数以描述更大的图像。局部属性对全局参数的影响是本提案的主题。