Extremal and Probabilistic Questions on Hypergraphs

超图的极值和概率问题

• 批准号: 1300138
• 负责人: Dhruv Mubayi
• 金额: $ 35万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1300138&HistoricalAwards=false
• 关键词: Extremal; Probabilistic; Questions; Hypergraphs

The PI will develop the theory of hypergraphs, or families of sets, focusing on extremal and probabilistic questions. Three directions of study are proposed: quasirandomness, extremal Turan-type problems, and ramsey theory. In each of these areas, the PI will extend classical results in graph theory that have been around for decades to hypergraphs. For example, extending the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs to hypergraphs has received considerable attention since the early 1990's and the PI has made further progress recently; he plans to explore the sparse case in this project. The PI (together with coauthors) has recently extended the Erdos-Gallai theorem about paths and cycles in graphs to hypergraphs; further extensions of the new method that was developed will be explored for other forbidden structures. Finally, there have been relatively few results in hypergraph Ramsey theory since some basic bounds of Erdos and others from the 1950's and the PI will use modern approaches to tackle some outstanding problems in these areas. The extremal and probabilistic theory of hypergraphs impacts several areas of Mathematics (number theory, combinatorics, logic) as well as other fields like information theory, coding theory, and theoretical computer science. The study of random structures and randomized algorithms has gained particular importance in recent years due to the many large real world networks that have emerged and are being studied. Developing new techniques to study these complex systems will be a major task for future researchers. The theory of quasirandom hypergraphs may form a theoretical foundation for studying large scale behavior of more complicated networks where groups of more than two nodes are connected to each other. One theme common to most problems that will be investigated in this project is to understand the quantitative relationship between the local and global behavior of a large system.

PI将发展超图或集合族的理论，专注于极值和概率问题。提出了三个研究方向：准随机性，极值图兰型问题，拉姆齐理论。 在这些领域中的每一个领域，PI将把图论中已经存在了几十年的经典结果扩展到超图。例如，从20世纪90年代初起，将Mesquason和Chung-Graham-Wilson关于拟随机图的基础结果扩展到超图已经受到了相当大的关注，PI最近取得了进一步的进展;他计划在这个项目中探索稀疏情况。PI（与合著者一起）最近将关于图中的路径和循环的Erdos-Gallai定理扩展到超图;将进一步扩展开发的新方法用于其他禁止结构。 最后，超图Ramsey理论的结果相对较少，因为Erdos和其他人的一些基本界限来自20世纪50年代，PI将使用现代方法来解决这些领域中的一些突出问题。超图的极值和概率理论影响了数学的几个领域（数论，组合学，逻辑）以及其他领域，如信息论，编码理论和理论计算机科学。近年来，由于出现了许多大型真实的世界网络并正在进行研究，因此对随机结构和随机算法的研究变得尤为重要。开发新的技术来研究这些复杂系统将是未来研究人员的主要任务。拟随机超图的理论可以为研究两个以上节点相连的复杂网络的大规模行为提供理论基础。 在这个项目中，大多数问题的一个共同主题是理解一个大系统的局部和全局行为之间的定量关系。