Matching Theory in Hypergraphs

Iowa State University, Ames IA

Investigators

Abstract

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.