Topology and Linear Algebra in Discrete Geometry

Cuny Baruch College, New York NY

Investigators

Abstract

Discrete geometry is the study of combinatorial properties of finite families of geometric objects. Results in this field often have applications to search algorithms, data classification, and optimization. The methods used to answer discrete geometry questions can be wildly different. Some are based on linear algebra, where the rigid structure of the space is important. Some are based on topology, and the results hold up to smooth deformations of the objects involved. This research project aims to develop new ways to use topological and linear algebraic methods in discrete geometry to expand the connections between combinatorics and other fields. The driving motivation is to understand what makes a combinatorial problem amenable to techniques from topology, and what makes it amenable to techniques from linear algebra. The project also includes topics that can be used to mentor undergraduate students in research. The project focuses on questions related to finite families of convex sets. The PI plans to develop new ways to apply topological methods to Tverberg-type problems, related to a longstanding "colorful" version of Tverberg’s theorem. The recent progress in quantitative Helly-type theorems can help build a bridge between the analytic side of convexity and linear programming, which the PI aims to formalize. Several of the questions under study aim to generalize classic results in extremal combinatorics to high-dimensional Euclidean spaces. 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.