Talk information

Date: Sunday, February 20, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Mykhaylo Tyomkyn (Charles University)
Title: Weakly Saturated Hypergraphs and a Conjecture of Tuza

Abstract:

For two $r$-uniform hypergraphs $G$ and $H$ we say that $G$ is weakly $H$-saturated if the missing edges in $G$ can be filled one by one, creating a new copy of $H$ at every step. The quantity $wsat(n,H)$ measures the smallest size of a weakly $H$-saturated $r$-graph of order $n$. For $r=2$ a short argument due to Alon (1985) shows that for any graph $H$, $wsat(n,H)/n$ tends to a limit as $n$ increases. Tuza conjectured in 1992 that for arbitrary $r$ the quantity $wsat(n,H)/n^{r-1}$ similarly has a limit $c(H)$. I will present a recent proof of Tuza’s conjecture.

Joint work with Asaf Shapira.