CAREER: KKM-Type Theorems for Piercing Numbers, Mass Partition, and Fair Division

Iowa State University, Ames IA

Investigators

Abstract

The purpose of this project is to develop cutting-edge mathematical methods for solving problems in three different domains: piercing numbers, fair division, and mass partition. Piercing numbers is an area in discrete mathematics that seeks the minimum number of elements needed to intersect all the sets in a given family of sets. This minimal set of elements is called a piercing set of the family. Many practical problems can be formulated as questions about piercing sets, where the family of sets may arise in various contexts (e.g., subscribers in a social network, geographical areas, biological cells). An example from cellular communication is as follows: given that the range of a cell tower is 200 feet, what is the minimum number of towers a company has to place, and where should those towers be placed, so that every household has service? Here, the family of sets is the family of disks of radius 200 feet centered at every household, and cell towers are to be placed at every point of a piercing set. Fair division and mass partition are areas in economics and discrete mathematics where one aims to find optimal ways to divide a set of goods equitably among agents with subjective preferences. These methods can be used to divide an estate, a jewelry collection, or a piece of land among heirs, or to split up the assets of a business when a partnership is being dissolved. As is apparent in all the above examples, the questions studied as part of this project are natural, intuitive, and easy to formulate. However, they are often notoriously difficult to answer and require sophisticated tools from different areas of mathematics. This project aims to develop such tools from an area of mathematics called topology. The educational component of this project includes delivering summer schools on “Topological Methods in Combinatorics” to undergraduate and graduate students, writing a textbook on the subject, and mentoring students and postdocs. The project focuses on the development of a topological framework based on the KKM theorem and its extensions to address these problems. This topological framework can be described as follows: the configuration space of all possible solutions to the problem (that is, all possible piercing sets/mass partitions/partition of goods) is modeled by a polytope P; if no "good" solution is found among the set of all possible solutions P, then one obtains a KKM cover of P; the conclusion of the topological theorem, namely that a large enough collection of the sets in this KKM cover intersects, is then translated to a contradiction to the given properties of the family of sets/mass/goods in question. The main objectives of this project include two primary aspects: first, the discovery of new KKM-type theorems that can be effectively employed within this topological framework, and second, the exploration of innovative ways to leverage this topological method in resolving discrete math problems. 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.