权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Extremal Combinatorics: Problems and Algorithmic Aspects

极值组合学：问题和算法方面

基本信息

批准号：
2154082
负责人：
Noga Alon
金额：
$ 44万
依托单位：
Princeton University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-07-01 至 2026-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154082&HistoricalAwards=false
关键词：
Extremal Combinatorics Problems Algorithmic Aspects

项目摘要

Extremal Combinatorics is one of the most active areas in modern Combinatorics and has developed spectacularly over the last decades. It deals with the problem of determining or estimating the maximum or minimum possible value of an invariant of a combinatorial structure that satisfies certain requirements as well as with the investigation of inequalities between combinatorial invariants, and questions dealing with relations among them. The Principal Investigator intends to investigate several questions in the area, including ones that are motivated by algorithmic applications. The specific topics to be studied include old and new problems in Graph Theory and Combinatorics, as well as the algorithmic aspects of questions about fair representations of necklaces and graphs. The non-constructive solutions of some of these questions combine algebraic and topological tools, leaving the fascinating problem of finding algorithmic solutions open.The proposal addresses several fundamental old and new combinatorial problems. Besides their intrinsic interest, many of these problems are motivated by related questions in other areas. In particular, the study of splitting random necklaces has a surprising connection to questions about random walks in Euclidean spaces and about matchings in nearly regular uniform hypergraphs. The algorithmic aspects of the necklace theorem are intriguing in view of the recent results about the hardness of the problem. The related study of the algorithmic aspects of some of the other fair partitioning problems described in the project is also challenging. The investigation of Graph Codes, which is interesting in its own right, is also motivated by questions about Ramsey type results in Additive Combinatorics. The methods the Principal Investigator intends to apply combine combinatorial, probabilistic, algebraic and geometric tools with ideas from Coding Theory. It is expected that progress on the problems mentioned here will be interesting and significant, will hopefully lead to the development of novel fruitful techniques, and will yield interesting applications and insights in related areas.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

极值组合数学是现代组合数学中最活跃的领域之一，在过去的几十年里得到了迅猛的发展。它涉及的问题，确定或估计的最大或最小可能值的不变的组合结构，满足一定的要求，以及与调查之间的不平等组合不变，和问题处理它们之间的关系。首席研究员打算调查该领域的几个问题，包括由算法应用程序激发的问题。要研究的具体课题包括图论和组合学中的新老问题，以及关于项链和图的公平表示问题的算法方面。其中一些问题的非建设性解决方案结合了联合收割机代数和拓扑工具，留下了迷人的问题，寻找算法的解决方案开放。该提案解决了几个基本的新旧组合问题。除了他们的内在利益，许多这些问题的动机是在其他领域的相关问题。特别是，研究分裂随机项链有一个令人惊讶的联系问题的随机游动在欧几里德空间和匹配的近正则一致超图。项链定理的算法方面是有趣的，鉴于最近的结果的硬度的问题。该项目中描述的其他一些公平划分问题的算法方面的相关研究也具有挑战性。调查的图形代码，这是有趣的，在其本身的权利，也是出于问题的拉姆齐型结果添加剂组合。主要研究者打算应用的方法结合了联合收割机组合，概率，代数和几何工具与编码理论的思想。预计在这里提到的问题上的进展将是有趣和重要的，将有望导致新的富有成效的技术的发展，并将产生有趣的应用和相关领域的见解。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。