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

职业：刺穿数、质量划分和公平除法的 KKM 型定理

• 批准号: 2336239
• 负责人: Shira Zerbib
• 金额: $ 45万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2029-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2336239&HistoricalAwards=false
• 关键词: CAREER; KKM; Type; Theorems; Piercing

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.

这个项目的目的是开发尖端的数学方法来解决三个不同领域的问题：穿孔数，公平分割和质量分割。刺穿数是离散数学中的一个领域，它寻求与给定集合族中的所有集合相交所需的最小元素数量。这个元素的最小集合称为族的穿刺集合。许多实际问题可以被公式化为关于穿孔集合的问题，其中集合族可以在各种上下文中出现（例如，社交网络中的订户、地理区域、生物细胞）。蜂窝通信的一个例子如下：假设一个蜂窝塔的范围是200英尺，一家公司必须放置的最小塔数是多少，这些塔应该放置在哪里，以便每个家庭都有服务？在这里，集合族是以每个家庭为中心的半径为200英尺的圆盘族，并且细胞塔将被放置在穿孔集合的每个点处。公平分配和质量分配是经济学和离散数学中的一个领域，其目的是找到最佳的方法来在具有主观偏好的代理人之间公平地分配一组商品。这些方法可用于在继承人之间分割遗产、珠宝收藏或一块土地，或者在合伙关系解散时分割企业资产。从上述所有例子中可以明显看出，作为本项目一部分研究的问题是自然的、直观的，并且易于制定。然而，它们往往是出了名的难以回答，需要来自不同数学领域的复杂工具。该项目旨在从一个称为拓扑学的数学领域开发此类工具。该项目的教育部分包括为本科生和研究生提供“组合数学中的拓扑方法”暑期学校，编写有关该主题的教科书，并指导学生和博士后。该项目的重点是开发基于KKM定理及其扩展的拓扑框架，以解决这些问题。这个拓扑框架可以描述如下：问题所有可能解的配置空间（即所有可能的穿透集/质量划分/货物划分）由多面体P建模;如果在所有可能的解P的集合中没有找到“好”解，则获得P的KKM覆盖;拓扑定理的结论，即在这个KKM覆盖中的集合的足够大的集合相交，然后被转化为与所讨论的集合/质量/货物族的给定性质的矛盾。该项目的主要目标包括两个主要方面：第一，发现新的KKM型定理，可以有效地利用这一拓扑框架，第二，该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响进行评估来支持审查标准。