Topological Methods for Discrete Problems

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

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.