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水平以及从海岸到海岸的教育和推广活动中。 PI是美国国际数学奥林匹克代表队的国家教练。 他积极利用这一领导地位，向公众介绍数学，吸引代表性不足的群体以及一些世界上最聪明的学生，并指导学生从K-12数学过渡到研究。这项研究的主题是使用问题驱动的哲学来激励新技术开发的创新。 该项目的重点是极值性质的主题，研究离散系统的有用参数之间的关系，并在这些系统的各种家庭中表征其极值。 这些问题通常在计算机科学和其他数学领域有应用，但它们本身也很优雅和有趣。 拟议的工作拉姆齐理论包括具体问题，可能导致发展新的概率方法，并与周围的Szemeredi的正则引理理论的新连接。 图兰理论的工作突出了一个特别自然的最大程度版本的基本克鲁斯卡尔-卡托纳定理，这是令人惊讶的仍然开放。 此外，它还提出了一些问题，这些问题激发了寻找无正则方法以及分析和计算方法的工作。 PI在所有这些领域都有经验，并建立了一个当地的研究小组，从博士后到非常有才华的本科生。