Extremal Combinatorics: Problems and Algorithmic Aspects

极值组合学是现代组合学中最活跃的领域之一，在过去的几十年里得到了惊人的发展。它处理确定或估计满足一定条件的组合结构不变量的最大或最小可能值的问题，以及研究组合不变量之间的不等式和处理它们之间关系的问题。首席研究员打算调查该领域的几个问题，包括由算法应用程序驱动的问题。要研究的具体主题包括图论和组合学中的新旧问题，以及关于项链和图的公平表示的算法方面的问题。其中一些问题的非建设性解决方案结合了代数和拓扑工具，留下了寻找算法解决方案的迷人问题。该建议解决了几个基本的新旧组合问题。除了他们的内在兴趣，许多这些问题是由其他领域的相关问题所激发的。特别是，分割随机项链的研究与欧几里得空间中的随机漫步和近规则均匀超图中的匹配问题有着惊人的联系。项链定理的算法方面是有趣的，考虑到最近关于这个问题的硬度的结果。该项目中描述的一些其他公平划分问题的算法方面的相关研究也具有挑战性。Graph Codes的研究本身就很有趣，它也是由Additive Combinatorics中关于Ramsey类型结果的问题所激发的。主要研究者打算将组合、概率、代数和几何工具与编码理论的思想相结合。我们期望在这里提到的问题的进展将是有趣的和重要的，将有望导致新的富有成效的技术的发展，并将产生有趣的应用和见解在相关领域。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.