Shira Zerbib receives National Science Foundation CAREER Award

Mathematics Associate Professor and Scott Hanna Faculty Fellow Shira Zerbib was recently selected by the National Science Foundation (NSF) as a recipient of the Faculty Early Career Development Program (CAREER) award.

CAREER awards are the NSF’s most prestigious awards given to early-career faculty. The support aims to build a firm foundation for leadership in integrating research and education. Shira will receive $450,000 to develop and implement her research project over the next five years.

Shira specializes in combinatorics, a mathematical field that focuses on the study of finite discrete structures. Her research tackles issues related to the behavior of families of sets. She employs advanced mathematical tools from various domains to explore how these sets can be efficiently represented using a minimal number of elements. Her work has wide-ranging applications in computer science, data analysis, biology, economics, and the social sciences.

Specifics regarding her project can be found below.

Congratulations, Shira!

Abstract: The purpose of the 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 evident from 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. 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.