Preview

PDF, English - main document Download (1MB) | Terms of use

Abstract

Consider the random greedy hypergraph matching process that, for a given hypergraph H, iteratively chooses edges of a matching as follows. In every iteration, an edge is chosen uniformly at random among all edges of H that do not intersect a previously chosen edge. If no such edges exist, then the process terminates. We analyze the behavior of a variation and a special case of this process. For the variation we consider, there is an initially given collection of forbidden edge sets that are not allowed to be subsets of the generated matching. Edges are then not chosen among all those that do not intersect with a previously chosen edge, but only among those that also do not form such a forbidden edge set with previously chosen edges. We call this variation the conflict-free matching process. Through an analysis of this process, we determine conditions on the hypergraph H and the collection of forbidden edge sets that still allow us to guarantee that, with high probability, the process generates a matching that covers all but a small fraction of the vertices of H. This in turn allows us to obtain general theorems that describe settings where almost-perfect matchings with pseudorandom properties that also avoid given edge sets as subsets exist. Exploiting that a wide range of combinatorial problems can be phrased as hypergraph matching problems, these theorems can be applied in several different areas. As one application, we prove an approximate version of a generalization of a conjecture of Erdős about Steiner systems. Perhaps one of the most obvious ways to construct a k-uniform hypergraph on n vertices containing no copies of a fixed k-uniform hypergraph F, but preferably many edges, is the F-removal process. Starting with a complete k-uniform hypergraph on n vertices, this iterative process proceeds as follows. In every iteration, all edges of a copy of F chosen uniformly at random among all remaining copies are removed and once no copies of F remain, the process terminates. While this process, which corresponds to the random greedy hypergraph matching process in an auxiliary hypergraph, is easy to formulate, proving that asymptotic runtime bounds with the correct order of magnitude hold with high probability is challenging. So far, ignoring the cases where F has at most one edge, such proofs were only available for one choice of F, namely when F is a triangle. We extend this by proving such bounds whenever F comes from a large natural class of hypergraphs. As this class in particular includes all complete uniform hypergraphs, this confirms the major folklore conjecture in the area in a very strong form.