Extremal and Probabilistic questions on hypergraphs

超图的极值和概率问题

• 批准号: 0969092
• 负责人: Dhruv Mubayi
• 金额: $ 20万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-05-15 至 2014-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0969092&HistoricalAwards=false
• 关键词: Extremal; Probabilistic; questions; hypergraphs

The PI will develop the theory of hypergraphs, or families of sets, focusing on extremal and probabilistic questions. A goal is to extend classical theorems in the area and to discover new phenomena using modern approaches, which include the semirandom or nibble method and hypergraph regularity. The PI and his collaborators have recently used these tools to improve and extend several results in combinatorics that have been around for decades. The plan is to continue these projects. Several questions that were unapproachable for many years have suddenly come within reach due to some ground-breaking recent developments and the PI plans to continue exploiting these new techniques to shed light on old problems. The specific questions to be attacked concern the chromatic number of locally sparse hypergraphs, the structure of typical hypergraphs that contains no copy of some fixed configuration, and the enumeration of copies of one hypergraph in another.The extremal theory of hypergraphs impacts several areas of Mathematics and also has consequences in other fields like information theory, coding theory, and theoretical computer science. The study of random structures and randomized algorithms has gained importance in recent years due to the proliferation of large networks like the internet and various other social networks. Developing new techniques to study these complex systems will be a major task for future researchers. Part of this project seeks to develop randomized algorithms that break a large complicated system into smaller, well understood pieces.

PI将发展超图理论，或集族，专注于极值和概率问题。目标是扩展该领域的经典定理，并使用现代方法发现新现象，其中包括半随机或蚕食方法和超图正则性。PI和他的合作者最近使用这些工具来改进和扩展已经存在了几十年的组合学的几个结果。计划是继续这些项目。由于最近一些突破性的发展，多年来无法解决的一些问题突然变得触手可及，PI计划继续利用这些新技术来解决老问题。要解决的具体问题涉及局部稀疏超图的色数、典型超图的结构（不包含某些固定构型的副本）以及一个超图在另一个超图中的副本枚举。超图的极值理论影响了数学的几个领域，也影响了其他领域，如信息论、编码理论和理论计算机科学。近年来，由于互联网等大型网络和各种其他社交网络的激增，随机结构和随机算法的研究变得越来越重要。开发研究这些复杂系统的新技术将是未来研究人员的主要任务。这个项目的一部分旨在开发随机算法，将一个庞大的复杂系统分解成更小、更容易理解的部分。