The ACO Seminar (2024–2025)

A graph H embeds in a graph G if G contains a subgraph isomorphic to H, and it decomposes G if the edges of G can be partitioned into subgraphs isomorphic to H. Questions about when a graph embeds in or decomposes another are central in combinatorics. “Dirac-type” embedding results address minimum-degree conditions to ensure an embedding of some graph. Block designs, a fundamental object of Design Theory, are decompositions of complete graphs.

In this talk, we will discuss robustness of embeddings and decompositions. For example, given a hypergraph of large minimum degree, we will discuss the threshold for a random subhypergraph to have a perfect matching or Hamilton cycle. We will also discuss the threshold for constructing block designs using only a random selection of blocks. All of these results utilize the recent Park–Pham Theorem or one of its variants. A crucial notion for this is that of the spreadness of a certain type of probability distribution.