Open Collections

Perfect matchings in subgraphs of random hypergraphs

Banff International Research Station for Mathematical Innovation and Discovery

Let $m_d(k,n)$ be the minimal $m$ such that every $k$-uniform hypergraph on $n$ vertices and with minimum $d$-degree at least $m$ contains a perfect matching (of course, assuming that $n$ is divisible by $k$). The problem of determining $m_{d}(k,n)$ has attracted a lot of attention in the last few decades, and unfortunately is still far from being completely understood. For example, already the cases $d=1$ and $k\geq 6$ are unknown. In this talk we show that random hypergraphs typically behave as expected. Specifically, we prove (without knowing $m_d(k,n)$) that for a typical $H^k_{n,p}$ with $p\geq n^{-c(d,k)}$, every spanning subgraph with minimum $d$-degree at least $(1+o(1))m_d(k,n)p$ contains a perfect matching. This is clearly (asymptotically) best possible. Joint work with Matthew Kwan.

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: MIT

2020-09-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75862

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/