Disputation Marcus Kühn The Random Greedy Hypergraph Matching Process

Für einen festen uniformen Hypergraphen H betrachten wir den Zufallsprozess, der, beginnend mit einem vollständigen uniformen Hypergraphen auf n Ecken, iterativ wie folgt verfährt. In jeder Iteration werden alle Kanten einer uniform zufällig unter allen verbleibenden Kopien von H ausgewählten Kopie entfernt. Sobald keine Kopien von H verbleiben, terminiert der Prozess. Was können wir über die Zahl R(n,H) der nach dem Terminieren übrigen Kanten sagen? Dieser Prozess, welcher dem Random Greedy Hypergraph Matching Prozess in einem Hilfshypergraphen entspricht, ist leicht zu formulieren, es ist aber eine Herausforderung, zu zeigen, dass asymptotische Schranken der richtigen Größenordnung für R(n,H) mit hoher Wahrscheinlichkeit gelten. Abgesehen von den Fällen, bei denen H höchstens eine Kante hat, waren solche Schranken bis jetzt nur für eine einzige Wahl von H verfügbar, nämlich nur, wenn H ein Dreieck ist. Als Erweiterung dessen zeigen wir analoge Schranken für alle Fälle, in denen H Teil einer großen natürlichen Klasse von Hypergraphen ist. Da diese Klasse insbesondere alle vollständigen uniformen Hypergraphen umfasst, bestätigt dies eine zentrale Vermutung in diesem Forschungsgebiet auf sehr allgemeine Weise.