Matching Theory in Hypergraphs

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

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.