Problems in Extremal Set Theory

极值集合论中的问题

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

The PI and his coauthors will work on extremal problems for set systems using combinatorial, algebraic, and probabilistic methods. The basic problem of extremal set theory is to determine the maximum number of subsets a finite set can have without containing some fixed forbidden configuration. Many special cases are famous problems that have been open for over 50 years. Nevertheless, substantial work on closely related issues has occurred recently and the PI is part of these projects. The PI will focus on three major questions:the Turan conjecture for the complete 3-graph on four points, Chvatals conjecture on simplices, and sharpening the Frankl-Rodl omitted intersection theorem.The general topic of finite set systems has connections to diverse areas of mathematics (combinatorial geometry, design theory, partially ordered sets, additive number theory), and also to academic disciplines with concrete applications in everyday life (coding theory, information theory, optimization and scheduling problems, computer science). As an example, modern communication would be impossible without the existence of codes, or objects designed to relay information faithfully even in the face of distortion.Extremal problems for set systems play an important role in constructing codes for various situations.

PI和他的合作者将使用组合、代数和概率方法研究集合系统的极值问题。极值集理论的基本问题是确定一个有限集合在不包含某些固定禁形的情况下所能具有的子集的最大数目。许多特殊案例都是50多年来一直悬而未决的著名问题。然而，最近在密切相关的问题上进行了大量工作，PI是这些项目的一部分。PI将集中在三个主要问题上：图兰猜想在四个点上的完全3-图，Chvatals猜想在简单点上，和尖锐的Frankl-Rodl省略交定理。有限集系统的一般主题与数学的各个领域（组合几何、设计理论、部分有序集、可加数论）以及在日常生活中有具体应用的学科（编码理论、信息论、优化和调度问题、计算机科学）有联系。例如，如果没有代码的存在，现代通信是不可能的，或者即使面对失真也能忠实地传递信息的对象。集合系统的极值问题在构造各种情形的码时起着重要的作用。