CAREER: Extremal Combinatorics

职业：极值组合学

• 批准号: 1455125
• 负责人: Po-Shen Loh
• 金额: $ 40万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-02-15 至 2021-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1455125&HistoricalAwards=false
• 关键词: CAREER; Extremal; Combinatorics

Combinatorics, which concerns the study of discrete structures such as sets and networks, is as ancient as humanity's ability to count. Although in the beginning combinatorial problems were solved by pure ingenuity, today that alone is not enough. A rich variety of powerful methods have been developed, often drawing inspiration from other fields such as probability, analysis, algorithms, and even algebra and topology. This proposal aims to further develop the toolbox of available approaches, through investigating central problems in extremal combinatorics. Simultaneously, it integrates these research problems and themes into educational and outreach activities that extend from the graduate to the K-12 level, and from coast to coast. The PI is the national coach of the USA International Mathematical Olympiad team. He actively leverages this leadership position to address the public about mathematics, engaging underrepresented groups as well as some of the world's brightest students, and mentoring students in their transition from K-12 mathematics into research.The theme of this research is to use a problem-driven philosophy to inspire innovations in the development of new techniques. This project focuses on topics of extremal nature, which investigate the relationships between useful parameters of discrete systems, and characterizes their extreme values over various families of those systems. Such problems often have applications in computer science and other areas of mathematics, but are also elegant and interesting in their own right. The proposed work on Ramsey theory includes specific problems which may lead to the development of new probabilistic approaches, and new connections with the theory around Szemeredi's Regularity Lemma. The proposed work on Turan theory highlights a particularly natural maximum-degree version of the fundamental Kruskal-Katona theorem, which is surprisingly still open. In addition, it proposes questions which inspire work on finding Regularity-free approaches, and on analytical and computational methods. The PI has prior experience in all of these areas, and has built a local research group, spanning from post-docs to extremely talented undergraduates.

组合学是研究集合和网络等离散结构的学科，它和人类的计算能力一样古老。虽然组合问题在一开始是通过纯粹的独创性来解决的，但今天仅有这一点是不够的。已经开发了各种功能强大的方法，通常从其他领域如概率、分析、算法，甚至代数和拓扑学中获得灵感。这项提议旨在通过研究极值组合数学中的中心问题，进一步发展现有方法的工具箱。同时，它将这些研究问题和主题纳入从毕业生到K-12和从东海岸到西海岸的教育和外联活动。少年派是美国国际奥数代表队的国家队教练。他积极利用这一领导地位向公众发表关于数学的演讲，吸引代表不足的群体以及一些世界上最聪明的学生，并指导学生从K-12数学过渡到研究。这项研究的主题是使用问题驱动的哲学来激励新技术开发的创新。这个项目集中在极端性质的主题上，调查离散系统的有用参数之间的关系，并表征这些系统的各种族上的极值。这类问题通常在计算机科学和其他数学领域有应用，但它们本身也很优雅和有趣。关于Ramsey理论的拟议工作包括可能导致新的概率方法的发展的具体问题，以及与围绕Szmeredi正则性引理的理论的新联系。图兰理论的拟议工作突出了Kruskal-Katona基本定理的一个特别自然的最大次数版本，该定理令人惊讶地仍然开放。此外，它还提出了一些问题，启发了寻找无规律性方法以及分析和计算方法的工作。PI在所有这些领域都有经验，并在当地建立了一个研究小组，从博士后到才华横溢的本科生。