Topological Methods for Discrete Problems

我们经常遇到具有内在对称性的情况，例如试图公平地将一件物品分配给几个参与方：如果我们的分配是真正公平的，我们可以在不改变结果的情况下排列这些物品。这种观点也出现在更抽象的情况下，例如用线性方程以平衡的方式分解数据集以有效地处理它，或者在一组固定的点上评估函数以计算其积分。请注意，如果我们将有关各方的主观偏好引入公平分配问题，固有的对称性就会消失。再一次，对称性的丧失对于目前提到的这类问题来说是一种自然现象。这个项目开发了解决这些问题的方法，即使在没有对称的情况下。值得注意的是，这些方法是拓扑的，也就是说，是连续的，而这些问题具有组合性或离散性。因此，这项研究在数学的不同分支之间建立了桥梁，使一个分支的问题适用于另一个分支的工具。PI将从几何观点出发，对一系列组合问题进行研究。研究的主题包括集合的相交模式，无论是在纯组合设置（如超图匹配和设计理论），还是在几何设置（如凸集的相交和复合体的非嵌入到欧几里德空间），以及在阿贝尔群中的结构化集合的研究（如sumset，包含零和的集合结构，和球形设计）。在这些问题中，人们对构建一个对象或显示其不存在感兴趣，但全局障碍出现了——局部解决方案不能粘合在一起形成所需的对象。几何和拓扑学提供了一个合适的框架来组织这些非局部现象，并在大范围内检测这些障碍物。本研究的重点是承认几何推广的问题，旨在将刚性离散结果与更灵活的几何对应物区分开来。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

We often encounter situations with inherent symmetries, such as attempting to fairly divide a good among several parties: If our division is truly fair, we could permute the pieces without changing the outcome. This viewpoint arises also in more abstract settings, such as decomposing a data set in a balanced way with linear equations to efficiently handle it, or evaluating a function in a fixed set of points to compute its integral. Note that if we introduce subjective preferences of the involved parties to our fair division problem, the inherent symmetries disappear. Again this loss of symmetry is a natural phenomenon for the class of the problems mentioned so far. This project develops methods to approach such problems, even in the absence of symmetry. Notably, the methods are topological, that is, continuous, whereas the problems have a combinatorial, or discrete, flavor. Thus this research builds bridges between different branches of mathematics, making problems in one branch amenable to the tools of another.The PI will conduct research on a selection of combinatorial problems that benefit from a geometric viewpoint. Among the themes of research are intersection patterns of sets, both in a purely combinatorial setting (such as hypergraph matchings and design theory) as well as in geometric settings (such as intersections of convex sets and non-embeddability of complexes into Euclidean space), and the study of structured sets in abelian groups (such as sumsets, the structure of sets containing zero-sums, and spherical designs). These are problems, where one is interested in constructing an object or showing its non-existence, but global obstructions emerge---local solutions do not glue together to form the desired object. Geometry and topology provide a suitable framework to organize these non-local phenomena and detect such obstructions in the large. This research focuses on problems that admit geometric generalizations and aims to delimit rigid discrete results from their more flexible geometric counterparts.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.