Combinatorics Seminar - Spring '22

When: Sunday, February 20, 10am

Where: Zoom

Speaker: Mykhaylo Tyomkyn, Charles University

Title: Weakly Saturated Hypergraphs and a Conjecture of Tuza


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.