eprintid: 36726
rev_number: 12
eprint_status: archive
userid: 9084
dir: disk0/00/03/67/26
datestamp: 2025-06-18 09:39:53
lastmod: 2025-06-20 07:19:59
status_changed: 2025-06-18 09:39:53
type: doctoralThesis
metadata_visibility: show
creators_name: Kühn, Marcus
title: The Random Greedy Hypergraph Matching Process
subjects: ddc-510
divisions: i-110400
adv_faculty: af-11
cterms_swd: Hypergraph
cterms_swd: Matching
cterms_swd: Stochastischer Prozess
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.
date: 2025
ppn_swb: 1928712525
own_urn: urn:nbn:de:bsz:16-heidok-367264
date_accepted: 2025-06-02
advisor: HASH(0x55caa0d9b830)
language: eng
bibsort: KUHNMARCUSTHERANDOMG20250613
full_text_status: public
place_of_pub: Heidelberg
citation:   Kühn, Marcus  (2025) The Random Greedy Hypergraph Matching Process.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/36726/1/thesis_marcus_kuehn.pdf