Richard P. Stanley Seminar in Combinatorics: Hypergraph embeddings and decompositions: robustness via spreadness

SEMINARS, HARVARD-MIT COMBINATORICS

Speaker:

Tom Kelly - Georgia Tech

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.

===============================

For more info, see https://math.mit.edu/combin/