Extremal Combinatorics

极值组合学

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

The PI and his coauthors will work on extremal problems for setsystems or hypergraphs using combinatorial, algebraic,probabilistic, and topological methods. The basic problem ofextremal hypergraph theory is the so called Turan problem:determine the maximum number of subsets a finite set can havewithout containing some fixed forbidden configuration. Thisquestion, in its full generality, is very difficult, and certainspecial cases are famous problems that have been open for over 50years. Nevertheless, substantial work on closely related issueshas occurred recently, and the limits of this recent progress willbe explored. Although several different aspects are considered(Ramsey-Turan problems, jumps in hypergraphs, degenerate problemsfor simplices), the common theme is to obtain a hypergraphanalogue of the Erdos-Simonovits-Stone theorem, the cornerstone ofextremal graph theory.The general topic of finite set systems has connections to diverseareas of mathematics (combinatorial geometry, design theory,partially ordered sets, additive number theory), and also toacademic disciplines with concrete applications in everyday life(coding theory, information theory, optimization and schedulingproblems, computer science). Modern communication would beimpossible without the existence of codes, or objects designed torelay information faithfully even in the face of distortion.Extremal problems for set systems play a role in constructingcodes for various situations.

PI和他的合著者将使用组合，代数，概率和拓扑方法研究集合系统或超图的极值问题。极超图理论的基本问题是所谓的Turan问题：确定一个有限集合在不包含某些固定的禁止构形的情况下所能拥有的子集的最大数目。这个问题，在其充分的一般性，是非常困难的，和某些特殊情况是著名的问题，已经开放了50多年。尽管如此，最近在密切相关的问题上进行了大量的工作，我们将探讨最近进展的局限性。虽然考虑了几个不同的方面，（Ramsey-Turan问题，超图中的跳跃，单形的退化问题），共同的主题是获得Erdos-Simonovits-Stone定理的超图类似物，极值图论的基石。有限集系统的一般主题与数学的各个领域都有联系（组合几何，设计理论，偏序集，加法数论），并在日常生活中有具体应用的学科（编码理论、信息论、优化和排序问题、计算机科学）。如果没有代码，或者没有被设计成即使面对失真也能忠实地传递信息的物体，现代通信就不可能实现。集合系统的极值问题在构造各种情况下的代码中发挥着重要作用。