CAREER: Algebraic extremal combinatorics

职业：代数极值组合学

• 批准号: 1555149
• 负责人: Boris Bukh
• 金额: $ 45万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1555149&HistoricalAwards=false
• 关键词: CAREER; Algebraic; extremal; combinatorics

This project lies at the interface of two fundamental mathematical fields: combinatorics and algebra. The research pursues a powerful and novel approach to establish connections between the two areas, and the interplay between mathematical structures in common to both areas is investigated in depth. As a general theme, many problems in mathematics and physics can be recast as finding the largest size of a mathematical structure subject to prescribed constraints on the substructures. It is often the case that the largest structures organize themselves in a highly algebraic way, which opens the door to algebraic methods. These so-called extremal structures have a remarkable number of applications to other areas of mathematics and science, including to theoretical computer science, statistical physics and coding theory. A number of recent breakthroughs in the area reveal an exciting future for the proposed work. The PI will work closely with both undergraduate and graduate students in the research project. In addition, the PI is preparing comprehensive educational materials on the new techniques, whose target audience will be both students and experts in the area.There are several problems currently known to be at the interface of extremal combinatorics and algebra. Some examples are explicit constructions of Ramsey graphs, constructions of large graphs not containing a specific subgraphs, bounds on spherical codes, zero-error capacities of communication channels, set families with restricted intersections. The PI is an expert in creating novel algebraic and geometric methods for application to such combinatorial problems, and these methods are central to many of the most importance advances and new results in the area.

该项目位于两个基本数学领域的交汇处：组合学和代数。该研究寻求一种强大而新颖的方法来建立这两个领域之间的联系，并深入研究这两个领域共同的数学结构之间的相互作用。作为一个一般主题，数学和物理中的许多问题可以重新定义为在子结构的规定约束下找到数学结构的最大尺寸。通常情况下，最大的结构以高度代数的方式组织起来，这为代数方法打开了大门。这些所谓的极值结构在数学和科学的其他领域有大量的应用，包括理论计算机科学、统计物理学和编码理论。该领域最近的一些突破揭示了拟议工作的令人兴奋的未来。 PI 将在该研究项目中与本科生和研究生密切合作。此外，PI 正在准备有关新技术的综合教育材料，其目标受众将是该领域的学生和专家。 目前已知极值组合学和代数的接口存在几个问题。一些例子是拉姆齐图的显式构造、不包含特定子图的大图的构造、球形代码的界限、通信通道的零错误能力、具有受限交集的集合族。 PI 是创建应用于此类组合问题的新颖代数和几何方法的专家，这些方法是该领域许多最重要的进展和新成果的核心。