Matching Theory in Hypergraphs

超图中的匹配理论

• 批准号: 1953929
• 负责人: Shira Zerbib
• 金额: $ 14万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1953929&HistoricalAwards=false
• 关键词: Matching; Theory; Hypergraphs

Matching theory is an area in discrete mathematics that asks for the minimum number of elements needed to intersect all the sets in a given family of sets. Such a minimal set of elements is called a cover of the family. Many practical problems can be formulated as questions about covers of families of sets that arise in different contexts (for example, subscribers in a social network, geographical areas, biological cells). An example from public health is: How many medical clinics should be placed in a given state, and where, so that every resident has a clinic within 50 miles of home? Here the sets in question are disks of radius 50 miles centered at every household, and clinics are to be placed in every point of a cover. As apparent from this example, the questions studied in matching theory can be basic and intuitive, easily formulated, and are combinatorial, or discrete, in flavor. Nevertheless, they are often notoriously difficult to answer and require sophisticated tools from different areas of mathematics (such as algebra, probability, and topology) for their solution. This project focuses on developing improved methods (primarily topological ones) to approach several fundamental open problems in matching theory. As the methods developed come from other areas of mathematics, this project also contributes to building bridges between different branches of mathematics, making problems in one branch amenable to the tools of another. The project involves a graduate student in the research. This project studies matching theory in abstract finite hypergraphs, as well as hypergraphs arising from geometrical structures, whose edges are (generally, infinite) sets in a Euclidean space. Two intriguing longstanding conjectures on abstract hypergraphs motivate this project: one (Gyárfás-Lehel) concerns covers of hypergraphs consisting of cross-intersecting families of sets, and the other (Tuza) deals with covers of hypergraphs of triangles in graphs. Both conjectures received considerable attention over the years, mostly using elementary approaches, which now seem insufficient for their solution. One goal of this project is to develop new tools from other areas of mathematics for tackling these conjectures and related problems. Hypergraphs arising from geometrical structures are of special interest to researchers, as they appear in many different practical applications; consequently, questions in matching theory of geometrical hypergraphs have been widely studied (under different names) for decades. Within this direction, the project focuses on a conjecture of Wegner on covers of families of axis-parallel rectangles in the plane (and families of axis-parallel boxes in higher dimensions). The second main goal of this project is to develop a topological method in higher dimensions for the resolution of Wegner’s conjecture.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.

匹配理论是离散数学中的一个领域，它要求与给定集合族中的所有集合相交所需的元素的最小数量。这样的元素的最小集合称为族的覆盖。许多实际问题可以被公式化为关于在不同上下文中出现的集合的族的覆盖的问题（例如，社交网络中的订户、地理区域、生物细胞）。公共卫生的一个例子是：在一个给定的州应该有多少医疗诊所，在哪里，这样每个居民在离家50英里内都有一个诊所？这里的集合是以每户为中心的半径为50英里的圆盘，诊所将被放置在覆盖物的每一个点上。 从这个例子中可以明显看出，匹配理论中研究的问题可以是基本的和直观的，容易公式化，并且是组合的，或者是离散的。然而，它们往往是出了名的难以回答，需要来自不同数学领域（如代数，概率和拓扑学）的复杂工具来解决。这个项目的重点是开发改进的方法（主要是拓扑的），以接近匹配理论中的几个基本的开放问题。由于开发的方法来自数学的其他领域，该项目还有助于在数学的不同分支之间建立桥梁，使一个分支中的问题适合于另一个分支的工具。该项目涉及一名研究生的研究。这个项目研究抽象的有限超图中的匹配理论，以及由几何结构产生的超图，其边缘是欧几里得空间中的（通常是无限的）集合。两个有趣的长期存在的抽象超图的理论激发了这个项目：一个（Gyárfás-Lehel）涉及由交叉相交的集合族组成的超图的覆盖，另一个（Tuza）涉及图中三角形超图的覆盖。多年来，这两种方法都受到了相当大的关注，大多数都使用了基本方法，现在看来这些方法不足以解决问题。这个项目的一个目标是从其他数学领域开发新的工具来解决这些问题和相关问题。由几何结构产生的超图引起了研究人员的特别兴趣，因为它们出现在许多不同的实际应用中;因此，几何超图的匹配理论中的问题已经被广泛研究了几十年（以不同的名称）。在这个方向上，该项目的重点是韦格纳猜想覆盖家庭的轴平行矩形在平面上（和家庭的轴平行框在更高的维度）。该项目的第二个主要目标是在更高的维度上开发一种拓扑方法来解决Wegner猜想。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。