Topological Methods for Discrete Problems

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.