Title: Robustness for hypergraph embeddings via spreadness
| Speaker: | Tom Kelly |
| Affiliation: | Georgia Tech |
| Location: | MC 5479 |
Abstract: In joint work with Kang, K\"uhn, Methuku, and Osthus, we proved the following: If $p\geq{C\log^2n/n}$ and $L_{i,j}\subseteq[n]$ is a random subset of $[n]$ where each $k\in[n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,j\in[n]$, then asymptotically almost surely there is an order-$n$ Latin square in which the entry in the $i$th row and $j$th column lies in $L_{i,j}$. We prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs. These results can be understood as stating that these ``design-like'' structures exist ``robustly''.
In joint work with Kang, K\"uhn, Osthus, and Pfenninger, we proved various results stating that if $\mathcal{H}$ is an $n$-vertex $k$-uniform hypergraph satisfying some minimum degree condition and $p=\Omega(n^{-k+1}\log n)$, then asymptotically almost surely a $p$-random subhypergraph of $\mathcal{H}$ contains a perfect matching. These results can be understood as ``robust'' versions of hypergraph Dirac-type results as they simultaneously strengthen Johansson, Kahn, and Vu's seminal solution to Shamir's problem on the threshold for when a binomial random $k$-uniform hypergraph contains a perfect matching. In joint work with M{\"u}yesser, and Pokrovskiy, we proved similar results for hypergraph Hamilton cycles.
All of these results utilize the fractional version of the Kahn--Kalai conjecture, recently established by Frankston, Kahn, Narayanan, and Park, which provides bounds for thresholds in terms of the minimum \textit{spreadness} of a certain type of probability distribution.